darkrace's blog

By darkrace, 9 years ago, In English

I am trying to solve the problem http://codeforces.com/problemset/problem/507/C .I understood the problem clearly and i saw this soltuion 9539221 .But i am not able to undertand the code clearly.What is the if statement in the code mean? pls help..thanks

  • Vote: I like it
  • -3
  • Vote: I do not like it

| Write comment?
»
9 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Because the maze is a perfect binary tree, there is only one path from the root to the exit.

What will happen if you go left while the exit is to the right according to the rules? Well, according to the rules you will visit other subnodes of that node up to the point when you are back at that node. Then you will visit the other half of that node up to the point when you are back at that node again. But now, you have visited both children of the node, so you go to the parent. This parent was on the path to the exit, so then you can just continue.

The amount of nodes that are visited can be calculated. Imagine a tree of height h, then the total amount of nodes is 1 + 2 + 4 + .... + 2^(h) = 2^(h+1) — 1 (wiki)

In short, if you go the other way than the path to the exit, you have visited 2^(h+1) — 1 nodes, and the current node, so in total 2^(h+1) nodes. Of course, if you go the right way, you visit 1 node.

In the submission you linked to, mjhun uses a variable k, which is used to show if you have to go left (k=0) or right (k=1). "(n>>h)&1" is used to determine if the exit is to the left (0) or right (1). For example if h = 3, then after subtracting 1 from n, n has a value between 0 and 7. If n has a value between 0 and 3, you have to go left the first time, else (4 — 7) right.

If these values are different, then you go to the wrong node, so you will visit 2^(h+1) nodes. After visiting these nodes, you have to go the same direction as before. For example: if you go left and the exit is to the right, after many steps you get back at the node, then you go right, so you will go left at the next iteration.

If these values are the same, you only visit one node, and you will go the other way the next iteration.

This process is repeated h times, and after each iteration you subtract 1 from h.

Hope this helps.