Problem Link - Bytelandian Robots
Problem Statement
The Bytelandian Robotic Deparment has just succesfully made a robot that can be programmed to move. Our robot can perform two type of movements: moving one step to the left or one step to the right.
Our robot moves according to the instruction from its control sequence. A control sequence of the robot is a string consisting of only two type of characters: '+' and '-' symbols, in which '+' means a rightward step and '-' means a leftward step. For example, '+--' is a control sequence that instruct the robot to go one step to the right followed by two steps to the left.
Our robot also has a master control sequence (MCQ), which is a string of N characters '+' and '-'. Any valid control sequence of the robot must be a subsequence of the MCQ. Recall that a subsequence is a sequence obtained by removing some characters of the initial sequence. An empty sequence is also a subsequence of the MCQ.
Our robot is currently placed on a runway of length L, in which the leftmost point has coordinate 0 and the rightmost point has coordinate L. Intially our robot stands at the point at coordinate A. It needs to move to the point at coordinate B. Of course, it cannot go outside the runway.
How many different control sequences are there that make the robot go from A to B?
Approach
The solution uses dynamic programming with preprocessing. Precompute the next_plus
and next_minus
arrays to track the next occurrences of +
and -
for each position, along with plus_cnt
and minus_cnt
arrays to store cumulative counts. This allows us to determine the possible range of reachable positions, farthest_left and farthest_right.
The dp
table is defined where dp[x][i]
indicates the number of valid sequences that move the robot from position x
to B starting at command index i
. Iterate through the MCQ from the end to the beginning, updating the table based on whether the robot moves left or right. The result is stored at dp[A][0]
, representing valid sequences starting from A.
Time Complexity
The time complexity is O(N × R), where N is the length of the MCQ and R is the range of reachable positions.
Space Complexity
The space complexity is O(N × R), due to the dp
table storing states for all positions and command indices.