maroonrk's blog

AtCoder Regular Contest 143 Announcement
By maroonrk, history, 22 months ago, In English

We will hold AtCoder Regular Contest 143.

The point values will be 300-500-600-700-700-1200.

We are looking forward to your participation!

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

Comments Comments (37)
| Write comment?
»
22 months ago, # |
  Vote: I like it +23 Vote: I do not like it

yutaka1999!

→ Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

ABC 257 starting in less than a minute!!

→ Reply
»
22 months ago, # |
  Vote: I like it +8 Vote: I do not like it

How to solve B?

→ Reply
  • »
    »
    22 months ago, # ^ |
    ← Rev. 2   Vote: I like it +47 Vote: I do not like it
    Hint
    → Reply
    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Why?

      → Reply
      • »
        »
        »
        »
        22 months ago, # ^ |
          Vote: I like it +7 Vote: I do not like it

        Suppose we are assigning from 1 to n*n randomly on the grid. For a bad cell, a cell can be bad if

        1. it is the lowest number in this row (since every other number in row has a smaller number which is this number but this number does not have),

        2. it is the largest in its column as well (since we needed atleast 1 greater in column but we don't , everything else is smaller).

        Now if we are assigning numbers on grid in order , let's say we want to make some cell (xi,yi) bad first. Then in order to satisfy both of these conditions, we must fill entire column before filling this cell. Now this also implies that every other row now has smallest element in yi itself and therefore all of them have greater number in column which is (xi,yi) . So we cannot make any more bad cells further.

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

          Thanks

          → Reply
          • »
            »
            »
            »
            »
            »
            22 months ago, # ^ |
              Vote: I like it +2 Vote: I do not like it

            Furthermore if you want to see some more properties, you can search for saddle points in zero sum game matrix. Some properties which I could recall are-

            1) Swapping any row or coloumn does not affect the count of saddle points. 2) All the saddle points in the grid should have same value (In the given ques, since all the values are distinct we could have atmost one saddle point only)

            → Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Note that there can be maximum one "bad" cell per any permutation. Then, you can just subtract the contribution of each number from 1 to $$$N^2$$$ when they are in the intersection from the total number of permutation $$$(N^2)!$$$

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

      So, how to count the ans? Combination number is pretty hard to divide. It's too hard to a beginer.(Sorry for my poor English)

      → Reply
      • »
        »
        »
        »
        22 months ago, # ^ |
          Vote: I like it +4 Vote: I do not like it

        If we define $$$cnt_i$$$ to be the number of "bad" permutation with i in the intersection, $$$\forall i \in [1, N^2], cnt_i = N^2((N-1)!)^2((N-1)^2)!{i-1 \choose N-1}{N^2-i \choose N-1}$$$

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

          Thanks

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

          I think if you think the bad number and numbers in the same column or row in a whole, the sum of the cnt you said is (n^2,2n-1)

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

            (n^2,2n-1) means choose 2n-1 from n^2 numbers

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

            Sorry for my poor English. "in a whole"just means "as a whole"("看做一个整体" in Chinese)

            → Reply
»
22 months ago, # |
  Vote: I like it +37 Vote: I do not like it

I think B is possibly one of the best problems of 2022 so far. Thanks for setting it :flushed:

→ Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    +1.

    Was slightly lucky that I had seen this observation earlier (As I was author one of the problem with same observation link :P).

    → Reply
»
22 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Isn't C something like this? If the first player can win if he starts at some pile, then he can win the overall game, else second player wins?

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

    Almost, but you have to check for the piles that the first player loses, whether the second player is winning. Countertest to your solution could be
    2 7 4
    10 4

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

      I think I am really weak at problems like C (First or Second wins under some rules). Would you like to give some explanation or observation behind the logic? Thanks a lot

      → Reply
      • »
        »
        »
        »
        22 months ago, # ^ |
        ← Rev. 3   Vote: I like it +23 Vote: I do not like it

        Unless the question is supposed to be for high rated people (GMs or higher) , which would require Grundy number/nimbers/mex and etc, many game theory problems could be solved analyzing the winning states and losing states. I first looked at a single pile game, and observed that in order for the first player to win, there has to be an integer $$$k\geq 1$$$, such that $$$kx+(k-1)y\leq a_1$$$, and $$$kx + ky > a_1$$$. Let W denote a winning state and let L denote a losing state. It should be clear (with calculation) that W becomes L for the second player after the first player removes x stones, and L becomes W in a similar fashion. Now to generalize, consider the array as an array of Ls and Ws. The simple strategy of always handing the other person an array full of L (this should remind you of nim game if it doesn't I don't know why I wrote this), should be the optimal strategy. This solution is not possible if we have already have an array full of Ls to begin with and whatever move we make, there would be Ws in the resulting array. Now, it seems like if we have Ws to begin with, we can change all Ws to Ls and we are winning. However, there is one corner case, where we have $$$x > y$$$, and L for the first player is a W for the second player in some cases as shown above. If that is the case, the first player loses.

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

          Thank you so much for not only sharing your solution but also teaching me how to think about such problems from zero. I should start from a single pile and determine its state, and then generalize it to multiple piles. Thank you again for your invaluable help, and hope that next time when meeting similar problems, I could do better.

          → Reply
