EXUND - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest

Author: Shashwat Chandra
Tester: Shashwat Chandra, Bharat Goyal, Taranpreet Singh
Editorialist: Shashwat Chandra

DIFFICULTY:

EASY - MEDIUM

PREREQUISITES:

Depth-first search , Trees

QUICK EXPLANATION:

Note that we always remove the current leaves of the tree in every operation.
You can calculate the time at which every node becomes a leaf recursively and then print the number of nodes for which this time is <= K.

EXPLANATION:

First, let us solve the problem for K = 1. Observe that in this case, we should keep moving as long as we can which means until all the nodes with chips on them are leaves (nodes which have no children).

The proof is given below for the sake of completion.

Proof

For the sake of contradiction, assume the optimal solution involves covering a node which has a non-zero amount of children c_i > 0.

However, we could just move the chip to its children, changing the answer by c_i -1 which is a non-negative value.

So how do we use this to solve the problem for K > 1 ?

Observe that for K > 1 , we can treat the problem as K problems all with K_i = 1. This is pretty intuitive thus the proof is omitted.

Now the reduced problem is as follows -
You do K operations, in every operation you remove all the current leaves from the tree. Find the number of nodes that you will remove in total.

Define time(i) as the time when the i^{th} becomes a leaf, time(v) = 1 for all leaves v of the initial tree.

We can calculate time(i) recursively :

  • For all nodes u which are leaves of the original tree, time(u) = 1.
  • Otherwise for a node u with m > 0 children,
    time(u) = max(time(c_1), time(c_2), ... , time(c_m) ) + 1.
    Here, c_1,c_2, ... , c_m are the indices of the children of u.

Now, the answer is simply the number of nodes i for which time(i) <= K holds.

SOLUTIONS:

Setter’s Solution

Tester’s Solution

1 Like
2

@shashwatchandr @bharat2002 @taran_1407
During the creation of adjacency list why do we add parent node in the adjacency list of its children? Can’t we make an adjacency list named children and for every node add only its children to it? In this way we don’t have to put this condition if(i==p) continue; in the for loop. Is this right or wrong? Why?

3

The input provides a list of edges not the parent of each node hence you have to first store all the edges and then determine the parents.

1 Like
4

Oh! yes, my bad. But why do I get TLE?
https://www.codechef.com/viewsolution/27650921

5

You’re not clearing the adjacency list after every test case. By the last test case, you are actually doing a dfs on a random graph and not a tree.

1 Like
6

Got it!! Thank you very much.