fanache99's blog

[OpenCup] Grand Prix of Gomel
By fanache99, history, 3 years ago, In English

Solutions to E, H, I, K anyone?

  • Vote: I like it
  • +65
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it +48 Vote: I do not like it

Here's the official tutorial by tourist.

→ Reply
»
3 years ago, # |
  Vote: I like it +49 Vote: I do not like it

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).

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it +23 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 4   Vote: I like it +30 Vote: I do not like it

      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".

      → Reply
»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply