If you try to directly simulate Takahashi’s movement, storing the index of vertex he is currently at, the number of digits of index of vertex will be too large, so it will lead to TLE.

How to simulate it efficiently?

Solution 1

If L or R is immediately followed by U, then he goes back to the original vertex after these two moves, so such consecutive moves can be ignored. We can inspect \(S\) in order to remove all such parts in a total of \(O(N)\) time using a stack.

Let \(S'\) be \(S\) with all such parts removed. Then \(S'\) is “a string of length \(0\) or more, consisting only U” followed by “a string of length \(0\) or more, consisting of L and R.” During the process by \(S'\), the index of vertex does not exceed \(\max(\text{Initial vertex},\text{Final vertex})\). Therefore, we can manage the index of vertex that Takahashi is currently at, and directly simulate the moves, so that the problem is solved fast enough.

The time complexity is \(O(N)\).

Sample code (Python)

Solution 2

Consider managing the index of vertex that Takahashi is currently at with a string \(T\) containing the binary representation of the index. Then, each move updates \(T\) as follows.

• If it is U, remove the last character of \(T\)
• If it is L, append 0 to the tail of \(T\)
• If it is R, append 1 to the tail of \(T\)

All of these operations can be done in an \(O(1)\) time each. Therefore, this problem can be solved fast enough. The overall time complexity is \(O(N+\log X+\log {\rm Answer})\), because binary representations and integers are mutually converted at first and in the end.

Sample code (Python)