When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

rsj's blog

By rsj, history, 14 months ago, In English

1787A - Exponential Equation

Idea & Solution: rsj

Tutorial

1787B - Number Factorization

Idea & Solution: rsj

Tutorial
Solution

1787C - Remove the Bracket

Idea & Solution: rsj

Fact
Tutorial
Solution

1787D - Game on Axis

Idea & Solution: jiangtaizhe001

Tutorial
Solution

1787E - The Harmonization of XOR

Idea & Solution: jiangtaizhe001, rsj

Tutorial
Bonus Problem

1787F - Inverse Transformation

Idea & Solution: qzhwlzy, rsj

Tutorial
Solution

1787G - Colorful Tree Again

Idea & Solution: rsj, 275307894a

Tutorial

1787H - Codeforces Scoreboard

Idea & Solution: jiangtaizhe001, rsj

Something To Say
Tutorial

1787I - Treasure Hunt

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!

  • Vote: I like it
  • +216
  • Vote: I do not like it

| Write comment?
»
14 months ago, # |
  Vote: I like it +23 Vote: I do not like it

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

»
14 months ago, # |
Rev. 2   Vote: I like it -23 Vote: I do not like it

.

»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    14 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      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.

      • »
        »
        »
        »
        14 months ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        you could bruteforce it using binary search 191169657

        • »
          »
          »
          »
          »
          14 months ago, # ^ |
            Vote: I like it -8 Vote: I do not like it

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

          • »
            »
            »
            »
            »
            »
            14 months ago, # ^ |
            Rev. 3   Vote: I like it 0 Vote: I do not like it

            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

            • »
              »
              »
              »
              »
              »
              »
              14 months ago, # ^ |
              Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
14 months ago, # |
  Vote: I like it +37 Vote: I do not like it

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.

  • »
    »
    14 months ago, # ^ |
    Rev. 2   Vote: I like it +10 Vote: I do not like it

    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...

    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it +18 Vote: I do not like it

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

  • »
    »
    14 months ago, # ^ |
      Vote: I like it +45 Vote: I do not like it

    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 >:).

»
14 months ago, # |
Rev. 3   Vote: I like it +41 Vote: I do not like it

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.

  • »
    »
    14 months ago, # ^ |
      Vote: I like it +29 Vote: I do not like it

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

    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

  • »
    »
    14 months ago, # ^ |
      Vote: I like it +46 Vote: I do not like it

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

»
14 months ago, # |
Rev. 2   Vote: I like it +30 Vote: I do not like it

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

»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    14 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    click show test details at the bottom

  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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).

»
14 months ago, # |
  Vote: I like it -11 Vote: I do not like it

Thanks for the well written editorial

»
14 months ago, # |
  Vote: I like it +8 Vote: I do not like it

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

  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You spend exactly one minute to solve each problem

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

  • »
    »
    14 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    • See this. Nevertheless, I am really impressed that it has taken only 14 minutes to read enough problems to find H (and notice something familiar) and then code it.
»
14 months ago, # |
  Vote: I like it +28 Vote: I do not like it
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
14 months ago, # |
  Vote: I like it +43 Vote: I do not like it

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).

»
14 months ago, # |
  Vote: I like it +10 Vote: I do not like it

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

Did anyone else do that? :P

»
14 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Real math forces

»
14 months ago, # |
  Vote: I like it +26 Vote: I do not like it

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?

  • »
    »
    14 months ago, # ^ |
    Rev. 5   Vote: I like it +34 Vote: I do not like it

    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]$$$.

»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can somebody recommend problems similar to problem C ?

  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      14 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
14 months ago, # |
  Vote: I like it +6 Vote: I do not like it

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

»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
14 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    14 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    $$$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$$$.

    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks for your kind reply. get it.

    • »
      »
      »
      14 months ago, # ^ |
      Rev. 2   Vote: I like it +3 Vote: I do not like 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 ?

      • »
        »
        »
        »
        14 months ago, # ^ |
          Vote: I like it +3 Vote: I do not like 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.

»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    14 months ago, # ^ |
    Rev. 3   Vote: I like it +1 Vote: I do not like it

    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.

    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        14 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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].

»
14 months ago, # |
  Vote: I like it +8 Vote: I do not like it

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

»
14 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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

»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    equal to 0 is allowed

    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      Testcase
      • »
        »
        »
        »
        14 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        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

»
14 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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$$$.

»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Who is the Problem Authors ?

»
14 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

»
14 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
14 months ago, # |
  Vote: I like it +77 Vote: I do not like it

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.

»
14 months ago, # |
  Vote: I like it +6 Vote: I do not like it

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

»
14 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        14 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

»
14 months ago, # |
Rev. 2   Vote: I like it +14 Vote: I do not like it

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

  • »
    »
    14 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

»
14 months ago, # |
  Vote: I like it +1 Vote: I do not like it

what is approximate difficulty of problem D?

»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    13 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Yes

    Of course, you may also use stack without recursion.

    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        13 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        So the problem with smt like sys.setrecursionlimit(200005) is, that it apperently reserves a lot of memory

        • »
          »
          »
          »
          »
          13 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          You may follow the link. It works, I think.

          • »
            »
            »
            »
            »
            »
            13 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

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

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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