maroonrk's blog

By maroonrk, history, 7 months ago,

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!

• +75

 » 7 months ago, # |   +23
 » 7 months ago, # |   0 ABC 257 starting in less than a minute!!
 » 7 months ago, # |   +8 How to solve B?
•  » » 7 months ago, # ^ | ← Rev. 2 →   +47 HintThere can't be more than 1 bad cell.
•  » » » 7 months ago, # ^ |   0 Why?
•  » » » » 7 months ago, # ^ |   +7 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.
•  » » » » » 7 months ago, # ^ |   0 Thanks
•  » » » » » » 7 months ago, # ^ |   +2 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)
•  » » 7 months ago, # ^ |   +4 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)!$
•  » » » 7 months ago, # ^ |   0 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)
•  » » » » 7 months ago, # ^ |   +4 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}$
•  » » » » » 7 months ago, # ^ |   0 Thanks
•  » » » » » 7 months ago, # ^ |   0 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)
•  » » » » » » 7 months ago, # ^ |   0 (n^2,2n-1) means choose 2n-1 from n^2 numbers
•  » » » » » » 7 months ago, # ^ |   0 Sorry for my poor English. "in a whole"just means "as a whole"("看做一个整体" in Chinese)
 » 7 months ago, # |   +37 I think B is possibly one of the best problems of 2022 so far. Thanks for setting it :flushed:
•  » » 7 months ago, # ^ |   +11 +1.Was slightly lucky that I had seen this observation earlier (As I was author one of the problem with same observation link :P).
 » 7 months ago, # | ← Rev. 2 →   0 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?
•  » » 7 months 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
•  » » » 7 months ago, # ^ |   +3 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
•  » » » » 7 months ago, # ^ | ← Rev. 3 →   +23 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.
•  » » » » » 7 months ago, # ^ |   0 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.
 » 7 months ago, # | ← Rev. 2 →   +13 Weak tc for C. https://atcoder.jp/contests/arc143/submissions/32779839 this soln gives "First" for this tc: 2 3 2 5 5
 » 7 months ago, # |   +31 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.
•  » » 7 months ago, # ^ |   +10 I think the idea is exactly the same as 1667D - Edge Elimination
•  » » » 7 months ago, # ^ |   +26 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.
•  » » 7 months ago, # ^ |   +18 I think C has the same key observation with problem CF1033G and even weaker itself.
•  » » » 7 months ago, # ^ |   +3 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.
 » 7 months ago, # |   +70 Are the tests for C a bit weak?https://atcoder.jp/contests/arc143/submissions/32776447 will fail on 1 2 3 6https://atcoder.jp/contests/arc143/submissions/32776804 will fail on 1 1 1 2
 » 7 months ago, # |   +4 How to solve D?
•  » » 7 months ago, # ^ |   +19 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: if edge $i$ is a bridge in $H$, then it's a bridge in $G$. 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 :))
 » 7 months ago, # | ← Rev. 2 →   +8 When will the English editorial be published?
 » 7 months ago, # |   +10 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?
•  » » 7 months ago, # ^ |   0 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}$.
•  » » » 7 months ago, # ^ | ← Rev. 2 →   0 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#include using namespace std; const long long MAXN=505; const long long MOD=998244353; long long n; long long jc[MAXN*MAXN],inv[MAXN*MAXN],jcinv[MAXN*MAXN]; void prepro(){ long long i,j; //jc jc[1]=1; for(i=2;i<=n*n;i++) jc[i]=(jc[i-1]*i)%MOD; //inv inv[0]=inv[1]=1; for(i=2;i<=n*n;i++) inv[i]=(MOD-MOD/i)*inv[MOD%i]%MOD; //jcinv jcinv[0]=jcinv[1]=1; for(i=2;i<=n*n;i++) jcinv[i]=(jcinv[i-1]*inv[i])%MOD; } void solve(){ long long i,j; long long ans=1; for(i=n;i<=n*n-n+1;i++) ans=ans *jc[i-1]%MOD *jc[n*n-i]%MOD *jc[n*n-2*n+1]%MOD *jcinv[i-n]%MOD *jcinv[n*n-n-i+1]%MOD; ans=(ans*n%MOD*n)%MOD; cout<>n; prepro(); solve(); } 
•  » » » » 7 months ago, # ^ |   0 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'.
•  » » » » » 7 months ago, # ^ |   0 Oh, so it is $(N^2)!-N^2\sum_{x=N}^{N^2-N+1} A_{x-1}^{N-1}A_{N^2-x}^{N-1}(N^2-2N+1)!$thank you! 谢谢
•  » » » » » » 7 months ago, # ^ | ← Rev. 2 →   0 \begin{aligned} (N^2)!-\sum_{x=N}^{N^2-N+1} (C_{x-1}^{N-1}*N!)*(C_{N^2-x}^{N-1}*N!)*(N^2-2N+1)! \end{aligned}
 » 7 months ago, # |   -8 How to solve D?
 » 7 months ago, # |   -42 bad description
 » 7 months ago, # | ← Rev. 2 →   0 In editorial of B For each pair of these, we have (N−1)!×(N−1)!×(N−1)^2! ways to fill the gridI don't understand how. Should not this be (N-1)^2! because for each pair there are (N-1)^2 squares left and same number of numbers. But its giving wrong answer.