maroonrk's blog

AtCoder Grand Contest 056 Announcement
By maroonrk, history, 3 years ago, In English

We will hold AtCoder Grand Contest 056. This contest counts for GP30 scores, and this is the final AGC of this year.

The point values will be 300-900-900-1600-1600-1600.

We are looking forward to your participation!

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

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

Good luck on the contest, starting in 50 minutes.

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

Fun fact: For all AGC problems with score>=1600 this year, the number of accepted solutions is no more than 1.

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

The scores of the problems are quite strange.

→ Reply
»
3 years ago, # |
  Vote: I like it -29 Vote: I do not like it

AGC is really hard, I even cannot solve any problems.

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

    Even, I can't solve a single problem!

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

      AtCoder has great problems, but the difficulty estimation is so bad it's not even fun. Every ABC I took part in first 5 problems — >700-800 solves and the 6th had like <100, come on how come yesterday's F and E are weighed 500 points both??? On the other hand in AGC I couldn't solve a single problem ever, the same holds today. ARC is the only balanced one, but regarding the during contest time I really don't find AGC/ABC fun anymore, I just feel like wasting 2-3 hours of my life every weekend, although during practice I tend to learn a lot from them.

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

        Well, they can't make everyone happy, I have heard many LGM/GM/IM saying they like AGC/Atcoder the way it is, and it seems like they are the targeted contestants so ig you won't be seeing any changes in AGC.

        Speaking of ABC, I find it educational enough and I get to learn new things from almost every ABC, so points doesn't matter much to me.

        -Atcoder fan

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

          I never requested changes, I just stated my opinion on how it currently is, it may or may not be right, but again my personal opinion.

          When it comes to learning from ABC I'd argue 5/8 problems are just as bad as a regular Div. 3 round on CodeForces and the rest can't match CF Edu 70% of the time. I feel like solving CodeChef Longs when doing ABC's — a couple of trivial ad-hoc problems and a couple of trivial implementation problems in case you've encountered the specific rare technique required for the problem e. g. FFT/NFT/Automata/Grey's Code...

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

        I participated in AGC054 (solved 1 problem), AGC055 (solved 0 problems) and AGC056 (solved 1 problem). The difficulty of problem A in AGC contests does not seem to be unreasonably hard.

        I suspect that your main problem is that you overestimate the problem difficulty and give up too early. And your comment also had been posted long before the contest was over. You still had a lot of time to work on solving at least problem A.

        → Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it -7 Vote: I do not like it

Problem C:

Why I change unordered_set to set and it pass ???!! Do the problem setter intentionally kill it in the test "01-027"?

https://atcoder.jp/contests/agc056/submissions/27696901

https://atcoder.jp/contests/agc056/submissions/27696734

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

I solved A, but my rank is only 5 ranks higher than people who didn't solve any.

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

Some feedback on the contest:

  • A: I enjoyed solving it, though I am not sure that my solution is the expected one since it uses some randomization. My construction goes as follows. Choose a random permutation $$$p_1, p_2, \dots, p_n$$$. On the $$$i$$$-th row we paint cells $$$p_i, p_i+1, p_i+2$$$ (considering the row as a circular vector). One shall just check that the number of connected components is correct and it turns out that choosing the permutation randomly a few times one finds a good one.
  • B: Very nice dp problem. I was lucky and had the right idea very quickly.
  • C: Problem of the year. Just amazing. When it clicked and I saw the solution, it was enlightening. It is cool that the most natural lowerbound on the solution is actually a construction and it is even easy to show its correctness.
  • D: Here I just submitted a solution that I have no idea why works. I submitted 3 minutes before the end and I was not even hoping for it to get accepted. I think that guessing is too easy in this problem and therefore it is not worth so many points.

