Idea & Solution: rsj

**Tutorial**

Idea & Solution: rsj

**Tutorial**

**Solution**

Idea & Solution: rsj

**Fact**

**Tutorial**

**Solution**

Idea & Solution: jiangtaizhe001

**Tutorial**

**Solution**

1787E - The Harmonization of XOR

Idea & Solution: jiangtaizhe001, rsj

**Tutorial**

**Bonus Problem**

1787F - Inverse Transformation

**Tutorial**

**Solution**

Idea & Solution: rsj, 275307894a

**Tutorial**

Idea & Solution: jiangtaizhe001, rsj

**Something To Say**

**Tutorial**

Idea & Solution: 275307894a

**Tutorial**

I'm really sorry for the unsatisfactory problems and the tough 3 hours ;)

However, I still hope you can enjoy the problems after the contest. The editorial hasn't been fully checked, so feel free to comment if there're errors, typos or you have questions about them. We'll check them out tomorrow. Thanks!

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

it's accepted now

congratulations bro

bro how your ratings is that high ?? Do you have any past experiences with CP ??

Well, he started in 2012 :D

https://codeforces.com/blog/entry/112007 please help!!!!!!something is wrong in this legendary round

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

i think most who solve it try x=1 and get fun equal 2*y and notice that no sol for odd from test case

Yeah, I realized that the equation would always be even so I looked for a way to construct even answers. But originally I thought you could brute force it since n has to be divisible by xy so I tried finding divisors and looking for the other component. Probably should have realized that problem A shouldn’t be that hard.

you could bruteforce it using binary search 191169657

Time complexity? I don’t know how your iterating though all of n.(Java user here)

there's a fair amount of boilerplate for checking if values are out of bounds in the binsearch loop and once more after the loop. But other than that I think the code is fairly simple. WLOG let's assume x <= y. Then the outer loop iterates over x up until n (if we find solution or we know we won't find it we just break out of the loop). The inner loop binsearches on y from x to n. If y is the smallest possible (equal to x) but the formula gives an integer bigger than n, we know we are out of options so print -1 and return.

As for TC, the solution can't iterate too high in the x, because the value of the formula grows exponentially. Inner loop (binsearch) is O(log n). So a rough upper bound is O(log^2 n)

P.S. solve() function would look the same in Java, except for stdin/out (using cin and cout). Maybe bool -> boolean too, and you have Java code, it's all the same as C lol

Chat gpt is pro in converting code from one language to another. Just 2-3 subtle changes and we are done

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.

And I solved it using centroids, thus adding log factor to the solution and not changing the idea. Couldn't implement it in time, though...

Luckily for me, I had enough time even to convert to C++ after my Kotlin attempt TLEd.

Update: I was able to hack (TLE) my solution: https://codeforces.com/contest/1787/hacks/886533 Seems like it was completely unanticipated by the authors >:).

problem A is fun

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.

I don't agree that F was huge work. It was fine for that slot.

Well, maybe I'm not good in solving these kind of implement problems:( But I think the implement part is far bigger than the thinking part.

If G feels like huge work to you, I don't think you are able to judge that problem

Interesting. You are right.

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?

click show test details at the bottom

I think there's precision errors because you have

`number = number / i`

instead of`number = number // i`

. I couldn't find a test case that breaks it but 191191379 get's AC. (Seems like a strange behavior since we just checked that the numbers are actually divisible...but I'm not very good at Python so maybe it's expected).Probably because number / i returns a float and number // i returns an int in python, computing floats is probably decently slower

thank you, will keep in mind next time

Thanks for the well written editorial

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

`You spend exactly one minute to solve each problem`

By the statement of problem H, he delayed for 6 minutes.

Here goes complicated solns of A-F

Compiled you mean?

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

Because $$$y_{i-1}>x_{i+1}$$$ is symmetric with this

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?

Oh I know, if the answer is YES and $$$x\le n$$$, let $$$m$$$ be the number of subsequences $$$[a,a\oplus x]$$$, then $$$m\ge k-1$$$, $$$m\equiv (k-1) \pmod 2$$$.

if $$$m=k-1$$$, $$$[x]$$$ will in the last subsequence, otherwise it with redundant subsequences $$$[a,a\oplus x]$$$ will in the last subsequence.

So it's unnecessary to consider subsequence $$$[x]$$$.

Can somebody recommend problems similar to problem C ?

Click the tag and choose DP which is 1600 to 2000(rating,maybe higher than 2000).

Thanks but i need more specific recommendations based on personal experience not random problems :)

You could google this:linear dynamic programming in Codeforces.

Then you will find some tutorial that is helpful to you.

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.

Thanks for tutorial.

How to improve noob to pupil any topics I will study otherwise what should I do? Pls reply

Try to do CSES problem set Introductry and sorting and searching problem will help you in improving

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

Let's take some correct pair $$${a, x \oplus a }$$$, and suppose the numbers go into different sets $$$A$$$ and $$$B$$$ respectively. Then it's easy to see, that we can retrieve those numbers to form a pair set. So we convert $$$A$$$ and $$$B$$$ into $$${a, x \oplus a}$$$ and $$$A \cup B \setminus {a, x \oplus a}$$$ with both xor still equal to $$$x$$$. Now the pair is in its own set and the answer isn't smaller.

MikeMirzayanov, somehow the curly braces do not render correctly (or at all), please take a look.

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.

i dont understand the solution of D

when the game cannot end at first, we can only change the numbers on the circle

so why we should add

`ans += (n + s[n + 1])`

to the answer?

`s[n + 1]`

is the nodes that can end the game, but i dont understand why we add`n`

here.i understand it now :)

The

proofpart 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$$$)

