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

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

Competition is over. Is there any editorial available?

How to solve A, B, F?

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

»
6 лет назад, скрыть # |
← 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?

  • »
    »
    6 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +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.

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

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

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

F: if $$$s_b \gt 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 \lt 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)

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

Anyone have solution code for E and H?

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +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

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +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.

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

What's test 7 on C?