ko_osaga's blog

2022-2023 Winter Petrozavodsk Camp, Day 4: KAIST+KOI Contest
By ko_osaga, history, 20 months ago, In English

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:

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
  • Vote: I like it
  • +84
  • Vote: I do not like it

»
20 months ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

Nice problems, thank you for the authors.

How to solve G?

→ Reply
  • »
    »
    20 months ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

    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.

    → Reply
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How did you solve problem I ?

→ Reply
  • »
    »
    19 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply