### maroonrk's blog

By maroonrk, history, 15 months 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 Announcement of XXI Open Cup, Grand Prix of Tokyo Comments (33)
 » Auto comment: topic has been updated by maroonrk (previous revision, new revision, compare).
 » How to solve these Div. 2: [L]ooking For Plagiarism? [M]egafactorial? [O]dds For Palindrome?
•  » » 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
•  » » In M you can precalc answer for 12!! and notice for getting zero for greater n.In L just use Catalan numbers.
•  » » Is it possible to upsolve the problems of Div.2? The status of the contest on opentrains is OVER(instead of / RUNNING (xxx attempts out of 2000) / UPSOLVING), and I can't submit or upsolve problems.Thanks in advance.
 » 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)$.
•  » » 15 months ago, # ^ | ← Rev. 2 →   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?
•  » » » 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
 » 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?
 » Can anybody explain task B? What does it mean: ”choose an element, and then delete its left or right neighbor”?
•  » » 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.
•  » » » But how do we calculate an answer for "each i"?
•  » » » » 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.
•  » » » » » Such a beautiful reduction to the problem of the number of paths in a rectangle! Thanks!
 » 5 out of 10 problems use FFT, all of them in a very non-trivial way. Nice balanced contest.
•  » » Yeah in our team only one guy is really good with FFT and the rest of us were just: O_O
 » Grand Prix of 998244353 :)
 » Fun fact: There is "modulo 998244353" in all the problems.
 » Can someone explain the solution to problem A broadly?
•  » » 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.
•  » » » Hey, I still am not getting the solution. What is it meant by the "boundary line" between the squares $\le i$ and $\gt i$?.
•  » » » » 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).
 » more explanation for H?
 » 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?
•  » » 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.
•  » » » I think that makes sense.Thanks~
 » 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
•  » » Wow, 17234ms in my poor computer and 1824 ms in Codeforces!
 » 14 months ago, # | ← Rev. 2 →   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?
•  » » 14 months ago, # ^ | ← Rev. 7 →   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.
 » 5 months ago, # | ← Rev. 2 →   Hard problems with the famous 998244353
•  » » Why downvote?
•  » » » Necroposting