### Cirno_9baka's blog

By Cirno_9baka, history, 11 days ago,
solution
solution
solution
solution
solution
solution
solution
solution
solution

• +218

 » 11 days ago, # |   +8 Auto comment: topic has been updated by Cirno_9baka (previous revision, new revision, compare).
•  » » 10 days ago, # ^ |   +20 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.
 » 11 days ago, # |   +46 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?
•  » » 11 days ago, # ^ |   +9 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 ?
•  » » » 11 days ago, # ^ |   +1 So for this problem, there are 2 key entry points. Instead of something doesn't change, we need to find sth that can distinguish 2 operations. Count the number of the operation is a hint. Did I get your ideas right?
•  » » » » 11 days ago, # ^ |   +1 Yes, you are right.
•  » » 11 days ago, # ^ |   +16 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.
•  » » » 11 days ago, # ^ |   +5 Actually I am curious about how you came up with sum of the prefix sum. Is this some kind of experience?
•  » » » » 11 days ago, # ^ |   0 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:
•  » » » » 11 days ago, # ^ |   +6 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.
•  » » 11 days ago, # ^ | ← Rev. 3 →   +268 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.
•  » » » 11 days ago, # ^ |   +15 Wow, this idea is pretty straightforward for me. Thanks a lot.
•  » » » 11 days ago, # ^ |   +3 Really amazing intuition!
•  » » » 10 days ago, # ^ |   0 Where can I find more such problems (based on center of mass)?
•  » » » 10 days ago, # ^ |   0 Amazing idea!!
•  » » » 10 days ago, # ^ |   0 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 )
•  » » 11 days ago, # ^ | ← Rev. 2 →   +1 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.
•  » » 10 days ago, # ^ | ← Rev. 2 →   0 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.
•  » » 10 days ago, # ^ |   0 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 :)
 » 11 days ago, # |   +8 I don't quite get the solution for D, like where do the equations come from?
•  » » 11 days ago, # ^ |   -68 Dumb solution in editorial. Just look at how array of prefix sums changes after operations.
•  » » » 11 days ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » 11 days ago, # ^ |   +8 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.
 » 11 days ago, # |   0 Thanks for fast editorial.
 » 11 days ago, # |   0 Thanks for the fast editorial and the great round. Gonna be BLUE today!!
•  » » 11 days ago, # ^ |   0 Lost blue today :/ (again) In fact, I'm down to the exact rating you had before this round. How things change...
•  » » » 11 days ago, # ^ |   0 Sad may you compensate your loss bro, since being a specialist u can do tomorrow's div3 , You will surely ace it , Good luck!
•  » » » » 11 days ago, # ^ | ← Rev. 2 →   0 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 meEdit: I only have math at the time of the contest, I'm tempted to skip, we'll see...
•  » » » » » 11 days ago, # ^ |   0 yeah. Mine is in 1 more week. When school starts, I also won't be able to take as many contests.
 » 11 days ago, # |   +1 Even though I wasn't able to solve D, I respect the problem.
•  » » 11 days ago, # ^ | ← Rev. 3 →   0 Have you understood the solution yet? I have not :( edit: figured it out from above comment :)
 » 11 days ago, # |   0 Why there is an indentation in problem $F$ solution in line ans ^= f[j — i]? I was a little confused.
 » 11 days ago, # |   0 I think implementation for C isn't explained enough, and the tutorial is just a simplification of a problem.
•  » » 11 days ago, # ^ |   +1 jiangly's submission is much clearer to me
 » 11 days ago, # | ← Rev. 2 →   0 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.
•  » » 10 days ago, # ^ |   +5 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
•  » » » 10 days ago, # ^ | ← Rev. 2 →   0 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 0Move 1 right: 0 1 0Psum of 1 right: 0 1 1Move 2 right: 0 0 1Psum of 2 right: 0 0 1The 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.
•  » » 10 days ago, # ^ |   0 This solution is easy to understand and intutive as well. Thanks for sharing!! But how to come up with this during the contest?
 » 10 days ago, # |   0 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 SubmissionMy 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. :(
•  » » 10 days ago, # ^ |   +17 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)
•  » » » 10 days ago, # ^ |   0 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.
 » 10 days ago, # |   +190 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.
•  » » 10 days ago, # ^ | ← Rev. 2 →   +58 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.
•  » » » 10 days ago, # ^ |   +20 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.
•  » » » » 10 days ago, # ^ |   +20 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.
•  » » » » » 10 days ago, # ^ |   0 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.
•  » » 10 days ago, # ^ |   +15 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.
•  » » 10 days ago, # ^ |   +13 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.
•  » » » 10 days ago, # ^ |   +38 didn't know we had a rule 34 for SG as well.
 » 10 days ago, # |   0 May the variable val in D's solution overflow?
•  » » 10 days ago, # ^ | ← Rev. 2 →   0 ignore this.
•  » » » 10 days ago, # ^ |   0 Does problem D have $mod$?
•  » » » » 10 days ago, # ^ |   0 problem D guaranteed that everything will not exceed $10^{18}$.
•  » » 10 days ago, # ^ |   0 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}$
•  » » » 10 days ago, # ^ |   0 Uh thanks, but I want to know how to prove that operation 2 can be performed $\le 10^{18}$
•  » » » » 10 days ago, # ^ |   0 er it's written in the output section of the statement
•  » » » » » 10 days ago, # ^ |   +5 it also write "It can be shown that ... won't exceed 10^{18}" and I don't know how to show
 » 10 days ago, # |   +18 Yeah, nice observation on $34^2$ numbers, feeling ashamed that I don't have the sight.
 » 10 days ago, # |   +27 Who keeps putting "constructive algorithms" tag on DEF? In what sense are they "constructive"?
•  » » 9 days ago, # ^ |   0 Maybe it is some kind of bot
 » 10 days ago, # | ← Rev. 3 →   +4 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
•  » » 10 days ago, # ^ |   0 oh, a nice solution!
•  » » 10 days ago, # ^ |   0 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]++).
•  » » » 10 days ago, # ^ |   0 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.
•  » » » » 10 days ago, # ^ |   0 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 xDBy 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.
•  » » » » » 10 days ago, # ^ |   0 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?
 » 10 days ago, # |   0 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?
•  » » 10 days ago, # ^ |   0 Yeah me too.
 » 10 days ago, # |   0 Thanks.
 » 10 days ago, # |   0 In problem E, can someone explain what dp and sum is? I am unable to understand from editorial
 » 10 days ago, # |   0 The problem was very interesting ty for the contest + D make me cry but after the tutorial the observation is quite good
 » 10 days ago, # |   0 Why greedy for B is correct to use?
•  » » 9 days ago, # ^ |   0 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.
•  » » » 9 days ago, # ^ |   0 "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.
•  » » » » 9 days ago, # ^ |   0 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.
 » 10 days ago, # |   +1 For problem E, sink point refers to the node with no out edges Hint from somebody who spent almost ten minutes figuring that out
 » 9 days ago, # |   0 As a pupil, This is the toughest div1 + div2 round I came across.
 » 9 days ago, # |   0 Thanks for the editorial
 » 8 days ago, # |   0 Duliu round :((Duliu means very difficult in Chinese)
 » 5 days ago, # |   0 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.
 » 4 days ago, # | ← Rev. 2 →   0 can someone explain why in E there must be a continuous time for which sink will be != 0. I was trying out with linear graph where sink value becomes 0 then again != 0.Thankyou****