RBTREE - Editorial

ad-hoc
easy
graph
lca
nov14

#1

PROBLEM LINK:

Author: Sunny Aggarwal

Tester: Sergey Kulik

Editorialist: Florin Chirica

DIFFICULTY:

easy

PREREQUISITES:

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

It’s all about parities

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

Solution not accessible… Showing access denied


#3

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.


#4

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


#5

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


#6

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


#7

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

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


#8

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


#9

Can you inspect this solution also. Only one subtask was giving WA and rest all were accepted. Can’t figure out the problem in this.
http://www.codechef.com/viewsolution/5345645


#10

Cannot figure out the problem.Please inspect the solution.
Solution


#11

Here it is!!

Fully commented solution:
link text


#12

Getting all cases I could think of right. Submitted 3 times… still couldn’t get any points. I checked against all test cases in above editorial but working for all and giving right answer but on submission getting WA. Any help would be appreciated.
http://www.codechef.com/viewsolution/5403607


#13

Hello all

If someone need setter’s solution here is the link…


#14

Can someone help me with the 2 test cases where my code fails to give the correct answer?
My solution: http://www.codechef.com/viewsolution/5648945

It would be really helpful.Thank You.


#15

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


#16

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


#17

yeah !! I am also inspired with that cool problem authored by lalit kundu :smiley:


#18

I am so sorry for that. Here is the correct link.
http://www.codechef.com/viewsolution/5336214


#19

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


#20

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…