maroonrk's blog

By maroonrk, history, 3 years ago, In English

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!

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

»
3 years ago, # |
  Vote: I like it +77 Vote: I do not like it

Same time as Google Kickstart Round C :(

»
3 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Please try to prepond it.

»
3 years ago, # |
  Vote: I like it -13 Vote: I do not like 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 ?

»
3 years ago, # |
  Vote: I like it +34 Vote: I do not like it

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   Vote: I like it +86 Vote: I do not like it

Since the English editorial is not ready now, I'll leave short hints here.

A
B
C
D
E
F and F2

UPD: it's up.

»
3 years ago, # |
  Vote: I like it +147 Vote: I do not like it

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, # |
  Vote: I like it +11 Vote: I do not like it

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, # ^ |
      Vote: I like it +19 Vote: I do not like it

    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, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Thx dude, I see.

      Anyway, I wonder if I meet another problems about swapping, which direction should I think?

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

        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, # |
Rev. 2   Vote: I like it +10 Vote: I do not like it

I'm sorry but the editorial of the E problem is really hard to understand. The picture in it is misleading!

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

    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, # ^ |
        Vote: I like it +5 Vote: I do not like it

      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, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you share your code please? i can't understand how dp works

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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   Vote: I like it +3 Vote: I do not like it

    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, # |
  Vote: I like it 0 Vote: I do not like it

Is there any dynamic programming counting solution for problem B??

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why in problem D we should add i to a[i] (a[i] = a[i] + i)?