Overall, it was a very good contest with a problem which was amazing. Thanks for the contest!

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

    Feedback on your feedback on C:

    It's cool, but this idea about lowerbound also appeared in 1450E - Capitalism (and remembering it helped me to solve the problem fast).

    But the contest was still amazing, thanks a lot to maroonrk!

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

    in problem C I can see from your code and also the editorial that we make a graph where we add an edge between adjacent $$$v_i$$$'s of weight $$$1$$$ and between all pairs given in the problem, of weight $$$0$$$. Then we find the shortest path from $$$v_0$$$ to all $$$v_i$$$'s.

    But I can't understand what has the shortest path from $$$v_0$$$ to $$$v_i$$$ got to do with maximizing $$$v_i$$$ lexicographically. Can you please help with this "cow technique" as to how are the inequalities and the shortest path equivalent.

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

      The cost-$$$0$$$ edges force certain $$$v_i$$$s to be equal, and the cost-$$$1$$$ edges allow increments from both the left and right until they meet in the middle. Intuitively, if you graph the resulting $$$v_i$$$, you can see that from left to right, the graph will increase unless forced to decrease by one or more equality constraints, matching the greedy nature of lexicographic ordering.

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

    Can you please explain your solution for C?

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

      It is exactly the one described in the editorial.

      The magic moment was when I noticed that the distance does not provide only a lowerbound but also a construction.

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

Not at all , an easy contest!!!!!!

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +37 Vote: I do not like it
An easy construction for A
Code
→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it
My solution for A
Edit: C++ source of the random blocks generator/validator (sizes from 3x3 to 8x8)
→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it
My solution for A:
→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How do you manually generate a valid 11x11 block? This is the most difficult part of your solution and you provide no explanations for it. Did you rely on some additional observations and/or heuristics?

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

