GRAPART - EDITORIAL

general
, , , , ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2

Setter: Praveen Dhinwa
Tester: Xiuhan Wang
Editorialist: Taranpreet Singh

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

  • It is always possible to find a bipartition with k = 2 such that all the nodes are connected.
  • The idea is, that for each node, we need to color nodes in the subtree of this node in a manner such that |W-R| \leq 1. To be precise, if the number of nodes in the subtree of a node is odd, |W-R| = 1, Otherwise W == R where W and R denote the number of white and red nodes respectively.
  • To ensure that the resulting bipartitions are connected, each non-leaf node shall have a child of opposite color.
  • Corner case is when it is possible to find bipartitions of the tree itself with k = 1. It happens when the number of vertices at odd depth is the same as the number of vertices at even depth, both of them being N/2. This case can be handled separately.

EXPLANATION

For 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.

  • We shall maintain an invariant that for node u if the number of nodes in the subtree of u is odd, number of white nodes excluding node u is same as the number of red nodes, otherwise, number of white nodes is precisely same as the number of red nodes when node u is included.
  • Every non-leaf node has at least one opposite colored node as its direct child.

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. :slight_smile:

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 Complexity

Time complexity is O(N) per test case.

AUTHOR’S AND TESTER’S SOLUTIONS:

Setter’s solution
Tester’s solution
Editorialist’s solution

Feel free to Share your approach, If it differs. Suggestions are always welcomed. :slight_smile:

1 Like
2

Along the same lines, but a bit simpler solution:

  1. Color the root white
  2. Color all its children red
  3. Color all its grandchildren white
  4. … and so on, all can be done using DFS.
  5. If the number of white and red is the same, then k = 1;
  6. Otherwise k = 2 and just need to move sufficient number of leaves from one color to another to make number of nodes of each color equal.

Moving a leaf to a different color is equivalent to moving it up one level - the grandparent becomes the parent and the parent becomes a sibling. It is possible since skip connections are added for k=2.
Formally it also needs to be proven that there is always sufficient number of leaves to move to balance the cuts.

5 Likes
3

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®, 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:

4

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.

5

superb explanation… I did exactly same thing :slight_smile:
Is official solution same ?

6

Can it be proven ?

7

@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?

8

Why do we assign color alternatively ?
Because we need to SAVE each and every edge from being deleted… So if We assign color in this way then all of the edges are kept as it is…

9

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 .

2 Likes
10

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

1 Like
11

@l_returns Yes, it can be proven that there is always enough leaves to move. Supose we call:

  • W: number of white nodes
  • R: number of red nodes
  • Wi and Wl: number of white internal nodes and number of white leaves, respectivily
  • Ri and Rl: number of red internal nodes and number of red leaves, respectivily.

Supose W>R. We need to prove that 2*Wl>=W-R (number 2 comes from the fact that a “move” changes the difference W-R 2 units).
So… W-R = Wi+Wl-(Ri+Rl) <= Wi+Wl-(Ri+Wi) == Wl-Ri <= Wl < 2Wl.

1 Like
12

You used
Rl>=Wi
How is Rl always >= Wi ?
( as you said Wi+Wl-(Ri+Rl) <= Wi+Wl-(Ri+Wi))

13

I did exact same thing. This one was quite nice use of DFS :slight_smile:

14

@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. W-R = 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: W-R<=Wl

15

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

16

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

17

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.

2 Likes
18

Why can’t we do bfs coloring?

19

exactly true… getting it now… easiest proof :slight_smile:

20

Now I need proofs for wf<=Rl and Wo<=Ro+Rf XDD…