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

[OpenCup] Grand Prix of Gomel
Автор fanache99, история, 3 года назад, По-английски

Solutions to E, H, I, K anyone?

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

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

Here's the official tutorial by tourist.

→ Ответить
»
3 года назад, # |
  Проголосовать: нравится +49 Проголосовать: не нравится

The editorial of C tells us to find $$$(1+x+x^2)^k$$$ using "binary exponentiation and FFT". It may be understood as "multiply the polynomial by itself about log times", but in fact one can do fft, then $$$x \mapsto x^k$$$, then inverse fft. Though it still requires binary exponentiation, I believe that it should be faster than binary polynomial exponentiation (though it is kinda the same asymptotically).

→ Ответить
  • »
    »
    3 года назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +23 Проголосовать: не нравится

    Iirc some people commented about some way to find that in O(N), maybe adamant can reply here or make a blog about it.

    Edit: I'd welcome a blog like that if one doesn't exist, but here's the comment that someone linked: https://mirror.codeforces.com/blog/entry/73947?#comment-581173

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

      For $$$Q(x) = P^k(x)$$$ and $$$\deg P(x) = m$$$ it is possible to compute first $$$n$$$ terms of $$$Q(x)$$$ in $$$O(nm)$$$:

      $$$ Q'(x) P(x) = k P^k(x) P'(x) = kQ(x) P'(x). $$$

      Hence,

      $$$ q_i = \frac{1}{i p_0} \sum\limits_{j=1}^{\min(i,m)} p_j q_{i-j} [kj - (i-j)]. $$$

      This, indeed, provides a way to compute $$$(1+x+x^2)^k$$$ in $$$O(k)$$$.

      This approach was also explained in ODE techniques article, section "Exp in Gennady Korotkevich Contest 5".

      → Ответить
»
3 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

E: In the tree you can solve with two phases of DP. First, you count the number of reachable vertices in subtree (in bottom-up order), Second, you count the number of reachable vertices not in subtree (in top-down order) with help of the first computed values. In the cactus you just do the same thing. At least it's easier to write than B.

K: Do binary search, compute the min/max number of possible zeroes with DP (+ deques to optimize). If the desired number of zeroes fits into the interval, then the answer exists. I didn't prove it, but if you believe it, then you can just backtrack the DP to find the answer.

→ Ответить
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In editorial of F there is a small typo: $$$f(l, r) = 2f(\lfloor l/2 \rfloor, \lfloor r/2 \rfloor) + (l\%2)$$$

→ Ответить