the system test has finished, but my solution on C did not judge, what happened?

.

Very difficult A. The problems in general feel very observational. At least they are interesting.

My funny solution for G: Basically the same as the editorial, but instead of maintaining paths by their LCA, maintain them by their highest degree node. This means that each node will affect $$$\sqrt n$$$ nodes instead of just $$$1$$$, yielding an $$$O(q\sqrt n \lg n)$$$ solution. Implemented in C++ this takes 453 ms.

For me, it's like:

A: acceptable.

B: prime factorization is not something that appears in d2B, and the task is quite boring.

C: Nothing wrong, but it is too hard for C I guess.

D: Easy problem with details, but nothing too wrong.

E: Actually the guesses is not quite easy to make, especially for person like me tended to prove all the guesses during the contest. So it's kind of acceptable.

F: Huge work. Very, very large work. Is these kinds of problems really suitable for codeforces? We have D and G to let participants do huge works(lol

G: Huge work. Not interesting, and it's a little bit tricky to understand the problem correctly. H : Not able to give comments.

I : Too similar to some other problems.

If F is a div2D problem which only ask the minimal value, this contest would be better.

problem B. what am I doing wrong here(https://codeforces.com/contest/1787/submission/191135406). can I see the testcase for which this code fails?

Thanks for the well written editorial

Seriously, how did the top 1 solve problem H in 14 minutes?

Here goes complicated solns of A-F

For problem C, why can we assume that y_(i-1) < x_(i+1) ?

Not sure why the editorial says $$$O(n\log^2n)$$$ is "not good enough" for I, it seems that many of the solutions that passed have this complexity (191159985, 191159474, 191162667, 191147979).

Bonus F: solve problem but instead of reversing P^(2^k), we reverse P^(k).

Did anyone else do that? :P

Real math forces

On E my code only make subsequences like $$$[a,a\oplus x]$$$ and overlook $$$[x]$$$, but it's accepted, so does it work or it can be hacked?

Can somebody recommend problems similar to problem C ?

Can you roll back and give me another 1 rating? It's sad to be stuck at a rating of 1599.

I have some questions about problem H's editorial.

is $$$lim_i = c_i$$$?

The sentence

" with an additional number $$$k_i \times j$$$ in the middle, where $$$j$$$ is the maximum number satisfied $$$g_{i-1,j-1} \leq k_i \times j$$$ "

Shouldn't be:

"with an additional number $$$k_i \times j - lim_i$$$ in the middle, where $$$j$$$ is the maximum number satisfied $$$g_{i-1,j-1} \leq k_i \times j - lim_i$$$" ?

The way the sentence right now looks like you just ignore the $$$lim_i$$$ value in the minimum, which doesn't make sense to me.

I'm curious as to what the intuition behind problem E is supposed to be. It seems hard to figure out the ideal strategy.

Many people solved E in the end but I didn't :V. I should have prac more problem like this

I think the "reasom" in "Fact" of 1787C should be "reason".

I upsolved D and E on my own, should have skipped C :/. Didn’t know how to do dp. E was pretty interesting to prove.

The proof part of problem E:

"These $$$B$$$-th-bit-on numbers XOR $$$x$$$ must be smaller than themselves, so we can always obtain $$$M$$$ subsequences."

I suppose we can not know whether the $$$B$$$-th-bit-on numbers is smaller than $$$x$$$ since the highest digit of $$$x$$$ may not be the highest of these numbers.(for instance, $$$x=2$$$, while $$$a_i=4$$$, and $$$x \oplus a_i$$$ is $$$6$$$)

can someone explain how C can be done by DP? (I'm new to this)

Can someone please explain me the proof of E and why this solution works?

In problem D WA although my idea is the same as the editorial and I cant find the bug

can anyone help? here is it 191163552

edit:bug found

In problem C, for s = 3 and a[i] = 5. What can be the values of x and y? If I take (x,y) as (2,3) or (1,4) or (0,5) then the product (x-s)(y-s) becomes <0.

1787C - Remove the Bracket For those who as me struggle to understand tutorial, here is explanation what they want to say. They want to say that optimal selection of x, y might be only on edge cases, by way of contradiction. Suppose some is not on edge case. Then it has $$$y_{i−1}$$$ and $$$x_{i+1}$$$. Two cases $$$y_{i−1} < x_{i+1}$$$ and $$$y_{i−1} > x_{i+1}$$$ lead to contradiction based on things from the editorial (look into it). And in the remaining case $$$y_{i-1} = x_{i+1}$$$ we can pick edge x, y without any loss.

In problem C, can anyone explain what difference it makes logically (in dp transition) if we replace the original transition,

F[i][0] = min( F[i-1][0]+y[i-1]*x[i],F[i-1][1]+x[i-1]*x[i] );
F[i][1] = min( F[i-1][0]+y[i-1]*y[i],F[i-1][1]+x[i-1]*y[i] );

to this transition,

F[i][0] = min( F[i-1][0]+x[i-1]*x[i],F[i-1][1]+y[i-1]*x[i] );
F[i][1] = min( F[i-1][0]+x[i-1]*y[i],F[i-1][1]+y[i-1]*y[i] );

The answer for the second transition is coming different from the original answer but both of the transition seem correct to me logically.

Who is the Problem Authors ?

Can anyone give a reason why the following solution to H is wrong or give an example when the following solution fails.

We pick the problem we would solve i'th minutes after the contest begins by picking the problem whose value would decrease the most after 1 minute passes. The implementation would be done using a multimap to store the problem whose value would decrease the most. The multimap will be maintained by getting all the values of t'(minutes)s when the a particular problem stops decreasing and by updating the multimap when that time comes.

"Changing edges not on the key path is always legal. If changing the edges on the key path, for node x, we can change its successor to nodes except its precursor or itself."

We can also not change it to nodes which lead into cycles right? Its not enough to just subtract paths to predecessors on key path, we also have to subtract paths to nodes which lead into cycles right?

I have a different solution for problem $$$G$$$.

The idea is to run a BFS and label the edges according to when they were processed by the BFS. Below, I have the tree, with the edge colors and labels.

Now, we can turn these edge labels into color labels. Define the label of a color to the minimum label of one of its edges. For instance, the label of the red path is 1, and the label of the yellow path is 18. The label of the purple color is 13.

Now, whenever we perform an update (blocking or unblocking a node), we are updating at most two continuous range of labels. Say, for instance, we update the root of the tree. Then, we're blocking "red" and "blue" (label 1 and 2). If we were to update the node from which edges 4,5,6 protrude, then we're blocking "red" and "blue (4 and 5).

Now, updating continuous ranges of intervals can be done with a segment tree. Let the index of the segment tree be the label of each color. So segmentTree[label[i]] = sum of weights of path with color i.

Each time, we block some "path", we can subtract a big number from that contiguous range of the segment tree. Each time we unblock that path add back that big number. Now, it's just range minima of whole segment tree and range add.

When will the plagiarism check run? 1787-C, Remove brackets was leaked on youtube and many cheaters did it disrupting the standings.

D: "If changing the edges on the key path, for node x, we can only change its successor to nodes on the tree with the end node except its precursor or itself."

We are counting the opposite so shouldn't it be "to its precursor or itself on the tree with the end node"? Of course we also consider nodes outside the tree.

E: "the rest becomes a subsequence".

Shouldn't it be "adding the rest to one of the other subsequences"? If there is a solution then the rest must xor to zero (obviously the rest cannot xor to $$$x$$$) so we can add the rest to any other subsequence.

Here am I with my toxic grumblings about the quality of editorials again. Nothing new, I just decided to try reading editorials again and once again I ask myself why the editorial authors hate their readers so much.

I'm just opening the solution for D and the first thing I see is

int a[N], v[N], s[N];
struct E {
	int to;
	E *nex;
} *h[N];

The heck is a? the heck is v? the heck is s? Why the list of edges is h?
Probably it should be relatively easy for the typical audience of this problem to deduce that E means edge even if you don't care about the others, but a/v/s/h is just too much. I won't even ask why you needed a linked list.

As a result, decoding and deobfuscating the heck is written in the "author's solution" easily competes by difficulty with the original problem.

I understand that codeforces doesn't enforce the quality of editorials and it is done by putting the minimum effort possible, but put at least the minimum effort into making it readable, this is so below any bar.

I find it hard to comprehend that people spend some supposedly huge amount of time on coming up with and polishing those problems, but cannot find some minutes to make the code they just submitted at least a bit readable before attaching to the editorial

what is approximate difficulty of problem D?

When the ratings will get reupdated???????????? I became pupil, please re-add them fast!!!!

This contest was unique in that sense, that there were 3 working problems for me (Definition: working problem is a problem with difficulty approximately equal to contestant's rating), while for all contests it was either $$$0$$$ or $$$1$$$.

From my point $$$D$$$ and $$$E$$$ have equal difficulty, and $$$C$$$ is a little more complex. It was foolish, that I didn't give a try for problem $$$E$$$, but after I read first sentense in editorial, I thought "damn, it is obvious" and quickly implemented it.

why in problem c after remove the bracket (xi+yi) it turns to …+yi−1⋅xi+yi⋅xi+1+????

It's actually quite confusing you can't use python for a tutorial solution of a D problem. Is it true or i just do not know how to set recursion depth limit without getting ML?

193974524

Could anyone help me figure where my idea for problem C is wrong? The idea is as follows:

$$$F_n=a_1x_2+y_2x_3+y_3x_4+\ldots+y_{n-2}x_{n-1}+y_{n-1}a_n$$$

$$$F_{n-1}=a_1x_2+y_2x_3+y_3x_4+\ldots+y_{n-2}a_{n-1}$$$

$$$F_{n-1}=a_1x_2+y_2x_3+y_3x_4+\ldots+y_{n-2}x_{n-1}+y_{n-2}y_{n-1}$$$

Therefore:$$$F_n-F_{n-1}=y_{n-1}(a_n-y_{n-2})$$$

So, we can calculate $$$F_3$$$ and use dp to figure out $$$F_n$$$ with appropriate $$$y_{n-1}$$$. The consecutive range of $$$y_i$$$ can be determined by $$$x_i+y_i=a_i$$$ and $$$(x_i-s)(y_i-s)\geq 0$$$.

However, my submission is not correct for the 10th input data. 202618323

So what's the solution of bonus E?there is a obvious upper limit -[n/3],but is hard to reach it