### maroonrk's blog

By maroonrk, history, 3 years ago,

XXI Opencup GP of Tokyo will be held tomorrow.

I prepared the problems with the help from hos.lyric.

I'll upload the editorial after the contest ends, and also I'll upload the contest to the GYM.

Editorial

GYM

• +202

| Write comment?
 » 3 years ago, # |   +29 Auto comment: topic has been updated by maroonrk (previous revision, new revision, compare).
 » 3 years ago, # |   0 How to solve these Div. 2: [L]ooking For Plagiarism? [M]egafactorial? [O]dds For Palindrome?
•  » » 3 years ago, # ^ |   +3 Problem L is equivalent to number of correct bracket sequences length of 2*n. Answer for this is Catalan number.In problem M you could notice, that K! = 0 mod M for all K >= M, because M = 0 mod M and (n+1)! = (n + 1) * n!. So, answer for n > 12 is 0, otherwise we compute factorials
 » 3 years ago, # |   +27 Solution to D without multipoint evaluation:Let $T(x) = \sum_{i=1}^{N} \frac{C_i}{1 - A_ix}$.Let $P_{[L, R]}(x) = \prod_{j=L}^{R} (x + B_j)$Then, the answer for a given $k$ is the coefficient of $x^0$ in $T(x)P_{[1, k]}(1/x)$To solve for a given $(T(x), L, R)$, recursively solve $(T(x), L, M)$ and $(T(x)P_{[L, M]}(1/x), M + 1, R)$. We only need to maintain the first $R - L + 2$ coefficients of $T(x)$ and hence it works in $O(N \log^2 N)$.
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 Allow me to ask you some questions: What does "solve for a given $(T(x), L, R)$" mean exactly? Is it to find the coefficient of $x^0$ in $T(x) P_{[L,R]}(1/x)$ given the first $R-L+2$ coefficients of $T(x)$? About "We only need to maintain the first $R-L+2$ coefficients", I think we need to compute $N$ coefficients of $T(x)$ anyway because we need to solve for $(T(x), 1, N)$. If so, what makes us compute $T(x)$'s coefficients without multipoint evaluation?
•  » » » 3 years ago, # ^ |   0 Solving for $(T(x), L, R)$ means finding the coefficient of $x^0$ in $T(x) P_{[L, k]}(1/x)$ for each $k$ in $[L, R]$. We only need $R - L + 2$ coefficients as the degree of $P_{[L, k]}$ is going to be $\leq R - L + 1$ for each valid $k$. We call the function on $\sum_{i=1}^{N} \frac{C_i}{1 - A_i x}, 1, N$ to get all the answers. No multipoint evaluation needed. Code
 » 3 years ago, # |   +4 Guys, how can we solve I? I mean, knowing the number of 'pockets' we can insert some number to, how do we calculate an answer?
 » 3 years ago, # |   0 Can anybody explain task B? What does it mean: ”choose an element, and then delete its left or right neighbor”?
•  » » 3 years ago, # ^ |   0 You can find that for all 4 possible consecutive two elements (i.e. 00,01,10,11) one of the following is always true: · picking left element <-> apply AND operator, and picking right element <-> apply OR operator; · picking left element <-> apply OR operator, and picking right element <-> apply AND operator.
•  » » » 3 years ago, # ^ |   0 But how do we calculate an answer for "each i"?
•  » » » » 3 years ago, # ^ |   +49 Let's use $(x,y)$ to denote the state that we need to delete $x$ elements to the left and $y$ elements to the right. We can find that there are $2x-1$ ways to get to state $(x-1,y)$ from state $(x,y)$. Similarly, there are $2y-1$ ways to get to state $(x,y-1)$ from state $(x,y)$. Since there are $\binom{x+y}{x}$ paths from $(x,y)$ to $(0,0)$, we can see that the answer is just $\binom{x+y}{x}(2x-1)!!(2y-1)!!$. For each $i$ with $A_i=1$, we just apply the formual above with $x=i-1$ and $y=n-i$, which can be done in $O(1)$ time if we precalculate all the things we need.
•  » » » » » 3 years ago, # ^ |   0 Such a beautiful reduction to the problem of the number of paths in a rectangle! Thanks!
 » 3 years ago, # |   +164 5 out of 10 problems use FFT, all of them in a very non-trivial way. Nice balanced contest.
•  » » 3 years ago, # ^ |   +88 Yeah in our team only one guy is really good with FFT and the rest of us were just: O_O
 » 3 years ago, # |   +133 Grand Prix of 998244353 :)
 » 3 years ago, # |   +50 Fun fact: There is "modulo 998244353" in all the problems.
 » 3 years ago, # |   0 Can someone explain the solution to problem A broadly?
