PROBLEM LINK:
Author: Sai Sandeep
Tester: Aditya Shah
DIFFICULTY:
MEDIUM
PREREQUISITES:
Binary Search, Depth First Search
PROBLEM:
Given a tree with weights on vertices, and k, Find the minimum value of the maximum weight of subtree that can be obtained by partitioning the tree into k parts.
QUICK EXPLANATION:
Binary search the answer.
EXPLANATION:
We will first check for a given x, if we can partition the tree into k parts such that each part is less than or equal to x, and then binary search the answer.
Let’s root the tree at node 1. Say a subtree rooted at vertex v has weight <= x, there exists a cut in which no edge inside the subtree is used. This is because, we can replace that edge with the edge between v and it’s parent, the cut still satisfies the condition that all the subtrees have weight <= x
What if subtree rooted at v has weight > x and all the subtrees rooted at it’s children have weight <= x ? From our first observation, we have to cut some edges connecting v and it’s children. But which edges to cut ? Say we cut i of these edges, but we can cut the i edges such that the weights of subtrees that we cut is maximum, the condition still holds. So we should cut the subtees with large weights and we should cut as less as possible. Thus, we start from the least weight one and start adding up weights till the weight is <= x, once the total weight crosses x, we are forced to cut all the rest.
This gives a recursive algorithm to check if we can maintain all the subtree weights <= x. We run the previous algorithm and find the number of cuts required. If it’s >= k, then that x is not valid. By binary search, we find the smallest x that is valid.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here
Tester’s solution can be found here