maroonrk's blog

XXI Opencup GP of Tokyo
By maroonrk, history, 4 years ago, In English

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

  • Vote: I like it
  • +202
  • Vote: I do not like it

Comments Comments (31)
| Write comment?
»
4 years ago, # |
  Vote: I like it +29 Vote: I do not like it

Auto comment: topic has been updated by maroonrk (previous revision, new revision, compare).

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve these Div. 2:

  • [L]ooking For Plagiarism?

  • [M]egafactorial?

  • [O]dds For Palindrome?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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

    → Reply
»
4 years ago, # |
  Vote: I like it +27 Vote: I do not like it

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)$$$.

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Allow me to ask you some questions:

    1. 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)$$$?
    2. 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?
    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      1. 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$$$.

      2. 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

      → Reply
»
4 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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?

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anybody explain task B? What does it mean: ”choose an element, and then delete its left or right neighbor”?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      But how do we calculate an answer for "each i"?

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +49 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Such a beautiful reduction to the problem of the number of paths in a rectangle! Thanks!

          → Reply
»
4 years ago, # |
  Vote: I like it +164 Vote: I do not like it

5 out of 10 problems use FFT, all of them in a very non-trivial way. Nice balanced contest.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +88 Vote: I do not like it

    Yeah in our team only one guy is really good with FFT and the rest of us were just: O_O

    → Reply
»
4 years ago, # |
  Vote: I like it +133 Vote: I do not like it

Grand Prix of 998244353 :)

→ Reply
»
4 years ago, # |
  Vote: I like it +50 Vote: I do not like it

Fun fact: There is "modulo 998244353" in all the problems.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain the solution to problem A broadly?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hey, I still am not getting the solution. What is it meant by the "boundary line" between the squares $$$\le i$$$ and $$$\gt i$$$?.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Draw the edges of the grid that separates a square with value $$$<i$$$ and square with value $$$>i$$$ (also include some edges of the big rectangle so that it is a path between opposite corners of the rectangle).

        → Reply
»
4 years ago, # |
  Vote: I like it +20 Vote: I do not like it

more explanation for H?

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Wow, 17234ms in my poor computer and 1824 ms in Codeforces!

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

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?

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 7   Vote: I like it +5 Vote: I do not like it

    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.

    → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it -61 Vote: I do not like it

Hard problems with the famous 998244353

→ Reply