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]
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.
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
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
u < t).
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.
Time Complexity: . Each node
Space Complexity: .
Analysis written by: @awice.