»
22 months ago, # |
← Rev. 2   Vote: I like it +13 Vote: I do not like it

Weak tc for C. https://atcoder.jp/contests/arc143/submissions/32779839 this soln gives "First" for this tc: 2 3 2 5 5

→ Reply
»
22 months ago, # |
  Vote: I like it +31 Vote: I do not like it

Problem B and C are pretty nice.

I am not sure if problem E is well known. It is same as a problem in Moscow Prefinals Workshop 2021 day1 though the contest is probably not open to public.

→ Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    I think the idea is exactly the same as 1667D - Edge Elimination

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

      Huh, I did not see why the ideas are the same.

      My solution for problem E in ARC is that you can remove all vertices in a component if and only if the component contains an odd number of white pieces. (We remove vertices rather than pieces.) Suppose that initially the tree contains an odd number of white pieces. Then you can remove a vertex $$$v$$$ in component $$$C$$$ if and only if all components of $$$C \backslash {v}$$$ have an even number of white pieces (before flipping all pieces on vertices adjacent to $$$v$$$). From this you can find a topological order of removing vertices.

      → Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    I think C has the same key observation with problem CF1033G and even weaker itself.

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

      Ah interesting. I did not know this problem before. During the contest I first observed that only parity of the number of pebbles matters when $$$X = Y = 1$$$ and then came to find the conclusion for general $$$X, Y$$$. Thus it is approachable and I think it is a good problem for problem C in an ARC round.

      → Reply
»
22 months ago, # |
  Vote: I like it +70 Vote: I do not like it

Are the tests for C a bit weak?

https://atcoder.jp/contests/arc143/submissions/32776447 will fail on 1 2 3 6

https://atcoder.jp/contests/arc143/submissions/32776804 will fail on 1 1 1 2

→ Reply
»
22 months ago, # |
  Vote: I like it +4 Vote: I do not like it

How to solve D?

→ Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    note that the graph (let's call it $$$G$$$) consists of two parts, we call them "upper part (vertices 1,..,n)" and "lower part (vertices n+1,...,2n)". for each $$$i$$$, there is either an edge between upper $$$a_i$$$ and lower $$$b_i$$$ or upper $$$b_i$$$ and lower $$$a_i$$$.

    now, build a new graph $$$H$$$ by merging upper $$$i$$$ and lower $$$i$$$ vertices for each $$$i$$$. this graph has $$$n$$$ vertices and there is an edge between $$$a_i$$$ and $$$b_i$$$ for each $$$i$$$, regardless of how we put edges in graph $$$G$$$.

    now there is two observations:

    1. if edge $$$i$$$ is a bridge in $$$H$$$, then it's a bridge in $$$G$$$.
    2. if a vertex $$$v$$$ is not represented in a cycle in $$$H$$$, then the edge between upper $$$v$$$ and lower $$$v$$$ in $$$G$$$ is a bridge.

    here is a method for choosing edges in $$$G$$$ such that for all vertices $$$v$$$ which are presented in a cycle in $$$H$$$, edge between upper and lower $$$v$$$ is not a bridge:
    do a DFS in $$$H$$$. if you traversed an edge from $$$v$$$ to $$$u$$$, draw edge from upper $$$v$$$ to lower $$$u$$$ in $$$G$$$.

    the proof for observations and method is left to reader as an exercise :))
    → Reply
»
22 months ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

When will the English editorial be published?

→ Reply
»
22 months ago, # |
  Vote: I like it +10 Vote: I do not like it

I've thought of a solution to problem B in the contest, but it turns out to be wrong for no reasons.

To find out how many ways satisfies both conditions, assume the cell filling with $$$x$$$ is both the minimum of the row and the maximum of the column, then there are $$$A_{x-1}^{N-1}$$$ ways to fill the other elements in the column, and $$$A_{N^2-x}^{N-1}$$$ ways to fill the other elements in the row, and there are $$$(N^2-2N+1)!$$$ ways to fill the other elements neither in the row nor in the column. The "illegal" cell can be anywhere, so the answer should be multiplied by $$$N^2$$$. Therefore, I think the answer is

$$$(N^2)!-N^2\prod_{x=N}^{N^2-N+1} A_{x-1}^{N-1}A_{N^2-x}^{N-1}(N^2-2N+1)!$$$

However, the answer turns out to be wrong. Can anyone tell whether it is wrong?

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

    The number of ways to fill the column containing $$$x$$$ is $$$\dbinom{x-1}{N-1}(N-1)!$$$ and not just $$$\dbinom{x-1}{N-1}$$$.

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

      But my solution is already $$$A_{x-1}^{N-1}$$$ instead of $$$C_{x-1}^{N-1}$$$ or $$$\binom{x-1}{N-1}$$$, and

      $$$A_{x-1}^{N-1}=C_{x-1}^{N-1}(N-1)!=\binom{x-1}{N-1}(x-1)!$$$

      here's my code

      My code to problem B
      → Reply
      • »
        »
        »
        »
        22 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        The expression should be the sum over all $$$x$$$ from $$$N$$$ to $$$N^2-N+1$$$ ( not the product ). Note that no two numbers can be 'bad' at the same time and so you sum up the ways in which each of them is 'bad'.

        → Reply
»
22 months ago, # |
  Vote: I like it -8 Vote: I do not like it

How to solve D?

→ Reply