maroonrk's blog

By maroonrk, history, 4 days ago,

We will hold AtCoder Regular Contest 140.

The point values will be 300-400-500-700-800-900.

We are looking forward to your participation!

• +142

 » 3 days ago, # |   +23 Wish me luck.
•  » » 3 days ago, # ^ |   +18 Good luck
•  » » » 3 days ago, # ^ |   +18 Good luck.
•  » » 2 days ago, # ^ |   0 good luck
•  » » 2 days ago, # ^ |   0 good luck!
 » 2 days ago, # |   0 randomization can't solve problem E >3
•  » » 2 days ago, # ^ |   0 sure? this problem with c=3, n<=10 was in russian regional olympiad several years ago and proper solution is randomization
 » 2 days ago, # |   0 Anyone else got WA on 1 test case in C?
 » 2 days ago, # |   0 Took almost an hour to realize it was |P[i]-P[i+1]| instead of P[i]-P[i+1] in C lmao
 » 2 days ago, # |   +20 Bonus: the solution to problem E can be slightly modified to obtain a $625\times 625$ board. Can we construct a greater square board?
•  » » 47 hours ago, # ^ |   +10 I can't do better with a square board, but I think $625\times 650$ is possible. Identify the labels with elements of the finite field $\mathbb{F}_{25}$, the rows with ordered pairs $(u, v)\in \mathbb{F}_{25}^2$, and the columns with tuples $(a, b, c)\in \mathbb{F}_{25}^3$ where $(a, b)$ is restricted to the set $\{(1, x) \mid x\in \mathbb{F}_{25}\}\cup \{(0, 1)\}$. Then the label at the intersection of $(u, v)$ and $(a, b, c)$ is $au+bv+c$.Let's choose distinct rows and columns $(u_1, v_1), (u_2, v_2), (a_1, b_1, c_1), (a_2, b_2, c_2)$ and suppose that the corners all have the same label. If $(a_1, b_1) = (a_2, b_2)$ then $c_1\neq c_2$, so $a_1u_1+b_1v_1+c_1 \neq a_2u_1+b_2u_1+c_2$, i.e. the corners don't have the same label. Otherwise, $(a_1, b_1)\neq (a_2, b_2)$ so then $(u_1, v_1)$ is uniquely determined by $a_1u_1+b_1v_1+c_1$ and $a_2u_1+b_2v_1+c_2$. However, $(u_2, v_2)$ is determined by the same constraints so we would get $(u_1, v_1) = (u_2, v_2)$ contradiction.Also, by a counting argument, $625\times k$ is not possible for $k > 650$.
•  » » » 45 hours ago, # ^ |   0 If you can get $625 \times 650$, you can also get $625 \times 625$ by cutting the board (?)
•  » » » » 33 hours ago, # ^ |   0 The board $625\times625$ can be achieved just by placing $x_1x_2+y_1+y_2$ almost like in the editorial, but picking $x_{1,2}$ and $y_{1,2}$ from $\mathbb{F}_{25}$ instead of $\mathbb{Z}_{23}$. The question is, can you do at least $626\times 626$?
 » 2 days ago, # |   +8 Could anyone share the reasoning behind the particular construction in E (mentioned in editorial)? Thanks in advance!
•  » » 2 days ago, # ^ | ← Rev. 2 →   +90 Source: I spent almost the whole contest on problem E, and I got AC $37$ seconds before the end.My notes: PDF Page $9$: maybe it's useful to consider the "classical" bipartite graph. Page $10$: small cases by hand, in the $4 \times 4$ case the cells with color $1$ make a big cycle. Maybe the intended is choosing a color for each diagonal. Page $11$: there is a rectangle if there are two equal pairwise differences in the set of diagonals of a fixed color. Can we partition ${0, 1, \dots, 499}$ in such a way that there are no such differences? I tried to generate such diagonals on my PC, but I got stuck at $n \approx 370$. Page $13$: ok, let's quit the diagonals approach. Let's put the color $1$ greedily, but in such a way that there are $\approx \sqrt{500}$ occurrences on each row (unbalanced occurrences = more pairs of cells with the same color in the same row = worse) Page $14$: let's remove the rows $[4, 6]$ of page $13$, they seem inconsistent with the rest of the grid. Ok, we've found a construction with $n = m = 16$ and $4$ colors. [Actually it's wrong, there is a rectangle $(1, 1), (1, 11), (9, 1), (9, 11)$, but I hadn't noticed it.] Page $15$: oh wait, it works even with $n = m = 625$ and $25$ colors! [1:58:05] Submitted, got WA. Oh wait, there actually is a rectangle because $25$ is not prime. Let's try $23$. [1:59:23] Submitted, got AC, shouted like a crazy guy.
 » 2 days ago, # |   +44 I can't understand the editorial of D. What is "number of cycles that contain vertices in the connected components numbered x1...xk" mean?
•  » » 39 hours ago, # ^ | ← Rev. 2 →   +54 If we consider directed edge (i->xi), then each vertex will have out degree of exactly 1. Because of that, if we consider one graph such that all xi != -1, then each component will have at most one cycle if there are any.No. of connected components = No. of vertices — No. of edges + No. of cyclesInitially we will have n components in which no edge is added. We will start adding edges one by one. Adding each edge will reduce the component by one unless we are already in a same CC in which it won't reduce. All such edges will have one to one mapping with cycles. So we can count cycles instead. Now if we consider the graph with X array given in the question. We will get some components. Each component will have at most one xi = -1. We only consider the component with xi =-1 as we are interested only in cycles.Let the size of components be A1,A2...AM where M are the number of component which have xi = -1Consider the cycle formed from component set {A1,A2,A3...AK}. We can permute them in (k-1)! ways. And then we connect the edges. There are A2 edges we can direct of comp1 to comp2, A3 edges we can direct from comp2 to comp3 ... and A1 edges we can direct from compK to comp1. Then we can choose remaining edges arbitrarily. So we multiply N^(M-k). Thus for component set {A1,A2...AK} we have (k-1)! * A1 *A2...*Ak * N^(M-k)ways to form a cycle. So we can use NTT to find Summation of product of (A1*A2*A3..AK) for each k.
•  » » » 25 hours ago, # ^ |   0 Thanks a lot.
 » 2 days ago, # |   +39 Coming to ask for some help. Would anyone like to talk about problem D in more details? The editorial of problem D is somehow not so clear, at least for me :(I think this is about combinatorial mathmatics, but still not able to find out how to deal with it.
 » 29 hours ago, # |   0 Could anyone explain how so solve case $M=1$ in problem F. I don't understand clearly of the last part of the editorial.Thanks!