maroonrk's blog

By maroonrk, history, 7 weeks ago, In English

We will hold AtCoder Regular Contest 131.

The point values will be 300-300-600-600-600-1000.

We are looking forward to your participation!

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

»
7 weeks ago, # |
  Vote: I like it +12 Vote: I do not like it

Can the round be shifted an hour or two earlier, since it ends at the exact time Codechef snackdown starts.

»
7 weeks ago, # |
  Vote: I like it +64 Vote: I do not like it

This round intersects with OpenCup stage. Also please update rust

»
7 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

How do you solve D and E? Great contest btw, especially enjoyed proving C.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    The editorial of C made me angry...

  • »
    »
    7 weeks ago, # ^ |
    Rev. 2   Vote: I like it +30 Vote: I do not like it

    E: It's easy to see that there is no solution when $$$n = 3$$$ or $$$n \mod 3 = 2$$$. For $$$n \mod 3 = 2$$$ the total number of edges is not divisible by $$$3$$$. For $$$n = 3$$$ the only configuration with equal number of edges per color is a triangle, whch is prohibited.

    What about the other possible values of $$$n$$$?

    One of the possible solutions is to output matrix with equal numbers in each row. If we do that, condition 2 holds automatically. The reason: for each triangle there is a row having two of its edges, and we have equal numbers in each row. So the three numbers cannot be all different.

    Now we need to match condition 1. The number of symbols in rows are 1, 2, 3, ..., n — 1. So the question is whether we can split these numbers into three groups with equal sums. Turns out that it's always possible for $$$n \mod 3 \ne 2, n \ge 6$$$. Examples:

    6: {1 4}, {2 3}, {5} — sum of numbers in each subset is 5.

    7: {1 6}, {2 5}, {3 4}

    9: {1 2 3 6}, {4 8}, {5 7}

    10: {1 2 3 4 5}, {6 9}, {7 8}

    Any larger number $$$x$$$: partition for $$$x - 6$$$, and remaining 6 numbers are split into pairs similar to {1 6}, {2 5}, {3 4}

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Regarding splitting 1 to n-1 in three equal parts, You came up with this pattern with observation or some step-by-step deduction?

      • »
        »
        »
        »
        7 weeks ago, # ^ |
          Vote: I like it +18 Vote: I do not like it

        It's hard to say :) I think the chain of reasoning was the following:

        1. How can we enforce Condition #2? No having triangles with all 3 edges of distinct colors?

        2. OK, I don't know how to do that for the whole graph. Can we consider a small part of the graph? E.g. a vertex and its neighborhood?

        3. OK, for a single vertex there is quite a straightforward solution. Let's just use the same color for all edges incident to it.

        4. Can this be generalized to the whole graph? Yes — if we process vertices one by one and color only edges that are not colored yet. Note that this corresponds to coloring the adjacency matrix line by line.

        5. Now we have Condition #2 enforced. What about condition #1 (equal number of edges of each color)?

        6. As on each step we color all edges incident to some vertex, numbers of colored vertices on different steps are $$$n - 1, n - 2, \dots, 2, 1$$$.

        7. Now it's easy to see that we have to find three subsets of $$$1, 2, \dots, n - 1$$$ with equal sum of elements.

        I hope this was helpful :) To be honest, I spent some time on other ideas which didn't lead to a solution, and I guess it was a luck that I started thinking in this direction.

  • »
    »
    7 weeks ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Problem D:

    In the optimal solution, there is an arrow in $$$[0, d-1]$$$.

    If you fix the position $$$p$$$ of the arrow in $$$[0, d-1]$$$, you can get the solution greedily by always choosing coordinates as close to $$$0$$$ as possible. Let $$$a_p$$$ be the optimal sum with an arrow in position $$$p$$$.

    You can calculate answers, in order, from $$$a_0$$$ to $$$a_{d-1}$$$, after preprocessing: each $$$r_i$$$ contributes to at most $$$2$$$ differences $$$a_p - a_{p+1}$$$.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    D: It's easy to see that the optimal configuration is a sequence of shots where the distance between consecutive shots is exactly $$$D$$$. Moreover, we can always assume that one of the shots is located at some point $$$r_i$$$ (otherwise we can always slightly move all shots and answer won' change). Therefore it is sufficient to consider only $$$D$$$ placements uniquely defined by the remainder of dividing a position of shots by $$$D$$$, and find the best placement among them.

    We can evaluate one such placement naively (e.g. for remainder $$$0$$$ it is straightforward). We need to count number of shots in each of segments, and sum up the largest $$$n$$$ numbers. To process the other placements, we can use a sweepline. Each border $$$r_i$$$ corresponds to an event where you add one number and remove another number. We can sort all events and process them by a sweepine, managing a set of $$$n$$$ largest numbers.

    Time complexity: $$$O(m \log m + n \log n)$$$ or $$$O(D + m + n \log n)$$$, if instead of sorting all events we just fill $$$D$$$ vectors of events.

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      And what about "negative points"? You just extend the positive ri's with negative ri's? Or there is some other clever trick?

      • »
        »
        »
        »
        7 weeks ago, # ^ |
        Rev. 2   Vote: I like it +3 Vote: I do not like it

        Negative points similarly correspond to some events (one number added, another removed). As we consider only remainders modulo $$$D$$$, we can process both "negative" and "positive" points together. The only difference is that "negative" points "start" taking effect at $$$-r_i$$$, while "positive" points "stop" taking effect at $$$r_i$$$. So when using sweepline, for each remainder modulo $$$D$$$ we should first process events for "negative" points, then evaluate the point, and then process events for "positive" points.

        You might refer to submission https://atcoder.jp/contests/arc131/submissions/27724234 (function process_events). Definitely not the best implementation, but still.