Editorial to D is similarly useful to me than a sequence of random characters. Maybe after some time I would be able to parse and accept this, but it gives absolutely no intuition and looks ridiculous. Can somebody explain his reasoning on this problem? Maybe dario2994? (You said that the solution seems easy to guess, despite the fact that the solution from editorial looks ridiculous, so I suppose you must have had some intuition behind what you're doing)

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

    An intuitive way is to think about how Alice can win if $$$L=R$$$ and there is a specific subset that sum is $$$L$$$. Then Alice needs to pair the numbers to make sure that she can take this subset, otherwise, it's impossible for her to win.

    Then we can think about what if the number is $$$x+ y\times \varepsilon$$$, Alice still needs to take numbers from the pair and Bob now can choose arbitrary numbers from every pair. So it's not hard to guess the solution,

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

    My claim is that if Alice can win then she can win with the following strategy. Sort the array $$$A$$$.

    Choose two special indexes $$$i\not= j$$$. Then pair the remaining indexes in $$$\frac n2-1$$$ adjacent pairs. For example, if $$$n=5$$$ and $$$i=3$$$, $$$j=8$$$; then the pairs are $$$(1,2)$$$, $$$(4,5)$$$, $$$(6,7)$$$, $$$(9,10)$$$. Let the pairs be $$$(l_k, r_k)$$$.

    If $$$L \le A_i + A_{l_1} + A_{l_2} + \cdots + A_{l_k} \le A_i + A_{r_1} + A_{r_2} + \cdots + A_{r_k} \le R$$$, then Alice can win. Indeed, she begins by choosing $$$A_i$$$ and then she takes exactly one element from each pair (and $$$A_j$$$ will be taken by Bob).

    One has to check all possible $$$O(n^2)$$$ strategies (one for each choice of $$$i\not=j$$$).

    Why, if Alice can win, then she can win with such a simple strategy? No idea. Am I even sure that this is correct? Nope but it gets accepted.

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

      Oh wow, that makes total sense, thanks. Actually I have already written a code that does almost exactly that, but I did one stupid mistake in my thoughts, so I missed that

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

      I wrote exactly same solution and is struggling to prove why it works

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

      After some analysis of small case, I propose the following "proof"

      Let us prove that Alice can win with dario2994's strategy by induction on n.

      Suppose that A's winning strategy does not exist after choosing the first number.

      Name the remaining numbers as a_1, a_2, ..., a_(2t + 1)

      It is simple to find B's strategy if A has to declare one number to not choose at all in this game after choosing the first number. He just has to either keep choosing maximum or keep choosing minimum.

      Now, if B's strategy would be the same regardless of what number A declares to not choose, then we are done. Hence, we need to examine when if A declares he will not choose a_k then B can keep choose minimum to win and if A declares to not choose a_(k + 1) then B can keep choosing maximum to win.

      If we expand this condition out in terms of R and L, there is one number (either a_k or a_(k + 1)) that does not appear and excluding this number, the condition will be of the form (sum of (2p — 1)th number) < L < R < (sum of (2p)th number). B should choose the that one number not appearing in the condition and then (hopefully) mathematical induction would complete the proof. (I think the condition above would mean that if A then chooses i and avoids j, then if i < j then B chooses maximum and else B chooses minimum to win).

      I apologize for my inability to write Latex and I hope it is readable.

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

    You can modify the problem to the problem of minimax game of absolute value describe in the editorial.

    Notice that $$$\lvert x \rvert = max(x,-x)$$$, the problem can be describe as finding value of nested min, max function of some function $$$P_i(X,a_0,a_1,...,a_{n-1})$$$ such that coefficient of $$$X, a_i$$$ is $$$\pm 1$$$.

    Observe that when increase or decrease by $$$1$$$ of some $$$a_i$$$, the result is increase or decrease by $$$1$$$ because each $$$P_i(X,a_0,a_1,...,a_{n-1})$$$ is increase or decrease by 1 and invariant modulo 2. Also observe that adding $$$2$$$ same value $$$a_n = a_{n+1}$$$ into $$$(a_i)$$$ will not change the game because of when a additional move make an advantage for one player, the other can cancel it by making exactly same move.

    Now we want to to build the state $$$(a_0,a_1,...,a_{n-1})$$$ from some state with value $$$0$$$. The result of absolute value always $$$\geq 0$$$ so we will measure how close it can be reach from $$$0$$$, or tighten the upper bound for the result.

    So we find the minimum of maximum of the result, we need to start at Bob's turn and n odd. A state with value $$$0$$$ is a single $$$X$$$, adding $$$\frac{n-1}{2}$$$ pair of same value to make $$$n$$$ number such that minimize number of adjustment every number to arrive at state $$$(a_i)$$$. We get that by sorting the array $$$(a_0,a_1,...,X)$$$, make $$$n/2$$$ pair the adjacent of number and for each pair not contain $$$X$$$, add two same number of one element.

    The rest is to prove it, you can write a program to check it or induction,... I got some proof relate to color the line but it's quite complicate.

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

The problems were amazing!! :+1:

B was too difficult for me though :)

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

My solution for A

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

A bit another view at problem B, which worked for me for most of problems about segments, maxima and so: Our dynamic will be just $$$dp[i][j]$$$ — answer for segment $$$[i,j]$$$, when we are looking at maxima ​only of subsegments of $$$[i,j]$$$. How to recalculate it?

Let's call the element big, if it is maximal on all segments containing this element. Surely there are some big elements. Suppose we fix some set of elements ($$$S$$$), which will be big, and denote $$$F(S)$$$ — number of sequences, for which elements of $$$S$$$ are big. Then it is easy to calculate $$$F(S)$$$ — big elements split $$$[i,j]$$$ into some subsegments, and $$$F(S)$$$ is just a product of $$$dp$$$ of these subsegments. Only condition to big elements is that two different big elements can't be contained in one segment.

But $$$dp[i][j] =\sum_S(-1)^{|S|+1}F(S)$$$ using inclusion-exclusion principle, and this can be easily calulated in $$$O(n)$$$ by dynamics.

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

An alternate approach to E:

We could view the problem as generating several pieces of cheese on a circle. Each time we pick a piece of cheese, and we check it with the next mouse. It's eaten with probability 1/2 (if the mouse hasn't eaten anything yet) and travels an arc otherwise.

Notice that the order of picking cheese to check doesn't matter. So we could work arc by arc rather than cheese by cheese, which could be done by DP.

→ Reply