Solution - Burza (COCI 2016)

#1

I was trying this problem and I AC it with bruteforce. But reading the editorial I’ve seen that there is a more efficient solution.

The problem asks you to find if by rooting a tree at node 1 and removing 1 node at each depth (except from the root) it’s possible to have a tree with maximum depth K (constraints: number of nodes , K <= 400).
In the solution there’s a short proof about why it’s always possible to do that if K >= \sqrt{N} but I don’t get some points in that explanation.
We are proving this:
n_r≤(k−r)^2
by induction, from the solution:
“Let’s define n_r as the total number of nodes that haven’t been made invalid yet after r moves, and t_r as the number of valid nodes Stjepan can move to after r moves (aka the number of valid nodes of depth r+1).”

The solution says that this formula: n_r≤(k−r)^2 is true for r=0 but it doesn’t seem to me? for example if k is equal to 1 and we have 10 nodes connected to node 1 the formula becomes 10≤(1)^2

1 Like
#2

We are assuming K\ge \sqrt N. If K=1 then N=1. How is it possible for the number of nodes connected to node 1 to be greater than N?

1 Like
#3

The “further analysis” section isn’t ordered in the most understandable way. I think it would be better to first

  • state what the concrete strategy is (always remove the largest remaining subtree)
  • give some intuition on why it works (consider why it works on a star-like graph with N up to K(K+1) but not K(K+1)+1)
  • and then prove why it works (if n_r<k(k+1) before some step, then n_r<(k-1)k after that step).
1 Like