GRAPART - EDITORIAL

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- CodeChef: Practical coding for everyone

1 Like

@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

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

Why can’t we do bfs coloring?

Flips can be separately handled in separate DFS by maintaining a flipped array.

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 -

  • When the root of this fully colored subtree is in U and last colored leaf is also in U
  • When the root of this fully colored subtree is in V and last colored leaf is also in U
  • When the root of this fully colored subtree is in U and last colored leaf is also in V
  • When the root of this fully colored subtree is in V and last colored leaf is also in V

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.

Here is a simpler and better solution.

2 Likes

This post is useful for my work, thanks

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.

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

Can it be proven ?

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…

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

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

@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

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

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

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

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

thanks though…

that is easy, Wf are the fathers of Rl, so wf<=Rl; Wo are the fathers of Ro and Rf, so Wo<=Ro+Rf