mnaeraxr's blog

XXI Open Cup: GP of SPb
By mnaeraxr, history, 4 years ago, In English

Competition is over. Is there any editorial available?

How to solve A, B, F?

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

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

Our solution for problem B was an attempt to generalize Fermat Little Theorem over polynomials, but we still don't have any proof about why it works?

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

    $$$ (x^i+1)^{\text{mod}}=x^{i \text{mod}}+1 $$$ and since $$$ \text{mod} $$$ is a prime when modulo $$$ n $$$ we have $$$ \prod_{i=0}^{n-1} (x^i+1)^{\text{mod}} = \prod_{i=0}^{n-1} (x^i+1) $$$, and we can reduce $$$ T $$$ by this formula.

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

Has anybody got WA20 in L? What can be the reason of it?

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

    We got WA5 because we did initially all computations mod 998244353, but that was a case hacking this mod. After changing the mod to a more unusual, still FFT friendly, prime we got AC. Are you doing all computation with reals, or using mod?

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

      I tried to solve it without FFT, and more expected to have TL, not WA :)
      UPD: found a bug, now getting TL, never mind.
      UPD2: solution without FFT, just two BFS, gets AC (3.084s): https://pastebin.com/wWjVknQM

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

      After every multiplication you can "normalize" the polynomial with p[i] = min(1, p[i]). Then every coefficient after multiplication is at most p.size() and I believe any mod or floating-point works fine.

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

        got TL 5. Used floating point fft

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

          got AC 1.6s using fft with doubles in c++. We only have two optimizations: we precomputed the roots of unity and we did two ffts calls for every multiplication instead of three(item 16)

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

      We didn't get WA5 with mod 998244353; what we did is NTT, then take every number in the result to the power of l(or r-l, depending on which polynomial we're exponentiating) and then inverse NTT.

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

        Can you provide the formula you were using? I don't see any difference between solutions, yet you say that you had no problems with modulo.

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

Editorial

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

F: if $$$s_b > s_p$$$ you can always win (by throwing far enough)
if $$$s_b = s_p$$$ you can always win, unless opponent is between you and your teammate
The main case is $$$s_b < s_p$$$. Draw a Perpendicular Bisector between teammate and the opponent. If you are able to send the ball to this line so that it's not intercepted, your teammate will be here faster. So, you then get a quadratic equation and the sign of its discriminant determines the answer

Everyting can be done in integers(rationals)

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

    You can also construct an apollonian circle and check if this circle intersects the perpendicular bisector.

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

Anyone have solution code for E and H?

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

Nice tests in F (not a sarcasm), I wouldn't expect it was possible to fail $$$\varepsilon=10^{-8}$$$ within coordinates up to 75. If not for them I would have gotten AC within first hour :v

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

By the way it is possible to solve problem I in $$$O(n^3)$$$ even modulo anything instead of modulo 2. I actually think that is an easier solution than trick from editorial. Last cycle is either a loop (in that case we take answer from dp[n-1][k]) or it contains $$$n$$$ and $$$c$$$ for some number $$$c$$$ and it adds $$$2n-2c-1$$$ inversions, so we take answer from dp[n-2][k-2n+2c+1] then.

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

    Actually, this exact DP can be found at OEIS: http://oeis.org/A213910

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

    This is what I did as well. Since we are only interested in the parity of the answer, we could further use bitsets to calculate it in $$$O(n^3 / log\ n)$$$.

    EDIT: should have thought it through, calculating DP is indeed easy given the previous DP and prefix sum as bitsets, but I don't see how we can calculate the new prefix sums using bitsets >_>

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

      How do you use bitsets for this?

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

        If I understand correctly, we can calculate all dp[n][] using prefix sums sumdp of odd/even diagonals in one go: (sumdp[n — 1][] << 1) ^ dp[n — 1][].

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

        My bad, didn't think it through :/

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

What's test 7 on C?

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

    N = 1, answer should be 2.

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

      ............ :ultimate_facepalm:

      Stress tested with everything except $$$n = 1$$$. And that's the only case where my solution fails.

      → Reply