We will hold AtCoder Regular Contest 143.
- Contest URL: https://atcoder.jp/contests/arc143
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20220626T2100&p1=248
- Duration: 120 minutes
- Number of Tasks: 6
- Writer: yutaka1999
- Tester: maspy, satashun
- Rated range: — 2799
The point values will be 300-500-600-700-700-1200.
We are looking forward to your participation!
yutaka1999!
ABC 257 starting in less than a minute!!
How to solve B?
There can't be more than 1 bad cell.
Why?
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.
Thanks
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)
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)!$$$
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)
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}$$$
Thanks
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)
(n^2,2n-1) means choose 2n-1 from n^2 numbers
Sorry for my poor English. "in a whole"just means "as a whole"("看做一个整体" in Chinese)
I think B is possibly one of the best problems of 2022 so far. Thanks for setting it :flushed:
+1.
Was slightly lucky that I had seen this observation earlier (As I was author one of the problem with same observation link :P).
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?
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
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
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.
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.
Weak tc for C. https://atcoder.jp/contests/arc143/submissions/32779839 this soln gives "First" for this tc: 2 3 2 5 5
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.
I think the idea is exactly the same as 1667D - Edge Elimination
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.
I think C has the same key observation with problem CF1033G and even weaker itself.
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.
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
How to solve D?
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:
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 :))
When will the English editorial be published?
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
However, the answer turns out to be wrong. Can anyone tell whether it is wrong?
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}$$$.
But my solution is already $$$A_{x-1}^{N-1}$$$ instead of $$$C_{x-1}^{N-1}$$$ or $$$\binom{x-1}{N-1}$$$, and
here's my code
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'.
How to solve D?