Cirno_9baka's blog

CodeTON Round 2 Editorial
By Cirno_9baka, history, 2 years ago, In English
Tutorial is loading...
solution
Tutorial is loading...
solution
Tutorial is loading...
solution
Tutorial is loading...
solution
Tutorial is loading...
solution
Tutorial is loading...
solution
Tutorial is loading...
solution
Tutorial is loading...
solution
Tutorial is loading...
solution
  • Vote: I like it
  • +218
  • Vote: I do not like it

Comments Comments (81)
| Write comment?
»
2 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Auto comment: topic has been updated by Cirno_9baka (previous revision, new revision, compare).

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    I love this editorial, please put it on the contest materials under the "CodeTON Round 2 (en)" like other contests, so more people can read it.

    → Reply
»
2 years ago, # |
  Vote: I like it +46 Vote: I do not like it

The observations in D and E are quite amazing. During the contest I tried to solve D by finding some constants. I tried something for odd indices and even indices, but didn't come up with this. Can anyone tell me that are there any good ways to find such constants?

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    I also thought about odd/even indices first, and then I rememberd that we should also count the number of operations so I was thinking something like — What is one operation of the second type changing so we can count even the number of them ?

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      So for this problem, there are 2 key entry points.

      1. Instead of something doesn't change, we need to find sth that can distinguish 2 operations.

      2. Count the number of the operation is a hint.

      Did I get your ideas right?

      → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        Yes, you are right.

        → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    Xd I tried with parity also but it didn't work out. Actually thinking about prefix sums is more natural for me because "subtract 1 from a[i] and add 1 to a[i — 1]" actually increases the sum of prefix sums by 1. Similarly for other operations and thus you can find the unique array.

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Actually I am curious about how you came up with sum of the prefix sum. Is this some kind of experience?

      → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Was it the right approach??? Argh... I thought about it, but can't come up with any idea how to use it this case D:

        → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it +6 Vote: I do not like it

        Initially I only want to see if prefix sums will produce any patterns. And for operation 1 prefix sums will be like +1, -1; while for operation 2 it is +1, -2.

        → Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 3   Vote: I like it +268 Vote: I do not like it

    For problem D, you may perceive it as you have some particles, and you pick a pair of them and move outwards simultaneously. When thinking about just 2 particles, you easily notice that in first case, their center of mass (middle position) stays the same, while in second case it moves by exactly 0.5 to the right.

    Then, you see that this also works for mean position of all particles -- in first case it stays the same, in second case it moves to the right by 1/n.

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +15 Vote: I do not like it

      Wow, this idea is pretty straightforward for me. Thanks a lot.

      → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Really amazing intuition!

      → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Where can I find more such problems (based on center of mass)?

      → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Amazing idea!!

      → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Actually, there are a lot of cool interpretations of algorithms using physics (for instance watch this part of the video: https://youtu.be/cs8GuOg16_M?t=100 )

      → Reply
      • »
        »
        »
        »
        22 months ago, # ^ |
        ← Rev. 5   Vote: I like it 0 Vote: I do not like it

        Amazing!! Blow my mind. Thanks for sharing. I like the Dijkstra proof. I never thought that physics can also be used in problem-solving. Are there more good resources like this share it? I search on the web but can't find anything related to it.

        → Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    For problem E, my reasoning is a bit different than in the editorial.

    We may model the problem with some marbles moving along the DAG arcs, one marble from each node through all outgoing arcs at a time. Let's group marbles that pass through the node based on the length of the path they previously traversed to get to the node. For some marbles, the length is $$$0$$$ (they were in the node from the start), for some it's $$$1$$$ and so on.

    To make keeping track of them easier, let's say that first we will push down all marbles that traversed the length $$$0$$$, then all marbles that traversed the length $$$1$$$, and so on. We may prove that in this way, there never will be a node with a marble in it which didn't push it down, so the model is correct.

    Now, let $$$c_0, c_1, \dots, c_{n-1}$$$ be the number of marbles that will go through the sink and that will traverse the length of $$$0, 1, \dots, {n-1}$$$ before arriving to it. And let $$$t_0, t_1, \dots, t_{n-1}$$$ be the time at which the last marble in that group can be pushed down. Then the answer to the problem is $$$t_k$$$, where $$$k$$$ is the largest such that $$$c_k \neq 0$$$ and

    $$$ t_k = \max(t_{k-1}, k) + c_k, $$$

    as you will start pushing down marbles of group $$$k$$$ in the moment $$$\max(t_{k-1}, k)$$$ and will do so continuously until all of them are pushed. This seem to lead to $$$O(nm)$$$ solution rather than $$$O(n^2)$$$, though.

    → Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    For D: I think a nice way to motivate this solution is not to figure out what doesn't change but rather to find aspects of the operations that can then be used to find properties of these invariants. For example, in all the operations except for the special operation, the operations can be done on reversed versions of those arrays in the exact same way. This motivates finding constants that do not change when reversing the array. For example the sum of "distances" from the left and right ends of the array. Notice this only works because of this property of normal operations whereas it does not work when analyzing special operations.

    → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    There's a book, "Problem Solving Strategies Arthur Engel", where such observations known as "invariants" are discussed in detail, alongwith many cool problems. You can try it out :)

    → Reply
»
2 years ago, # |
  Vote: I like it +8 Vote: I do not like it

I don't quite get the solution for D, like where do the equations come from?

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it -68 Vote: I do not like it

    Dumb solution in editorial. Just look at how array of prefix sums changes after operations.

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      I actually think this is a more natural solution than looking at the prefix sums. See also this comment thread. Also if you build the sum of prefix- (or more precise suffix-) sums you also get just this formula.

      → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        I finally understand it, this is a pretty interesting problem. Had to debug and mess around to finally figure it out. The equations get too confusing for me, and a natural solution makes a lot more sense.

        → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for fast editorial.

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the fast editorial and the great round. Gonna be BLUE today!!

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Lost blue today :/ (again) In fact, I'm down to the exact rating you had before this round. How things change...

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Sad may you compensate your loss bro, since being a specialist u can do tomorrow's div3 , You will surely ace it , Good luck!

      → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        Thanks! But unfortunately tomorrow is actually my first day back at school and the contests happen during school hours (11h30am — I'm Brazilian). Quite unlucky of me

        Edit: I only have math at the time of the contest, I'm tempted to skip, we'll see...

        → Reply
        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          yeah. Mine is in 1 more week. When school starts, I also won't be able to take as many contests.

          → Reply
»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Even though I wasn't able to solve D, I respect the problem.

→ Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    Have you understood the solution yet? I have not :( edit: figured it out from above comment :)

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why there is an indentation in problem $$$F$$$ solution in line ans ^= f[j — i]? I was a little confused.

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think implementation for C isn't explained enough, and the tutorial is just a simplification of a problem.

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    jiangly's submission is much clearer to me

    → Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Alternate solution for D. Find the sums of the prefix sums of each array. The special array will be different than the rest of them and the difference between the sum of the special array and the sum of a non-special array will be the amount of operations.

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Sum of the prefix sums is equals to $$$\sum (n - i + 1) \cdot a_i = (n + 1) \sum a_i - \sum(i \cdot a_i)$$$

    Since $$$(n + 1) \sum a_i$$$ is the same for all the arrays of a sample, this is equivalent to $$$\sum(i \cdot a_i)$$$, the solution proposed by the editorial

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      I guess you are right. I think my logic was a bit different. I noticed that the prefix sums can help tell you the difference between a particle moving 1 or 2 to the right.

      Original: 1 0 0

      Move 1 right: 0 1 0

      Psum of 1 right: 0 1 1

      Move 2 right: 0 0 1

      Psum of 2 right: 0 0 1

      The psum of 1 right has one extra 1 which gave me the idea to subtract the sums of the psums to find the number of operations.

      → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is Chinese remainder theorem an alternative solution to problem E?

The idea is to simulate first n seconds of the algorithm and then in topological order simulate similar proces: instead of reducing original node by 1 and adding 1 to the following nodes we reduce orignial node down to zero and increase the value of following nodes by value of original. (So if there are edges: 1->2, 1->3, 2->3, and the values are 8, 5, 10 then after one step of 2nd process values will be 0, 13, 18 and after another step values will be 0, 0, 31.)

Since the values can be large we remember them modulo 2 numbers.

My Submission

My solution alternatively simulates 1st and 2nd process but this is effectively the same. Since my modulos are not random I guess it wouldn't be hard to hack the solution, however I don't know if there exists a test case which fails with high probablity for two random modulos.

Unfortunatly I forgot the corner case where solution is less than n during the contest. :(

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    Do you really need chinese remainder theorem ? You obviously don't need it for 1st process (values are low) and for the 2nd process I think you only need to know the values MOD 998244353, if I understood your solution.

    (I think we pretty much have the same solution (I only read your comment, not your code) but I don't use it)

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I overcomplicated my implementation a lot apparently. CRT is not necessary for either process individualy, but my solution alternated between simulating first and second process so I needed another modulo. So yeah, it doesn't need CRT I'm just overcomplicating it.

      → Reply
»
2 years ago, # |
  Vote: I like it +190 Vote: I do not like it

Am I the only one who thinks F is stupid ? (beautiful in a way, but stupid nonetheless)

I reduced the problem to calculating the Sprague-Grundy function, and tried to come up with a clever way to calculate it fast. I even calculated many values to try to spot a pattern, but how in the hell are you supposed to guess that there is a cyclic section of length 34 ? (the fact that this is except the first few elements makes it even more absurd) If you didn't knew it already or luckily found it on OEIS that is, in which case you have my special congratulations.

Anyway this is just my salty comment, don't take it too seriously, but the solution (and thus the problem too) doesn't feel very satisfying to me.

→ Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 2   Vote: I like it +58 Vote: I do not like it

    My thought process for this (sadly I didn't manage to finish this until after the end of the contest):

    • How big are the Grundy values? Maybe I can use their smallness to effectively calculate them?
    • Why are they all $$$\le 9$$$? How come 9 is reached in the first 100 values and it doesn't go above even at $$$5 \cdot 10^5$$$?
    • Maybe the sequence is cyclic?

    I do say that it is a bit frustrating that there seems to be no way to "see" that the array is cyclic without actually generating it and testing for it.

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +20 Vote: I do not like it

      I actually never realized it was cyclic. I also calculated the first like 10000 values and noticed that they are less than 10, even though 9 appears very early. Then I thought that we don't need to check too many splits (moves) to find all possible grundy values. One natural way to do it is to limit the size of one of the parts after split, so instead of

      $$$SG(n)=mex_{i=0}^{n-2i}SG(i) \oplus SG(n-2-i)$$$

      i tried assuming

      $$$SG(n)=mex_{i=0}^{min(n-2i,1000)}SG(i) \oplus SG(n-2-i)$$$

      To check if it works I locally calculated all Grundy values properly and verified that they are the same. The calculations only took about 1 or 2 minutes.

      → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it +20 Vote: I do not like it

        I tried to do the same but with sampling a random subset instead of going up to 1000. Sadly that quickly fails (which is weird actually) and I didn't think going to 1000 instead would be any different.

        → Reply
        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I guess it's not that weird now, it just means that you require one of the unique precycle values for correct grundy value at some point, so the number 17 or 51 (or whatever those unique numbers are) has to be in your random subset for this to work.

          → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    My thought process (after reducing this problem to finding SG values):

    First, I used pencil and paper to calculate $$$n\leq 8$$$, but found nothing. Then I used my computer to calculate $$$n\leq 100$$$, but still found nothing, thinking how in the world is this problem solvable.

    Then I calculated further to $$$n\leq 1000$$$, found that the largest SG value is still $$$9$$$, and that the SG values around these $$$9$$$s are the same, so I decided to print all $$$n$$$ such that the SG value is $$$9$$$, found that the differences between adjacent $$$9$$$s are all $$$34$$$.

    I got a conclusion that maybe the SG values are cyclic after a certain point. I verified this, and I started writing the solution.

    I agree that this problem is quite weird, because there is no way to spot the solution other that writing brute force.

    → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    I once organized a local contest where this game was involved. Everyone was aware that the game is solvable in $$$O(1)$$$, but we had a consensus that increasing the limit will only worsen the problem quality, hence we sticked to $$$N \le 5000$$$.

    After that, I saw this same game several times again. I kinda ended up memorizing the number 34, so it's not hard for me now.

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

May the variable val in D's solution overflow?

→ Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    ignore this.

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Does problem D have $$$mod$$$?

      → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        problem D guaranteed that everything will not exceed $$$10^{18}$$$.

        → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It is guaranteed that each element of the discarded array $$$b$$$ is in the range $$$[0,10^6]$$$.

    The value of $$$i \cdot b_i$$$ never changes when performing operation 1, and it increases by $$$1$$$ only when performing operation 2. Number of operation 2 performed $$$\le 10^{18}$$$.

    So, for all $$$i$$$ ($$$1 \le i \le n$$$), sum of $$$j \cdot c_{i,j} \le 10^{18} + 10^6 \cdot \frac{n(n+1)}{2}$$$

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Uh thanks, but I want to know how to prove that operation 2 can be performed $$$\le 10^{18}$$$

      → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        er it's written in the output section of the statement

        → Reply
        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

          it also write "It can be shown that ... won't exceed 10^{18}" and I don't know how to show

          → Reply
»
2 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Yeah, nice observation on $$$34^2$$$ numbers, feeling ashamed that I don't have the sight.

→ Reply
»
2 years ago, # |
  Vote: I like it +27 Vote: I do not like it

Who keeps putting "constructive algorithms" tag on DEF? In what sense are they "constructive"?

→ Reply
»
2 years ago, # |
← Rev. 3   Vote: I like it +4 Vote: I do not like it

I have a different way to solve D.

I first suppose array $$$c[1]$$$ to be the normal array. Then I do the following thing every other array $$$c[a]$$$:

  cnt:=0
  for i in range [1,n]:
    cnt+=(c[a][i]-c[1][i]),c[a][i+1]+=(c[a][i]-c[1][i]),c[a][i]=c[1][i].

If another array is a normal array too, then because one normal array must can be generated by using the operation (c[1][i-1]++,c[1][i]--,c[1][j]--,c[1][j+1]++) to array $$$c[1]$$$ and it can be divided in to two operations $$$f_{i-1}$$$ and $$$-f_j$$$ that $$$f_i:c[1][i]++,c[1][i+1]--$$$.

If another array is a special array, then $$$|cnt|$$$ is the least time to do operation 2. Because the difference between $$$op1$$$ and $$$op2$$$ is (c[1][j+1]--,c[1][j+2]++) and it is just $$$-f_{j+1}$$$. We use this operation for $$$|cnt|$$$ times and it's ok to generate the special array.

But what if array $$$1$$$ is the special array? If so, then in all $$$[2,n]$$$, there is equal $$$cnt$$$ s.

I think my method is simpler than the std.

166368251

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    oh, a nice solution!

    → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I used the exactly same way to solve D. However, for me this is more complicated than std since this solution have much to be proved.

    Like, why two non-special arrays can always become the same with |cnt|==0 in this greedy manner and why the |cnt| for special array is really exactly (c[1][j+1]--,c[1][j+2]++).

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Why two non-special arrays can always become the same with $$$|cnt|==0$$$ in this greedy manner:

      Prove: First, Let's clarify that $$$cnt$$$ calculates the times we do positive $$$f_i$$$ more than negative $$$-f_i$$$.

      Second, we prove why |cnt| always becomes 0 for a normal array. Consider $$$op1$$$. It always does $$$f_{i-1}$$$ and $$$-f_j$$$ in a time, so the times we do positive $$$f_i$$$ is always equal to the times we do negative $$$-f_i$$$. Because there are balanced times to do $$$f$$$(shorter form below: times) from the original array to array $$$1$$$(a supposed normal array) and another array, and the option $$$f$$$ s are reversible, so there are always balanced times from array $$$1$$$ to the original array(equals to the times from the original to array $$$1$$$) and always balanced times from the original array, so there are always balanced times to turn array $$$1$$$ to any other normal arrays.

      Third, why it is optimal to use exactly $$$|cnt|$$$ $$$op2$$$ s to turn the original array to the special array. I have mentioned that the times from array $$$1$$$ to the special array is equal to $$$cnt$$$. Let $$$cnt'$$$ be the times from the original array to the special array, and $$$cnt"$$$ be the times from the original array to array $$$1$$$. Obviously there is $$$cnt'=cnt"+cnt$$$. So $$$cnt' \ge cnt$$$. If we set the array $$$1$$$ as the original array, then we get an optimal $$$cnt'$$$ because $$$cnt"=0$$$ and $$$cnt'=cnt$$$. So, the options we do to make it optimal is exactly $$$cnt$$$.

      Q.E.D.

      → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thanks for your reply but that's not what I mean. In fact I have understood all you said, otherwise I couldn't come up with this solution during the contest xD

        By greedy manner, I mean that in fact we just scan the two arrays from left to right and apply simple (-1,+1) or (+1,-1) many times and that's not directly equivalent to original operation 1 (which do (-1,+1), (+1,-1) simultaneously) so there need some proof. And same (maybe even more) for operation 2.

        → Reply
        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          There are only one special array and the statement guaranteed that there are more than $$$1$$$ $$$op2$$$ s. And using $$$cnt'=cnt$$$ we know that it must be the only one which have $$$cnt \neq 0$$$. And it is enough for us to find the special array.

          Surely, the options to turn array $$$1$$$ to another array isn't equivalent to original option. But the problem doesn't means there is a fixed original array and we have to find the exact options, but a valid array that makes $$$op2$$$ as small as possible. And I have proved that we can construct a method with $$$|cnt|$$$ options and there is no other method with less than $$$|cnt|$$$ options.

          So we have found the special array and the smallest option times, isn't it enough?

          → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem D: This center of mass concept is new to me. Can anyone point out to more such problems? What tag should I search the problem set with?

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem E, can someone explain what dp and sum is? I am unable to understand from editorial

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The problem was very interesting ty for the contest + D make me cry but after the tutorial the observation is quite good

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why greedy for B is correct to use?

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Note that when $$$v$$$ changes, it can change to any integer as desired, so whatever happened in the past has no bearing on the new value of $$$v$$$. Therefore, a choice that requires an earlier change of $$$v$$$ cannot be better than a choice that requires a later change of $$$v$$$.

    If you want a more technical proof, consider two possibilities: one in which the first change happens at position $$$i$$$, and another in which the first change happens at position $$$j$$$, where $$$i < j$$$. Suppose for option 1, the value of $$$v$$$ at position $$$j$$$ is $$$v_1$$$. Then construct a third option where you follow option 2 until position $$$j$$$, then change $$$v$$$ to $$$v_1$$$ and follow option 1. This can never be worse than option 1, since all changes after $$$j$$$ are the same between options 1 an 3, whereas option 3 has exactly one change in the interval $$$[1, j]$$$ (specifically at $$$j$$$ itself) while option 1 needed at least one change in the same interval (there is a change at $$$i$$$, and there could be more). Therefore, at each instant where you need to choose $$$v$$$, there will always exist an optimal solution (from that point on) in which the chosen value of $$$v$$$ lasts the longest.

    Basically, there is no disadvantage to trying to pick a value of $$$v$$$ that lasts longer (should hopefully be clear intuitively, if you don't wanna bother with a formal proof), since each change is a reset that doesn't care about the previous choice at all.

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      "Note that when v changes, it can change to any integer as desired, so whatever happened in the past has no bearing on the new value of v. Therefore, a choice that requires an earlier change of v cannot be better than a choice that requires a later change of v."

      It's true, but if you take the random element for v which satisfies for the first and not satisfy some next elements, it's not optimal because if you can take the first v which satisfy for the first and some next elements it's better than first variant because in second case we can use changes less than first variant.

      → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        That's pretty much what I was saying. For example, if one choice of v works for the first three elements, whereas another choice of v works for the first five elements, then the first choice will not have any advantage when compared to the second choice. If an optimal solution exists with the first choice, then an optimal solution must also exist with the second choice instead. Therefore, if we keep choosing the v that covers the maximum number of elements, we will get an optimal solution.

        → Reply
»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

For problem E, sink point refers to the node with no out edges Hint from somebody who spent almost ten minutes figuring that out

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Duliu round :(

(Duliu means very difficult in Chinese)

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Maybe cancerous is a better translation of 毒瘤(dúliú)? The metaphorical meaning of a cancer is something harmful to the society, and cancerous means the problem is like a cancer.

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I see. I didn't know how to express this in English before. Thanks.

      → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I had a little bit different ideas(actually, the same as in editorial, but under a different angle).

Problem D: Let's take a look a prefix sums $$$P_i = b_1 + \ldots + b_i$$$. Then first operation just adds $$$1$$$ to some $$$i$$$ and subtracts $$$1$$$ from some $$$j$$$ from $$$P$$$, $$$1 \leqslant i < j - 1$$$. But second operation adds $$$1$$$ to one index of $$$P$$$ and subtracts $$$1$$$ from two indices. So first operation does not change sum of prefix sums, and second just decreases it by $$$1$$$. From here it is obvious how to solve this problem in $$$O(nm)$$$ time, even if $$$n = 2$$$.

Remark. $$$\sum a_i \times i$$$ is sum of prefix sums, but I think problem become less more bloated and strange while looking at prefix sums as all these strange operations become more natural and convenient.

Problem E: Suppose we have topologically sorted graph $$$G$$$ with $$$n$$$ vertices, and process on him halts in $$$T$$$ seconds. Let's do one iteration ONLY FOR VERTICES EXCEPT FIRST, and then add $$$a_1$$$ to all $$$a_v$$$, where $$$1 \to v$$$. We got a new graph $$$G^\prime$$$ with, in fact, $$$n - 1$$$ vertices, because first is empty. One can see, that on $$$G^\prime$$$ process halts in $$$T - 1$$$ seconds.

It is like equivalent graph(since halt time is almost same), but with less vertices.

So the solution is following: do $$$n - 1$$$ steps, on $$$i$$$-th if all vertices are empty, output $$$i$$$ and return, otherwise do one iteration for vertices $$$i + 1, \ldots, n$$$, and add $$$a_i$$$ to all $$$a_j$$$, such that $$$i \to j$$$. After all steps we'll get graph with one non-empty vertex($$$a_n$$$), so output $$$n - 1 + a_n$$$.

Each step is done in $$$O(n + m)$$$ time, so total complexity is $$$O(n(n + m))$$$.

There is a tricky moment: how can we compare integer to zero, if we work modulo $$$M$$$? Let's mark number big, if we added number, which was marked big before, or there're were overflow (we got something, greater than $$$M$$$ while added two numbers). By induction you can prove, that if $$$a_v$$$ is marked big on $$$i$$$-th step, then it's greater, than $$$M - i$$$, and since $$$M \gg n$$$, $$$a_i = 0$$$ if and only if it is not big and $$$a_i \equiv 0 \pmod M$$$.

It may seem difficult, so you can just check submission 167203576 for details.

→ Reply
»
2 years ago, # |
  Vote: I like it +10 Vote: I do not like it

In H2, "Newton's method" is the usual trick for doubling the number of coefficients? I'm only familiar with the name for the iterative numerical method for finding roots etc starting from a correct fixed number.

Anyway, I have a different solution that starts from the observation in H1. For each set of $$$c_2$$$ labeled paths with length $$$\ge 2$$$ and $$$c_1$$$ with length $$$1$$$, we have a weight $$$(n-1)^{c_2} (n-c_1-c_2)^{c_1} / c_1! c_2!$$$, and we need to sum up all weights.

The number of ways to split $$$c_1+c_2+k$$$ vertices into paths with fixed lengths is $$$(c_1+c_2+k)!$$$. Therefore, for fixed $$$c_1$$$ and $$$c_2$$$, we can make a generating function for the number of ways to choose paths on $$$n$$$ vertices divided by $$$n!$$$: $$$(x^2+x^3+\ldots)^{c_2} x^{c_1} = \frac{x^{c_1+2c_2}}{(1-x)^{c_2}}$$$. Dividing by $$$x^{c_1+c_2}$$$, the coefficient of $$$x^k$$$ corresponds to $$$n=c_1+c_2+k$$$, so we can apply the operator $$$O = x \delta_x$$$ to express the g.f.

$$$\sum a_i x^i = \sum_{c_1,c_2} (n-1)^{c_2} \frac{1}{c_1!} \frac{1}{c_2!} x^{c_1+c_2} O^{c_1} \frac{x^{c_2}}{(1-x)^{c_2}} \,,$$$

where the answer for $$$n$$$ is just $$$a_n n!$$$.

It's known that $$$O^c x/(1-x) = x A_c(x) / (1-x)^{c+1}$$$, where $$$A_c(x)$$$ is the $$$c$$$-th Eulerian polynomial; since $$$O$$$ satisfies the chain rule, $$$O^c (x/(1-x))^b = c! [y^c] \left(\sum_{i=0}^{\inf} \frac{x A_i(x)}{(1-x)^{i+1}} \frac{y^i}{i!} \right)^b$$$, where $$$[y^c]$$$ is the operator extracting the coefficient of $$$y^c$$$. We simplify that to $$$c! x^b (1-x)^{-b-c} [y^c] \left(\sum_{i=0}^{\inf} \frac{A_i(x)}{i!} y^i \right)^b$$$, apply the definition of e.g.f. of Eulerian polynomials and get $$$c! x^b (1-x)^{-c} [y^c] \left(e^{(x-1)y}-x\right)^{-b}$$$. Now we need to plug it back with $$$b=c_2$$$ and $$$c=c_1$$$:

$$$\sum a_i x^i = \sum_{c_1,c_2} (n-1)^{c_2} x^{2c_2} \frac{1}{c_2!} \frac{x^c_1}{(1-x)^{c_1}} [y^c_1] \left(e^{(x-1)y}-x\right)^{-c_2} = \sum_{c_2} \frac{1}{c_2!} \left(\frac{x^2(n-1)}{e^{-x}-x}\right)^{c_2} = \exp\left(\frac{x^2(n-1)}{e^{-x}-x}\right) \,,$$$

where we used $$$y=x/(1-x)$$$. Since $$$n$$$ is involved on the right hand side, this isn't a g.f. from which we can extract all answers! Instead, we need something like $$$\sum c_n x^n [w^n] \exp\left(\frac{w^2(n-1)}{e^{-w}-w}\right)$$$; note that the exact multipliers $$$c_n$$$ aren't important as long as they're known.

At this point, we can notice a similarity with Lagrange-Burmann inversion formula: if $$$f(x) = x g(f(x))$$$ and $$$f(0) = 0$$$, then $$$f(x) = \sum x^n \frac{1}{n} [w^{n-1}] g^n(w)$$$. If we used $$$g(w) = e^{a(w)}$$$, where $$$a(w) = \frac{w^2}{e^{-w}-w}$$$, this would give $$$f(x) = \sum x^n \frac{1}{n} [w^{n-1}] e^{a(w)n}$$$ where $$$f(x) e^{-a(f(x))} = x$$$.

We'll need a more general version of this formula: $$$H(f(x)) = \sum x^n \frac{1}{n} [w^{n-1}] H'(w) g^n(w)$$$. For example, if we pick $$$H = g$$$, then $$$g(f(x)) = f(x)/x = \sum x^n \frac{1}{n(n+1)} [w^n] g^{n+1}(w)$$$. Let's use the fact that $$$g$$$ is an exponential here, and pick something very similar: $$$H(w) = 1/g(w) = e^{-a(w)}$$$. Then $$$H' = - H a'$$$ and

$$$H(f(x)) = 1/g(f(x)) = x/f(x) = - \sum x^n \frac{1}{n} [w^{n-1}] e^{a(w)(n-1)} a'(w) = - \sum x^n \frac{1}{n(n-1)} [w^n] e^{a(w)(n-1)} \,.$$$

We need to find $f(x)$ satisfying $$$f(x) e^{-a(f(x))} = x$$$, take the coefficients of $$$(f(x)/x)^{-1}$$$, multiply them by $$$-(n-1) n!$$$ and we have the answers.

Finding inverse function from $$$x = g(f(x))$$$ can be done here by starting with $$$f(0) = 0$$$, $$$f(1) = 1$$$ (from expansion of exponential, since $$$a(x) = 0$$$ modulo $$$x^2$$$) and gradually doubling the number of Taylor series coefficients we know. If we know $$$f_L = \sum_{i=0}^{n-1} f_i x^i$$$ where $$$n$$$ is a power of $$$2$$$, then modulo $$$x^{2n}$$$, we have

$$$x = g(f_L + x^n f_R) = g(f_L) + g'(f_L) x^n f_R \quad \rightarrow \quad x^n f_R = (x - g(f_L)) (g')^{-1}(f_L) \,,$$$

which in this case is

$$$f_R = \left(x - f_L e^{-a(f_L)}\right) e^{a(f_L)} \left(1 - \frac{f_L^2 (2e^{-f_L} + f_L e^{-f_L} - f_L)}{(e^{-f_L} - f_L)^2} \right)^{-1}$$$

and we're taking this modulo $x^{2n}$. Inverting a power series with 0-coefficient equal to $$$1$$$ is known and so is taking the exponential of a power series with 0-coefficient equal to $$$0$$$, so this formula seems scary, but it's just a lot of library operations. Since we're always doubling lengths, the time complexity is the same as an FFT with length $$$O(N)$$$, i.e. $$$O(N \log N)$$$.

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

for problem G, there is a solution which does not need fft! if you consider A[i] = a[i]+2*a[i+1]+a[i+2] and B[i] similar as A[i], then each operation does not change A[i] exept choosing a[i+2] wich increase A[i] by 1; so afterall operations each A[i] has increased atmost by 1 unit! so A[i] can be matched to B[i] if and only if 0<=B[i]-A[i]<=1 and we can find all the possible subsegments by bitset!(I do not know there is a better way please inform me if we have one) and also we should check can we transform a[i] to b[i] and a[i+1]to b[i+1] but this is not a problem and it is EZ and can be done in O(1) 172415521

→ Reply