PROBLEM LINK:
Author: Denis Anishchenko
Tester: Hasan Jaddouh
Editorialist: Sarv Shakti Singh
Difficulty: Medium
Prerequisites: dfs(or bfs)
Problem: Given a tree of N nodes, you need to partition the edges into (N-1/3) sets such that each set contains edges of the form ((a,b),(a,c),(a,d)), or tell if it is impossible to do so.
Quick Explanation: The answer is NO if the number of edges is not divisible by 3. Consider the following two images: A and B. Now, we need to remove edges from the tree of the form as shown in them. We need to recursively find a node which has three or more children that are leaf nodes(Image A), or a node which has exactly two children which are leaf(Image B). Once, we find them, remove these edges marked E1, E2, and E3, and then repeat the process, until no edges remain. Or print NO if at some stage, there exist no such nodes.
Explanation: For the sake of simplicity, let’s call the set of three edges ((a,b),(a,c),(a,d)) as 3C-set (3-connected edges set). It can be seen that the best way to guarantee optimality by removing a 3C-set is in such a way that after removing this set, the tree does not split into two or more subtrees. So, we will try to remove this set from leaf nodes. Suppose we root the tree at any vertex, (say at vertex 1). Then, each node can be represented by a level l having values from 0(root) to L(max-depth node).
Now, let’s select any node v of the deepest level L. It has a parent u at level L-1. For an answer to exist, we need to associate edge (u,v) with two other edges. Since v is a leaf node, it does not have any other edge. Now, one of the following three conditions occur:
-
If vertex
uhas no other children i.e.uhas only one child, the edge cannot be associated and hence the answer isNO. -
If
uhas just one extra child(sayv') i.e.uhas total two children, we can associate edge (u,v) with edges (u,v') and (u,parent(u)) and remove them from the tree. [Removing 3C-set of type Image B] -
If
uhas greater than or equal to three children(sayv,v1,v2,…), we can associate edge (u,v) with edges (u,v1) and (u,v2), and remove them from the tree. It is sure thatv1,v2,v3,… are all leaf nodes at level L, because if they had a child, it would be at levelL+1and we would have selected that node asvto begin with because then, this node would have been at the deepest level. [Removing 3C-set of type Image A]
Hence, 2 and 3 always ensure that even after removing the edges, the tree never splits into two or more subtrees which has at least one edge.
This is what is needed to be done repeatedly until all the edges have been removed. It can be done using a dfs or a bfs. The editorialist’s solution is that of a dfs implementation. In that, starting from the root, we explore the tree until a deepest leaf node is hit and check if the parent of that node has how many spare children. And then build up the answer from the deepest level to the top.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.