Please note that the contest time is one hour earlier than the usual time.
We will hold AtCoder Regular Contest 120.
- Contest URL: https://atcoder.jp/contests/arc120
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20210523T2000&p1=248
- Duration: 120 minutes
- Number of Tasks: 6
- Writer: QCFium
- Tester: maspy, satashun
- Rated range: — 2799
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!
Same time as Google Kickstart Round C :(
Please try to prepond it.
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 ?
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.
Since the English editorial is not ready now, I'll leave short hints here.
After we do the operation for some $$$i$$$, the maximum among $$$a$$$ would be $$$a_i$$$.
The 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.
Let $$$B_i=A_i+i$$$. Find what happens to $$$B_i$$$ after an operation.
Let $$$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.
Each person $$$i$$$ should do one of the followings:
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.
Let $$$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.
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.
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)
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
Thx dude, I see.
Anyway, I wonder if I meet another problems about swapping, which direction should I think?
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.
Thank you again.
You're welcome~
I'm sorry but the editorial of the E problem is really hard to understand. The picture in it is misleading!
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.
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!
Can you share your code please? i can't understand how dp works
I submitted it so it's already shared. https://atcoder.jp/contests/arc120/submissions/22870157
Thanks!!
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
Try
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.Is there any dynamic programming counting solution for problem B??
Why in problem D we should add i to a[i] (a[i] = a[i] + i)?