»
7 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

Thanks for the contest, problems are very nice!

Am I the only one who got WA in E because of using RGB colors instead of RWB? :)

»
7 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

Problems were great, editorial of C is fantastic

»
7 weeks ago, # |
Rev. 2   Vote: I like it -10 Vote: I do not like it

.

»
7 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

In problem D I got AC 45 and WA 5.

What's wrong?

submission

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell me what is wrong with my code for Problem A of today's contest?

I am getting the wrong answer verdict only on system test case 1 (in01.txt). How can I see this test?

My Code
»
7 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

how to solve problem C? Please anyone.nichke please explain.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can read my comment or the editorial, it was published by AtCoder: https://atcoder.jp/contests/arc131/editorial/3057

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    My solution is based on a fact that, If N is odd, player making first move always wins. I am going to prove that later and for now let us assume that it is true.

    If N is even and XOR of all elements(let, X) is exist in the array, then I can win in my first move by removing the element which is equal to X(arr[i] = X) and game ends. Otherwise, I have to remove an element but the game continues and the game becomes where (N — 1)(which is of course odd) element exists and other player makes the first moves and so the other player wins.

    Ok. Now let's prove, If N is odd, player making first move always wins.[Reminder: All elements are distinct]

    Let's assume I started the game by making the first move and after some moves the other player got a move where removing one element makes XOR of remaining elements 0. If that happens I always could swap my previously taken element with any one of the currently remaining element which would make remaining XOR not-zero because all elements are distinct.

    This process continues until the array is empty. That makes player with first move always win.

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      thanks bhai. If that happens I always could swap my previously taken element with any one of the currently remaining element which would make remaining XOR not-zero because all elements are distinct, any proof for this??

      • »
        »
        »
        »
        7 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I don't have any formal proof. Hope it will help

        Let's say XOR of N numbers is zero. If I replace any one number with an other number XOR will change. For example,

        A = {1, 2, 4, 7} XOR of A = 0. I can not change value of any one position so that XOR of A becomes 0. I need at least 2 value for that.

»
7 weeks ago, # |
Rev. 8   Vote: I like it +1 Vote: I do not like it

About C:

It is a problem of games, therefore we should look for winning/losing positions.

If we can't win the game in one move, it is optimal to try to do so, that the other player wouldn't be able to win the game in one move. Therefore we should look for when we cannot achieve that our opponent wouldn't win in his next move.

Let's say the array currently is $$$x_1,x_2...x_k$$$ and $$$x_1\oplus x_2\oplus ...\oplus x_k=Y$$$. If we cannot achieve that, it must hold that for every $$$i$$$, there is an element $$$x_j (i\neq j)$$$, such that it can be deleted and the XOR will be 0. This implies that $$$x_i\oplus Y$$$ (the new XOR) is equal $$$x_j$$$ (because $$$b\oplus b=0$$$ (you only win in one move if an element in the array is equal to the XOR of whole array)). $$$x_i\oplus Y=x_j$$$ implies that $$$x_j\oplus Y= x_i$$$. So we get that there are such $$$(i,j)$$$ pairs in the array. But wait... If $$$k$$$ is odd, then we cannot make pairs! We can try to use this contradiction to figure out winning/losing positions.

So, if $$$k$$$ is odd, we can do so, that the other player wouldn't win. Therefore, our turn will come once again. And the array size is odd again. It means that at the end we will come to an array of size 1 and win.

And like it is common in game problems, if we aren't in the winning position (don't win in one move and the array size is even), we give the other player a winning position (array size is odd).

It kind of turns out what I wrote is very similar to the editorial, although I think this maybe is a bit more intuitive, because the only two main ideas we used were that we try to find winning/losing positions and that you shouldn't let your opponent win in one move.

»
7 weeks ago, # |
  Vote: I like it +31 Vote: I do not like it

Interesting observations on problem A:

  1. Sample output 2 is the number 869120. It is the same number in the handle of the problem writer E869120.

  2. Sample output 3 is the number 6283185. Divide this number by 2 gives the number 3141592.5, which is Pi and it is often used in AtCoder sample inputs.

»
7 weeks ago, # |
  Vote: I like it +29 Vote: I do not like it

Why so few upvotes to the blog? The problems were beautiful.

»
7 weeks ago, # |
  Vote: I like it +24 Vote: I do not like it

How to solve F?

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone give me a testdata to make me wrong , I get 49AC and 1WA on problem D . Now I'm very sad . Here's my submission my code (49ac1wa)

»
7 weeks ago, # |
  Vote: I like it +19 Vote: I do not like it

I hope the editorial of problem DEF will be published as soon as possible.

I think the round is fine by the way.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I have learned so hard in order to read English editorials, but now I find there are also Japanese editorials!