Notes on SRM 590, D1, 250-Pointer (FoxAndChess)

Mon Sep 9 12:44:21 EDT 2013
Problem Statement.

First, try to do this one yourself; however, if you find yourself lacking inspiration, consider the following points:

Since the L's and R's can't cross each other, if you strip the dots from begin and target, they should equal each other. So, create two strings: B, which is begin without the dots and T, which is target without the dots. If B doesn't equal T, return "Impossible." That will help you write code later that does not seg fault.
Now, each character in B corresponds to a character in begin. Create a new vector bi of ints, where bi[i] is equal to the index in begin of the character that corresponds to B[i].
For example, suppose begin equals "..R.L.RR.". Then B equals "RLRR", and bi equals { 2, 4, 6, 7 }.
Create ti, which is like bi, only for target and T rather than begin and B.
Can you see how to finish the problem using B, bi and ti? Think about it before moving on.
The solution is this:
- If B[i] == 'L', then ti[i] must be less than or equal to bi.
- If B[i] == 'R', then ti[i] must be greater than or equal to bi.

Hack it up.