MOVING ROBOTS

Solution

Lets call robot’s state ( state - position and direction in that position ) reachable iff
the robot can reach that state by performing some subsequence of its original sequence of commands. For every reachable state exists the longest subsequence of commands that drives robot to that state. Lets call the length of that subsequence the length of the
reachable state.
For every robot we calculate set of reachable states and their lengths. That calculation can be done in the following way based on dynamic programming idea. For every k  from 0 to n ( n - the length of the robot’s original sequence of commands ) we calculate reachable states and their lengths considering only subsequences of the first k commands of the original sequence - lets denote that set S(k) = {<s(k,i), l(k,i)> | i=1,...,P(k)}, here s(k,i) is a state and l(k,i) - its length. Initialy we have S(0) = {<s(0,1), l(0,1)>}, here s(0,1) is initial robot’s state and l(0,1) = 0. To perform calculations for k = 1, ..., n we use results of  (k-1). First set S(k) = S(k-1). Then S(k-1) is iterated and from every s(k-1,i) (i=1,...,P(k-1)) we perform the command with number k in the original sequence. If resulting state is not present in S(k), then it is added with the length l(k-1,i) + 1. Otherwise there exists (exactly one)  j that <s(k,j), l(k,j)>  is element of S(k), s(k,j) = s(k-1,i) and we set l(k,j) = max ( l(k,j), l(k-1,i).l + 1).
We should examine the set of positions that are reachable by all robots. If this set is empty then there is no final common position. Otherwise we examine every common position. For every robot we select the state which has the given common position and which length for that robot is maximal. Then the common length of the common position is the sum of lengths of these states. The common position with maximal common length
is optimal and the number of commands to be removed  in order to reach that position is ( n(1) + ... + n(R) - [common length of the position] ), here n(r)(r = 1, ..., R) is  the length
of the robot's original sequence of commands.