AtCoder Regular Contest 143 Announcement

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!

• • • 3 hours ago, # ^ | Suppose we are assigning from 1 to n*n randomly on the grid. For a bad cell, a cell can be bad if 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), 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.

      • • 109 minutes ago, # ^ | 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)

• 4 hours ago, # ^ | 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 when they are in the intersection from the total number of permutation

  • 4 hours ago, # ^ | 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)

    • 4 hours ago, # ^ | If we define to be the number of "bad" permutation with i in the intersection,

      • 3 hours ago, # ^ | Thanks

      • 3 hours ago, # ^ | 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)

        • 3 hours ago, # ^ | (n^2,2n-1) means choose 2n-1 from n^2 numbers

        • 3 hours ago, # ^ | Sorry for my poor English. "in a whole"just means "as a whole"("看做一个整体" in Chinese)

• 4 hours ago, # ^ | Was slightly lucky that I had seen this observation earlier (As I was author one of the problem with same observation link :P).

• 4 hours ago, # ^ | ← Rev. 2 →   0 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

  • 4 hours ago, # ^ | 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

    • 4 hours ago, # ^ | ← Rev. 3 →   +10 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 , such that , and . 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 , 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.

• 4 hours ago, # ^ | I think the idea is exactly the same as 1667D - Edge Elimination

  • 103 minutes ago, # ^ | 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 in component if and only if all components of have an even number of white pieces (before flipping all pieces on vertices adjacent to ). From this you can find a topological order of removing vertices.

• 3 hours ago, # ^ | note that the graph (let's call it ) consists of two parts, we call them "upper part (vertices 1,..,n)" and "lower part (vertices n+1,...,2n)". for each , there is either an edge between upper and lower or upper and lower . now, build a new graph by merging upper and lower vertices for each . this graph has vertices and there is an edge between and for each , regardless of how we put edges in graph . now there is two observations: if edge is a bridge in , then it's a bridge in . if a vertex is not represented in a cycle in , then the edge between upper and lower in is a bridge. here is a method for choosing edges in such that for all vertices which are presented in a cycle in , edge between upper and lower is not a bridge: do a DFS in . if you traversed an edge from to , draw edge from upper to lower in . the proof for observations and method is left to reader as an exercise :))