•  » » 3 years ago, # ^ |   +3 For each $1 \le i \le K$, consider the "boundary line" between the squares $\le i$ and $> i$ (from bottom-left corner to top-right corner), and shift the $i$-th path $1$ unit to the right and $1$ unit downwards. If there were no $A_{R,C} = V$ condition, then the problem is just counting set of disjoint paths with some set of starting points and ending points that can be solved using Lindstrom-Gessel-Viennot Lemma.To handle the $A_{R,C}=V$ condition, note that it is equivalent to saying that $V-1$ paths continue on the "top-left" of some point $p$ in the lattice and the other paths continue on the "bottom-right" of the same point $p$. To keep track of this information, instead of setting all edge weights as $1$ in LGV Lemma, set the edges adjacent to $p$ as $0$ and then for the row of edges below $p$, set the left side as $1$ and right side as $x$. This will multiply the weight all paths that go from the bottom-right by $x$. By LGV Lemma, you just need to find the determinant of the matrix, which is a polynomial in $x$. To find it fast, substitute values and use Lagrange Interpolation.
•  » » » 3 years ago, # ^ |   0 Hey, I still am not getting the solution. What is it meant by the "boundary line" between the squares $\le i$ and $\gt i$?.
•  » » » » 3 years ago, # ^ |   0 Draw the edges of the grid that separates a square with value $i$ (also include some edges of the big rectangle so that it is a path between opposite corners of the rectangle).
 » 3 years ago, # |   +20 more explanation for H?
 » 3 years ago, # |   0 Are there any more explanation of D?$\sum_{1\leq i\leq n} C_i*f(A_i)$This gives the value of $\sum_{1\leq k \leq n} Z_i$Is this solving the transposing of the original problem?If yes,then what's the matrix that is transposed?
•  » » 3 years ago, # ^ |   +8 This is definitely a bit of a strange concept, I think you should look at the linked paper for more details.The original problem can be thought of as a linear transformation of given $[x]$, find the values $[Z_1 x, Z_2 x, Z_3 x, \ldots, Z_k x]$, which is just a left-multiplication by a $k \times 1$ matrix. The transpose then, is given $[D_1, D_2, \ldots, D_k]$, find $[\sum_{i=1}^k D_i Z_i]$, which is multiplying by the $1 \times k$ matrix. Then, we can essentially take any algorithm which solves the transposed problem and "reverse+transpose" it to get a solution to the former; this is because we can treat the algorithm as a sequence of linear transformations, and $(AB)^T = B^TA^T$. It is definitely a little strange, but seems like a pretty interesting concept to me.
•  » » » 3 years ago, # ^ |   0 I think that makes sense.Thanks~
 » 3 years ago, # |   0 Problem C: time limit per test: 4 seconds is too strictly for me.It takes me 23s to compute $\frac{e^{Nx} - 1}{e^x - 1} \mod x^B, B = 10^6$ in my machine.109185142
•  » » 3 years ago, # ^ |   +8 Wow, 17234ms in my poor computer and 1824 ms in Codeforces!
 » 3 years ago, # | ← Rev. 2 →   +5 Can someone explain the solution to C? I have already understood the combinatorial meaning of $z$, but I don't know why this implies $z={W+H+1\choose W}$.PS : It is very interesting that $f(H,W,A,B)$ does not depend on $B$. Is there a combinatorial proof avoiding binomial coefficient identities?
•  » » 3 years ago, # ^ | ← Rev. 7 →   +5 I realized that the first question is silly.Now imagine a path from $(0,0)$ to $(p,Ap+B)$ (let's denote this part of the path by $u$) and then to $(W,H)$ (denote this by $v$).Consider paths shaped like $u+\uparrow+v$, they are exactly all the paths from $(0,0)$ to $(W,H+1)$. $p$ indicates the last time for them to touch $y=Ax+B$. (it is obvious that it must go $\uparrow$ after touching $y=Ax+B$ for the last time, or it will never reach $(W,H+1)$ since $(W,H+1)$ is above $y=Ax+B$)This also explained why $z$ does not depend on $A$ or $B$, because $A$ and $B$ only effect how we classify these paths.
 » 2 years ago, # | ← Rev. 2 →   -61 Hard problems with the famous 998244353
•  » » 2 years ago, # ^ |   0 Why downvote?
•  » » » 2 years ago, # ^ |   +10 Necroposting