PROBLEM LINK:Practice Setter: Praveen Dhinwa DIFFICULTY:Medium PREREQUISITES:Observations, Invariants and Constructive Algorithms. PROBLEM:Given a tree $G$ with $N$ ($N$ is even) number of nodes, we can make Graph $H_k$ by adding an edge between every pair of nodes which have distance up to k. We need to find the minimum $k$ such that we can split all nodes into two disjoint partitions of size $N/2$ such that if considering the edges of the graph $H_k$ having both ends in different partitions, all the nodes are connected. Also, print one such valid bipartition. Note: I shall use the color white to represent a node in the first partition while red to represent a node in the second partition. SUPER QUICK EXPLANATION
EXPLANATIONFor $k = 1$. The only possible bipartition which is connected is the one where nodes with odd depth are colored white while nodes at even depth are colored red. But the number of white and red nodes may not be equal. So, for the trees where the number of nodes at odd depth is same as the number of nodes at even depth, we can directly print this bipartition with $k = 1$. For rest cases, we need $k \geq 2$. It can be proven that $k = 2$ is sufficient for any tree. Lemma: Nodes in Graph $H_2$ can always be colored white and red such that considering edges with opposite colored ends only, all nodes are connected. Proof: We shall prove it subtree wise, by the principle of induction. We shall maintain the following invariants.
Considering the base case, where node u is a leaf, we can simply color it white, thus invariant is maintained. Now, If a node has only one child, let us color the node as opposite of its child node. It can be seen that the first invariant automatically holds here. Now assuming all the children of node u maintain this invariant, let us prove that we can maintain this invariant for node u too. Considering children of u, the ones having even subtree size. We know that the number of white nodes in its subtree is the same as the number of red nodes, while the ones having odd subtree size, have exactly one colored node more. We first need to flip the color of subtrees of some children, until the absolute difference between the number of white and red colored nodes is minimum. An important point to note is, that we can flip subtree at node u without breaking any invariant. If the node has even subtree size, the number of white and red nodes isn't affected, while if subtree size is odd, the number of one colored node increases by 1 and other colored node decreases by 1, thus causing the absolute effect of 2 nodes. So, It makes sense to flip subtrees with odd subtree size, till the minimum is achieved. Now, if subtree size of node u is even, node u shall be colored to make the number of white nodes same as the number of red nodes since absolute difference after flips would be 1. Otherwise, we can color node u any color, but before that, we need to balance white and red nodes in the subtree of u excluding u, which can be achieved using flips. To maintain the second invariant, we can find one child with even subtree size and if required, flip it to ensure it has opposite color as node u. If no child has even subtree size, the second invariant is automatically holding. You can prove it easily. :) Hence, this proves by induction that it is possible to maintain these two invariants which not only ensure the existence of valid bipartitions but also give one valid bipartition. Flips can be separately handled in separate DFS by maintaining a flipped array. After handling cases, Implementation shall be easy, which can be referred in solutions below. Time ComplexityTime complexity is $O(N)$ per test case. AUTHOR'S AND TESTER'S SOLUTIONS:Setter's solution Feel free to Share your approach, If it differs. Suggestions are always welcomed. :)
This question is marked "community wiki".
asked 14 Jan, 16:18

The easiest solution is my own. First, use preorder traversal for K=2 case. Assign one color to all the odd elements and another to all the even. What is important is that the first child of every node has a different color from the parent. The all other nodes would be able to find the opposing color by looking at its parent and the same color by looking at the first child of its parent. answered 15 Jan, 11:13

Here is a sketch of proof of why rerooting the leaves always work : Pair every unpaired node with a child of it. At the end only (some) leaves remain unpaired and since each paired node has a parent/child of the opposite color , we can ignore it. Thus it is sufficient to only look at the (unpaired) leaves and make them equal as described by @shoom . answered 14 Jan, 23:19

Similar to shoom as well. Firstly, for each node, record all the "leaf children" (children with degree 1). Next, start a DFS with a node, and a side. Recursively add children to opposite sides. Eventually, if the nodes are not equally distributed, then iterate on the smaller group, and for each vertex, try adding its leaf children (one by one) from the larger group to itself until the group sizes are the same. Link to solution https://www.codechef.com/viewsolution/22465500 answered 14 Jan, 23:21

@l_returns Yes, it can be proven that there is always enough leaves to move. Supose we call:
Supose W>R. We need to prove that 2*Wl>=WR (number 2 comes from the fact that a "move" changes the difference WR 2 units). So... WR = Wi+Wl(Ri+Rl) <= Wi+Wl(Ri+Wi) == WlRi <= Wl < 2Wl. answered 15 Jan, 00:02
You used
(15 Jan, 00:12)
@l_returns Sorry, my bad, that's not true. Let's try this. Split the internal nodes in fathers of a leave (Wf) and father of another internal node (Wo). Now, 1) WR = Wo + Wf + Wl  (Ro + Rf + Rl) <= Wo+Wl(Ro+Rf); because Wf<=Rl 2) Wo+Wl(Ro+Rf) <= Wl; because Wo<=Ro+Rf (Wo is father of Ro's and Rf's) 3) Following 1 and 2: WR<=Wl
(15 Jan, 02:50)
Now I need proofs for wf<=Rl and Wo<=Ro+Rf XDD....
(15 Jan, 12:52)
thanks though....
(15 Jan, 12:53)
that is easy, Wf are the fathers of Rl, so wf<=Rl; Wo are the fathers of Ro and Rf, so Wo<=Ro+Rf
(15 Jan, 14:34)

My solution, Similar to shoom (WA, but I'm unable to find a counter example yet) Color root node White (W), all White children Red(R), all Red children Blue(B), all Blue children Green(G) and all Green children White. If W+B = R+G then k=1 and groups are W+B and R+G If they are not the same then let (WLOG) W+B > R+G and let (WLOG) W>=B. We can then show that with k=2 there are enough W nodes to move across to the right group such that they have the same number of nodes. Since there must always still be a B node on the Left that's 2 away, thus still keeping the graph connected. I'd like to know where I went wrong in my solution, if anyone can help me I've asked about it here: https://discuss.codechef.com/questions/143751/isthepartitionthegraphcheckercorrect answered 14 Jan, 20:31
Did you mean "let W>=B and move enough W nodes to the right" (since W+B > R+G)? Just try it on many random trees and check the solutions. There must be some counterexample, since it produced WA.
(14 Jan, 21:19)
Sorry that's what I meant, I struggled with this for 2 days and couldn't get why my solution did not work. Anyway I'll just have to give up on it I guess
(15 Jan, 02:53)

@linjoehan How do you choose which nodes to change color? As I understand, there are certain constraints on which nodes you can move. What if there is no G that is 2 away? answered 14 Jan, 22:17

Actually, I think I can add something here. What I did was, if answer was $K=2$, then do a simple DFS. In DFS, keeping assigning nodes one by one, first to $U$, then next to $V$, then next to $U$ and so on. I identified $4$ cases, but they can be further reduced 
The intuition in cases was enough for me to give this approach a try. The proof I feel, is based on proving that the root node of subtree is connected either to its immediate next child, or to its grandchild (which in turn is connected its parent) in each of the $4$ cases. answered 15 Jan, 15:22

I must admit, before you realize that K is no greater than 2, the problem description looks intimidating. :)