### mnaeraxr's blog

By mnaeraxr, history, 4 years ago,

Competition is over. Is there any editorial available?

How to solve A, B, F?

• +91

 » 4 years ago, # | ← 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 years ago, # ^ |   +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 years ago, # |   +10 Has anybody got WA20 in L? What can be the reason of it?
•  » » 4 years ago, # ^ | ← 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 years ago, # ^ | ← 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 years ago, # ^ |   +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 years ago, # ^ |   +10 got TL 5. Used floating point fft
•  » » » » » 4 years ago, # ^ |   +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 years ago, # ^ |   +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 years ago, # ^ | ← 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 years ago, # |   +67
 » 4 years ago, # | ← 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 teammateThe 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 years ago, # ^ |   +48 You can also construct an apollonian circle and check if this circle intersects the perpendicular bisector.
 » 4 years ago, # |   +11 Anyone have solution code for E and H?
•  » » 4 years ago, # ^ |   +10 yes, why?
 » 4 years ago, # |   +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 years ago, # |   +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 years ago, # ^ |   +10 Actually, this exact DP can be found at OEIS: http://oeis.org/A213910
•  » » 4 years ago, # ^ | ← 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 years ago, # ^ |   +10 How do you use bitsets for this?
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   +8 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][].
•  » » » » 4 years ago, # ^ |   0 My bad, didn't think it through :/
 » 4 years ago, # |   +10 What's test 7 on C?
•  » » 4 years ago, # ^ |   +18 N = 1, answer should be 2.
•  » » » 4 years ago, # ^ |   +10 ............ :ultimate_facepalm:Stress tested with everything except $n = 1$. And that's the only case where my solution fails.