Approach Framework

Explanation

Let denote the command (k times).

Starting with an "R" command doesn't help, and as the final sequence does not end on an "R", so we have some sequence like which could be instead for the same final position of the car. (Here, , where means no command.)

So let's suppose our command is always of the form . Note that under such a command, the car will move to final position .

Without loss of generality, we can say that (, odd) is monotone decreasing, and (, even) is also monotone decreasing.

Also because terms will cancel out, we can also ignore the possibility that (for with different parity).

A key claim is that is bounded by , where is the smallest integer such that - basically, if you drive past the target, you don't need to keep driving. This is because it adds another power of two (as ) to the position that must get erased by one or more negative terms later (in whole or in part), as it is not part of the target.


Approach #1: Dijkstra's [Accepted]

Intuition

With some target, we have different moves we can perform (such as , using the notation from our Approach Framework), with different costs.

This is an ideal setup for Dijkstra's algorithm, which can help us find the shortest cost path in a weighted graph.

Algorithm

Dijkstra's algorithm uses a priority queue to continually searches the path with the lowest cost to destination, so that when we reach the target, we know it must have been through the lowest cost path. Refer to this link for more detail.

Back to the problem, as described above, we have some barrier where we are guaranteed to never cross. We will also handle negative targets; in total we will have 2 * barrier + 1 nodes.

After, we could move walk = 2**k - 1 steps for a cost of k + 1 (the 1 is to reverse). If we reach our destination exactly, we don't need the R, so it is just k steps.

Complexity Analysis

  • Time Complexity: . There are nodes, we process each one using work (both popping from the heap and adding the edges).

  • Space Complexity: .


Approach #2: Dynamic Programming [Accepted]

Intuition and Algorithm

As in our Approach Framework, we've framed the problem as a series of moves .

Now say we have some target 2**(k-1) <= t < 2**k and we want to know the cost to go there, if we know all the other costs dp[u] (for u < t).

If t == 2**k - 1, the cost is just k: we use the command , and clearly we can't do better.

Otherwise, we might drive without crossing the target for a position change of , by the command , for a total cost of .

Finally, we might drive which crosses the target, by the command , for a total cost of .

We can use dynamic programming together with the above recurrence to implement the code below.

Complexity Analysis

  • Time Complexity: . Each node i does work.

  • Space Complexity: .


Analysis written by: @awice.