Solutions to E, H, I, K anyone?

# | User | Rating |
---|---|---|

1 | tourist | 3843 |

2 | jiangly | 3705 |

3 | Benq | 3628 |

4 | orzdevinwang | 3571 |

5 | Geothermal | 3569 |

5 | cnnfls_csy | 3569 |

7 | jqdai0815 | 3530 |

8 | ecnerwala | 3499 |

9 | gyh20 | 3447 |

10 | Rebelz | 3409 |

# | User | Contrib. |
---|---|---|

1 | maomao90 | 171 |

2 | adamant | 163 |

2 | awoo | 163 |

4 | TheScrasse | 157 |

5 | nor | 153 |

6 | maroonrk | 152 |

6 | -is-this-fft- | 152 |

8 | Petr | 145 |

9 | orz | 144 |

9 | pajenegod | 144 |

Solutions to E, H, I, K anyone?

↑

↓

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/18/2024 00:00:55 (k3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Here's the official tutorial by tourist.

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

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://codeforces.com/blog/entry/73947?#comment-581173

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)$$$:

Hence,

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

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.

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