Competition is over. Is there any editorial available?
How to solve A, B, F?
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 157 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 146 |
| 8 | orz | 146 |
| 10 | BledDest | 145 |
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?
$$$ (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.
Has anybody got WA20 in L? What can be the reason of 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?
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
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.got TL 5. Used floating point fft
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)
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.
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.
Editorial
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)
You can also construct an apollonian circle and check if this circle intersects the perpendicular bisector.
Anyone have solution code for E and H?
yes, why?
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
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.
Actually, this exact DP can be found at OEIS: http://oeis.org/A213910
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 >_>
How do you use bitsets for this?
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][].
My bad, didn't think it through :/
What's test 7 on C?
N = 1, answer should be 2.
............ :ultimate_facepalm:
Stress tested with everything except $$$n = 1$$$. And that's the only case where my solution fails.