Hello!
I uploaded 2022-2023 Winter Petrozavodsk Camp, Day 4: KAIST+KOI Contest to the CF Gym.
Problems are from KAIST 12th ICPC Mock Competition, with the exception of A, B (KOI 2022 Finals), and C (hard to explain).
Problems are authored by:
- ABC: ko_osaga
- D: circle-oo, queued_q
- EKL: mo_onrabbit2
- F: mo_onrabbit2 Worteltje Retro3014
- GI: Worteltje
- J: queued_q
- HM: kclee2172
I could be wrong, and I wish I am, but it feels like this is the last camp contest I will organize. Hope you had fun participating in the contest, as much as I enjoyed preparing the contest so much!
List of relevant previous contests
Nice problems, thank you for the authors.
How to solve G?
The following strategy works: Remove $$$k-1$$$ edges from the tree, find the diameter for each $$$k$$$ component, and connect them with the deleted $$$k-1$$$ edges.
Then you can run DP on tree, where the arguments are: (vertex $$$v$$$, number of completed component $$$k$$$ in subtree of $$$v$$$, how many endpoint of diameters are selected in the "open" component containing $$$v$$$). You can redeem an edge if you select $$$1$$$ diameter endpoint or decide to complete the current open component.
$$$k$$$ can not exceed the number of vertices in subtree $$$v$$$, so it is well-known that this DP runs in $$$O(NK)$$$ time.
How did you solve problem I ?
The author didn't provide a tutorial, and I could not solve it yet. As I know, the intended solution is not different from the paper on the internet.