erray's blog

A Cool Tree Problem (Yea it's a creative title)
By erray, 19 months ago, In English

The Problem

You are given a tree with $$$N$$$ ($$$1 \le N \le 10^5$$$) vertices.

You need to partition the vertices into minimum number of sets, such that every set has a maximum size of $$$S$$$ ($$$1 \le S \le N$$$) and maximum distance between any of the two vertices, that are in the same set is less than $$$2K$$$ ($$$1 \le K \le 20$$$).

With a more formal statement, assuming vertices in the tree are labeled $$$[1, N]$$$ and $$$dist(v, u)$$$ is defined as the distance between two vertices in the tree, you need to find a partition $$$ \{ P_0,\, P_1,\, \dots ,\, P_{C-1} \} $$$ with minimum $$$C$$$, such that:

  • for every $$$\displaystyle P_i, \ max_{\ \forall v,\ u \ \in P_i} \{dist(v, u)\} \le 2K$$$
  • for every $$$\displaystyle P_i, \ |P_i| \le S$$$
  • for every $$$\displaystyle 1 \le x \le N, \ x \in \bigcup P_i$$$

The problem doesn't want you to print the partition, you only need to print it's size (number of sets) and note that it's not necesseary for vertices in a set to form a connected component.

$$$ \ $$$

My manners
My ideas
  • Vote: I like it
  • +62
  • Vote: I do not like it

»
19 months ago, # |
  Vote: I like it +28 Vote: I do not like it

Waiting for jiangly or any Chinese prodigy, or simply the greatest ahmet23...

→ Reply
»
19 months ago, # |
← Rev. 2   Vote: I like it +34 Vote: I do not like it

once upon a time, i claimed that the people running this exam formed a cult

now with this, i stand behind my judgement even more firmly

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

I have feeling that you can get up to ~%72 points if the cases are not well prepared with cout << (n+s-1)/s << endl;

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

I guess there may be a greedy solution based on something like Chordal Graph Theory.

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

https://www.acmicpc.net/problem/8169 looks similar.

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

    Yeah, it was identical (I'll look into your code more carefully when I'm free, it looks like I'm missing something that makes merging subtrees pretty easy, thanks for the lead)

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

I think there is a typo. There should be $$$max_{\forall v,u \in P_i} dist(v,u) $$$ not $$$min$$$.

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

    You're right, sorry fixed it now

    → Reply