### maroonrk's blog

By maroonrk, history, 3 years ago,

Please note that the contest time is one hour earlier than the usual time.

We will hold AtCoder Regular Contest 120.

The point values will be 400-400-500-600-700-1600(800).

The full version of the last problem is unusually hard for ARC, so there is an 800-point subtask.

We are looking forward to your participation!

• +122

 » 3 years ago, # |   +77 Same time as Google Kickstart Round C :(
 » 3 years ago, # |   +10 Please try to prepond it.
 » 3 years ago, # |   -13 Please prepone or postpone , I hope you also know that the no. of participants will be very less due to kickstart then why not prepping or postponing ?
 » 3 years ago, # |   +34 Although it sucks for contests to overlap, especially with a Google round, I really appreciate AtCoder has been trying to run theirs at the same time each week. Out of all 347 contests ever hosted since 2016, a whopping 298(85.9%) of them have started at 12:00 UTC sharp. And for the past year, that number has been 88.8%. Their consistency is very impressive.
 » 3 years ago, # | ← Rev. 2 →   +86 Since the English editorial is not ready now, I'll leave short hints here. AAfter we do the operation for some $i$, the maximum among $a$ would be $a_i$. BThe colors of the cell $(i,j+1)$ and cell $(i+1,j)$ must be same for all valid $i,j$, and this necessary condition is also sufficient. CLet $B_i=A_i+i$. Find what happens to $B_i$ after an operation. DLet $B_1,B_2,\cdots,B_{2N}$ be the array after sorting $A$. The upper bound of the score is $\sum_{N+1 \leq i \leq 2N} B_i - \sum_{1 \leq i \leq N} B_i$. We can always achive this. EEach person $i$ should do one of the followings: type 1: move with velocity $+1$ until they meet person $i+1$, then move with velocity $-1$. type 2: move with velocity $-1$ until they meet person $i-1$, then move with velocity $+1$. We can prove that there is an optimal strategy in which no three consecutive people belong to the same type. Thus we can do DP in $O(N)$ time. F and F2Let $F(n,k)$ be the number of ways to steal $k$ from $n$ bottles, and let $G(n,k,i)$ be the number of ways in which the $i$-th bottle is stolen. We can see that $G(n,k,i)=F(n-D,k-1) - \sum_{l \leq j \leq r} G(n-D,k-1,j)$ for some $l,r$. When $D=2$, we can compute the recurrence relation in $O(N)$ time. For larger $D$, we'll see the recurrence relation as an operation on polynomials. Then we can make it fast by using Divide-and-Conquer and FFT, which results in an $O(N\log^2N)$ algorithm.UPD: it's up.
 » 3 years ago, # |   +147 I’m consistently in awe of how beautiful most AtCoder problems are. Can rarely solve any or am pathetically slow, but the ideas behind most of them are so elegant and many turn out to have such trivial solutions that I’m repeatedly banging my head while admiring it. Kudos to authors and everyone else involved yet again. Very grateful.
 » 3 years ago, # |   +11 From C, I really feel the charming of swapping, for I didn't get it until I read the editorial.So, can anyone give me some advice on how to think of the problems like this one.(I mean, problems about swapping)
•  » » 3 years ago, # ^ |   +19 I found that id+val, equality, can make them hold. Then, finding is to find the nearest point pair, and then every exchange will make the front id+1, and then it has no effect on the back. I recorded a weight array D with a tree array, and then found the corresponding answer through each bi+valb. My code: https://atcoder.jp/contests/arc120/submissions/22872204
•  » » » 3 years ago, # ^ |   +3 Thx dude, I see.Anyway, I wonder if I meet another problems about swapping, which direction should I think?
•  » » » » 3 years ago, # ^ |   +19 first looked at the conditions under which it didn't hold, and then found that there was a corresponding relationship between id+val, and then simulated the larger sample to get the result.
•  » » » » » 3 years ago, # ^ |   +3 Thank you again.
•  » » » » » » 3 years ago, # ^ |   +16 You're welcome~
 » 3 years ago, # | ← Rev. 2 →   +10 I'm sorry but the editorial of the E problem is really hard to understand. The picture in it is misleading!
•  » » 3 years ago, # ^ |   +11 Binsearch and instead of turning around when meeting, you can treat people as moving on straight line segments $y=a-x$ or $y=a+x$ for $0 \le x \le T$, with the condition that all the segments have to form a connected component.I use a DP that checks for each pair of people $(i,i+1)$ whether it's possible to connect them and everything to the right of them in one component if $i$ has a line $a_i+x$ and $i+1$ has a line $a_{i+1}-x$. The bruteforce version is $O(N^2)$ and it can be simplified to $O(N)$ quite easily.
•  » » » 3 years ago, # ^ |   +5 Thanks to your reply.I understand the editorial finally and it's really a good problem. But I think it'll be better if the picture in the editorial can be updated. Because of that picture, I almost misunderstand the mean idea of the editorial.However, the proof of the E problem is excellent and wonderful!
•  » » » 3 years ago, # ^ |   0 Can you share your code please? i can't understand how dp works
•  » » » » 3 years ago, # ^ |   +8 I submitted it so it's already shared. https://atcoder.jp/contests/arc120/submissions/22870157
•  » » » » » 3 years ago, # ^ |   0 Thanks!!
 » 3 years ago, # |   0 I have a WA idea for problem D, which I still cannot understand why it is wrong.First, I observe that a '(' could only match a ')' in a position of different parity, otherwise the number of characters between them is odd and thus cannot make a valid sequence. Therefore, I split the numbers into two sets, each one with different parity of the indices. Then I sort the first set in ascending order and the other in descending order. I think that this way of matching would maximize the cost. Finally, I match those two sets and construct a valid sequence.However, I got WA and still do not understand why. Could anyone find out my flaws? Thanks in advance.Here is my code: https://atcoder.jp/contests/arc120/submissions/22888138
•  » » 3 years ago, # ^ | ← Rev. 6 →   +3 Try 3 1 2 3 3 2 1 The Answer from your program will be ((())) Which yields 0, one better answer would be (())() which yields 4.The problem is: You are matching indices 3-0, 1-4 and 5-2 this way. By just placing '(' at the lower valued index and ')' at the higher valued index you get ((())), which does match indices 0-5, 1-4 and 2-3 though! Here's the flaw in your placement of the brackets. It is a valid bracket sequence, just not the one you wanted.
 » 3 years ago, # |   0 Is there any dynamic programming counting solution for problem B??
 » 3 years ago, # |   0 Why in problem D we should add i to a[i] (a[i] = a[i] + i)?