Блог пользователя mnaeraxr

Автор mnaeraxr, история, 4 года назад, По-английски

Competition is over. Is there any editorial available?

How to solve A, B, F?

  • Проголосовать: нравится
  • +91
  • Проголосовать: не нравится

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +45 Проголосовать: не нравится

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?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +71 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
    Rev. 4   Проголосовать: нравится +8 Проголосовать: не нравится

    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?

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 5   Проголосовать: нравится +21 Проголосовать: не нравится

      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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +20 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +10 Проголосовать: не нравится

        got TL 5. Used floating point fft

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится +20 Проголосовать: не нравится

          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)

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +16 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        4 года назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        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.

»
4 года назад, # |
  Проголосовать: нравится +67 Проголосовать: не нравится
»
4 года назад, # |
Rev. 2   Проголосовать: нравится +38 Проголосовать: не нравится

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)

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +48 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

Anyone have solution code for E and H?

»
4 года назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

    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 >_>

»
4 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

What's test 7 on C?