The problem is one of the easiest in the set. The solution is as follows.

When we have an odd-length string S, we can make one turn and set some flag the the answer is even. Otherwise, we should keep in mind than the answer is odd.

The remaining part always has even length, and we can threat the tree as the octary one and numerate the nodes by consecutive natural numbers. When we have found the node number in this tree, we will only need to multiply it by two and possibly to subtract one. The tree is octary, so the consecutive symbols can be grouped in pairs and each pair will denote a single edge of the tree. Namely, in the order from left to right the order of pairs is âllâ, âlrâ, ârlâ, ârrâ.

So we just maintain the variable index and each time we traverse one edge of our tree, we multiply it by 4, and then add -2, -1, 0 or 1, depending on the type of the edge: -2 for âllâ, -1 for âlrâ and so on.

At the end we just need to find the index-th even (or odd) number. The parity depends on the parity of the length of the string that denotes the path.

For each level, keep a counter whether the level number is odd or even.

We have ans = root = 1

Now traverse through the string.

If the next character is 'l' and we are on an even numbered level -
ans = ans x 2
else if the next character is 'l' and we are on an odd numbered level -
ans = ans x 2 - 1
else if the next character is 'r' and we are on an even numbered level -
ans = ans x 2 + 2
else if the next character is 'r' and we are on an add numbered level -
ans = ans x 2 + 1

Please someone let me know whatâs wrong with my code http://www.codechef.com/viewsolution/4811858 I followed the same method, and it worked for provided test cases, but on submission, it keeps showing wrong answer.

here I want to mention something which you may havnât taken care
first one when you are taking mod some even level value may be convert into odd value because there are so many times mode happen thatâs why you should a separate variable for keeping track of level or you can use index also

second one may be your root[i] is exact multiple or equal to mod than root[i]%mod=0 later (may be )2*root[i]-1 become negative

here I want to mention some points which you may havnât taken care

POINT 1

first one when you are taking mod some even level value may be convert into odd value because there are so many times mode happen thatâs why it is possible

Solution 1

you should a separate variable for keeping track of level or you can use index also

POINT 2

second one may be your root[i] is exact multiple or equal to mod than root[i]%mod=0 later (may be )2*root[i]-1 become negative