# RBTREE - Editorial

Author: Sunny Aggarwal

Tester: Sergey Kulik

Editorialist: Florin Chirica

easy

graph theory

### PROBLEM:

You’re given an infinite complete binary tree. If a node has a color, its sons have complementary color. You need to perform some operations: either swap colors or answer how many nodes have a given color on a path.

### QUICK EXPLANATION:

The idea is the distance from a node x to the root is at most log2(x). Also, we can notice the tree is uniquely determined by the color of the root. Using those observations, we can keep a variable for the color of the root and apply brute force for solve queries.

### EXPLANATION

Let’s suppose the root of the tree has a color. Then, its sons will have different color. Also, the son of sons will have different color compared to sons. Since there are only two colors, this means sons of sons will have the same color as root.

Let’s define level of a node by distance from the root to that node. The only node at level 0 is root. The nodes at level 1 are the sons of root. The nodes from level one have different color from the root. The nodes from the level 2 (sons of sons) have the same color of the root. Also, the nodes from level 3 have different color from the root.

We can observe that if the parity of the level is 0, node has same color as the root. Otherwise, node has different color by the root.

Number of nodes from a path having a given color

This is a standard problem: count number of nodes from a given path having some property. Usually, in a tree to count something from a path from x to y, you count from the root to x, then add result from the root to y and subtract result from the root to LCA(x, y).

count(x, y, color) = count(root, x, color) + count(root, y, color) - 2 * count(root, LCA(x, y), color) + (1 if color(LCA(x, y)) is equal to color).

By LCA(x, y) I noted lowest common ancestor between x and y. Why does it work the formula? It’s clearly that count(root, x, color) + count(root, y color) counts the nodes from the path from x to y. However, it counts something more… it counts also number of nodes from root to LCA(x, y). It counts this once calling count(root, x, color) and once calling count(root, y, color). So, we need to subtract 2 * count(LCA(x, y), color). Now, it is still not good… Node LCA(x, y) is not counted at all now! However, it should be counted exactly once. So we can check if node LCA(x, y) has wanted color and if so, increase the result of count by 1. Now, the formula should be good.

Subproblem: how to implement function count

Let’s suppose we get all nodes from path from root to node x together with their levels. Then, it’s simple to count how many nodes have a given color.

1. If root has the same color as color variable, we need to count how many nodes have parity of level even.
2. Otherwise, we need to count how many nodes have parity of level odd.

All we need to do is, for a node x, to find its parent. Then, repeat the procedure for its parent. We know that node x is either 2 * k or 2 * k + 1. So k = x / 2. After 1 step, parent becomes x / 2. After two steps, parent becomes (x / 2) / 2 = x / 4. After s steps, x becomes x / 2 ^ s. Since our root is node 1, we’re interested in all nodes such as x / 2 ^ s >= 1. This means x >= 2 ^ s. Since x <= 10^9, it means 2 ^ s <= 10^9. So we get worst case, s = log2(10^9). This means, going up in the tree takes at most log2(10^9) ~ 31 steps until it reaches the root.

Since we do at most 31 steps, we can afford to find all nodes from path from node x to the root. We can also afford to find level of node x. Then, after each step, level will decrease by one, so it will be found in O(1). Since we have nodes and levels, we can easily count how many nodes have a given color from path from root to node x.

Handle operations Qi

We can keep a variable rootColor, initially BLACK. When you apply a “Qi” operation, it’s like flipping color of the rootColor (BLACK -> RED and RED -> BLACK). All tree is uniquely determined by the color of the root, so it’s enough to simply flip rootColor variable.

Subproblem: find LCA(x, y)

This part is our last challenge to finish the task. We calculate LCA like doing a brute force. Please refer to official solution to see the details.

Complexity

Operation “Qi” takes only O(1) time, since you simply flip a variable. Operations “Qr” and “Qb” take O(log(max(x, y))) time, needed for going up in the tree.

### AUTHOR’S AND TESTER’S SOLUTIONS:

To be updated soon
To be updated soon

2 Likes

1 Like

Please check this solution. If you can give me some or one of the test cases where my code fails, that would be highly appreciated.
http://www.codechef.com/viewsolution/5336214
Thank you.

1 Like

Please see this solution. I have tried all combinations of inputs I can think of and the output seems correct, I don’t understand why am I getting WA.I would be very grateful if you can point out the error. http://www.codechef.com/viewsolution/5401226

1 Like

This link is for different problem, is it a mistake?

Please tell me what am I doing wrong - your code return 2 for input from problem statement - http://ideone.com/yepUD3

I found that this question is similar to BinTree of April long challenge 2014.

I used that same logic, augmented colour to the code, it gave AC: ACed solution

1 Like

yeah !! I am also inspired with that cool problem authored by lalit kundu I am so sorry for that. Here is the correct link.
http://www.codechef.com/viewsolution/5336214

It prints `2` as an output for problem statement example - see here http://ideone.com/APdHId

I didn’t test it, but why `in` is of length 2? try to make it 5… Ok, and I tested it and this is first problem (same link), it also seems, that you print additional empty lines between the outputs…

Same as @thegreatheisenberg above - use `a` instead of `a`, in C, string is ended with `'\0'` and it’s a good habbit to alocate a little more memory than you need in contest programming…

http://www.codechef.com/viewsolution/5290532.
Take a look at my code. Have tried to explain it with comments.

1 Like

I tried using this method, but WA!
can anyone fix this?
http://www.codechef.com/viewsolution/5423114

For input:

``````14
Qb 1 2
Qr 1 2
Qb 1 4
Qr 1 4
Qi
Qb 1 2
Qr 1 2
Qb 1 4
Qr 1 4
Qb 4 5
Qr 4 5
Qi
Qb 4 5
Qr 4 5
``````

``````1
2
1
2
``````

ans should end with

``````1
2
2
1``````

Okay, so I printed an extra line after each output because earlier in the sample output it seemed to me that they wanted me to print an extra line due to their formatting, now they corrected it (and it seems the online judge ignores extra line between outputs).
Secondly, it worked after changing in to in (no need for 5), but I don’t understand the logic behind this. Is it because ‘in’ needs to take a null character at the end so I need to provide extra space for that? If that’s true then why did the program run correctly on my pc before?

Thanks for the help.

One of the test case is accepted and the others are not. Can any one tell why ?

http://www.codechef.com/viewsolution/5406843

1 Like

Getting all cases I could think of right. Submitted 11 times… still couldn’t get any points.
Any help would be appreciated. Also no issues as reported in earlier comments.
My solution:
http://www.codechef.com/viewsolution/5419500

1 Like

It returns 1 for input

``````1
Qr 12 28``````