maroonrk's blog

By maroonrk, history, 2 months 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

Announcement of XXI Opencup GP of Tokyo
 
 
 
 
  • Vote: I like it
  • +202
  • Vote: I do not like it

»
7 weeks 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).

»
7 weeks 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?

  • »
    »
    7 weeks 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

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In M you can precalc answer for 12!! and notice for getting zero for greater n.

    In L just use Catalan numbers.

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

  • »
    »
    7 weeks 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?
    • »
      »
      »
      7 weeks 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

»
7 weeks 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?

»
7 weeks 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”?

  • »
    »
    7 weeks 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.

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        7 weeks 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.

        • »
          »
          »
          »
          »
          7 weeks 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!

»
7 weeks 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.

  • »
    »
    7 weeks 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

»
7 weeks ago, # |
  Vote: I like it +133 Vote: I do not like it

Grand Prix of 998244353 :)

»
7 weeks ago, # |
  Vote: I like it +50 Vote: I do not like it

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

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain the solution to problem A broadly?

  • »
    »
    7 weeks 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.

    • »
      »
      »
      7 weeks 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$$$?.

      • »
        »
        »
        »
        7 weeks 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).

»
7 weeks ago, # |
  Vote: I like it +20 Vote: I do not like it

more explanation for H?

»
7 weeks 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?

  • »
    »
    7 weeks 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.

»
7 weeks 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

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

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

»
3 weeks 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?

  • »
    »
    3 weeks 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.