$$$B$$$ is the highest bit which $$$x$$$'s is on. We only consider $$$a_i$$$ when $$$B$$$-th bit of $$$a_i$$$ is on, when $$$x=2=(10)_2$$$, $$$B=1$$$, $$$a_i=4=(100)_2$$$ so the $$$B$$$-th bit isn't on.

When $$$a_i$$$'s $$$B$$$-th bit is on, $$$a_i\oplus x$$$'s $$$B$$$-th bit is off, and their higher bits are equal, so we have $$$a_i\oplus x< a_i\le n$$$.

Thanks for your kind reply. get it.

Can you help me in problem E what about the case that number of subsequence parity from input is differ from the maximum subsequence that we found , we always can't construct it ?

In that case just consider the xor of all elements; the total xor value of the desired number of segments (each has an xor value of $$$x$$$) is different from the give array's xor value so there is no way to construct it.

Oh I got it thanks <3

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

Since we can get unique $$$p_i$$$ and $$$q_i$$$ (assuming $$$p_i \le q_i$$$ ) satisfying $$$p_i+q_i=a_i$$$ to make $$$F$$$ as small as possible, where $$$x_i=p_i, y_i=q_i$$$ or $$$x_i=q_i, y_i=p_i$$$. Assuming we let all $$$x_i=p_i$$$ and $$$y_i=q_i$$$, we still have the possibility to swap some values of $$$x_i$$$ and $$$y_i$$$ to make the value of $$$F$$$ is smaller.

Taking $$$n=5$$$ as an example, $$$F = a_1*x_2+y_2*x_3+y_3*x_4+y_4*a_5$$$.

We can let $$$x_2 = p_2$$$, so that we can determine $$$y_2 = q_2$$$, and similarly if we let $$$x_2 = q_2$$$ we can determine $$$y_2 = p_2$$$. Then we can let $$$a_1*x_2 + y_2*x_3$$$ take the minimum value if $$$x_2$$$ takes the value of $$$p_2$$$ or $$$q_2$$$ by deciding the value of $$$x_3=$$$ ($$$p_3$$$ or $$$q_3$$$), and at the same time the value of $$$y_3$$$ is determined. Next, the value of $$$x_4$$$ can be chosen as $$$p_4$$$ or $$$q_4$$$ so that $$$a_1*x_2+y_2*x_3+y_3*x_4$$$ takes the minimum value if the value of $$$x_3$$$ is $$$p_3$$$ or $$$q_3$$$. Finally we can use the minimum value of $$$a_1*x_2+y_2*x_3+y_3*x_4$$$ and the $$$x_4$$$ corresponding to its minimum value, and then $$$y_4$$$ is determined, and after calculating $$$y_4*a_5$$$ we get $$$F$$$. in other words to find the minimum value of $$$F$$$ in the cases $$$x_4=p_4$$$ and $$$x_4=q_4$$$, and this process can be done by DP.

It should be emphasized that we have been considering the minimum value of a part of equation $$$F$$$ in the case $$$x_i=p_i$$$ or $$$x_i=q_i$$$, and the current worse choice may be better later, so the greedy algorithm cannot be used.

191171920 The state in this code preserves the specific values of $$$x_i$$$ and $$$y_i$$$, which may be easier to understand compared to using 0/1.

In problem C, can you 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 transitions seem correct to me logically.

To avoid confusion, I still use $$$p_i$$$ and $$$q_i$$$ to explain. f[i][0] can be considered as choosing $$$p_i$$$ to compute, and f[i][1] can be considered as choosing $$$q_i$$$ to compute. Then, as you can see from the process shown earlier, assuming that you currently choose $$$p_i$$$, then the next product will already have a number determined to be $$$q_i$$$. So for $$$F[i-1][0]+x[i-1]*x[i]$$$, F[i-1][0] has already determined one of the numbers in the next product to be y[i-1] instead of x[i-1].

thank you! I understand it now.

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.

equal to 0 is allowed

This 191151252 got accepted in which values of (x,y) is (2,3) for

Testcaseoutput:

`3*4 + 2*6 = 24`

using 2,3 would give (2-3)*(3-3) which is equal to 0 and it satisfies the given condition (xi−s)⋅(yi−s)≥0

Thanks

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,

to this transition,

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

They are just different. For each $$$i$$$ we have $$$x_i$$$ and $$$y_i$$$, one of them multiply by last number and another by next one.

As an example, for $$$f_{i-1,0}$$$ we used $$$x_{i-1}$$$, then $$$y_{i-1}$$$ is left, so for $$$f_{i,0}$$$ we should use $$$y_{i-1}$$$ and $$$x_i$$$ then the formula is $$$f_{i,0}=f_{i-1,0}+y_{i-1}*x_i$$$.

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.

can someone give more intuition on how to get to logic in problem C

Also, can someone suggest me how to get to specialist quickly. I have been around for a while but been on and off all the time.

When will the plagiarism check run?

1787-C, Remove bracketswas 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.

You find m — 1 subsequences, and the rest becomes the m-th

The rest does not xor to $$$x$$$ so cannot form a valid subsequence.

But it should. If it doesn't then there's no way to form m valid subsequences. It is provable

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

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

Agree. Usually I only read the English tutorial and then implement my own solution.

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+????

Oh i see

Could you help me see too?

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

Yes

Of course, you may also use stack without recursion.

Well, yes. But then its not like a given solution for the problem. The question is, how to use recursion in Python properly?

So the problem with smt like

`sys.setrecursionlimit(200005)`

is, that it apperently reserves a lot of memoryYou may follow the link. It works, I think.

It appears i misunderstood your statement. Thanks:)), it really helped indeed.

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

Take a look at Ticket 16851 from

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