I used state machine concept. Identified 5 different states using two character combination. See this in my solution Explaination: State is represented by two state variables a and b. if the string is ending at b then a is zero (to indicate the end state). If a is not zero then a and b represent the last two point (character) states when b is not the end point, but a is the end point. So (0, 1) and (0, 2) means the good string is ending at character 1 and 2 respectively. The valid states can be (2, 1) when it is like (***21) and from b(1) the dog can jumps to a(2) and so a(2) is the end point, not the last character b(1). (2, 2) when it is like (**22) and dog is at the a(2) and b(2) is unvisited character. So moving to next character is like state transition, this will be clear by following example:
This is explained in the code. asked 17 Oct '16, 15:26

By making some "good strings" manually you can easily see that following two conditions should be hold
Now after determining these conditions you just have to form a dynamic programming solution in which at each index you have two choices , either swap the corresponding digits or don't. here is the link of my solution my_solution . P.S. I took digits "0 and 1" instead of "1 and 2" in my solution . answered 17 Oct '16, 19:15

After determining the condition for a good string, I used $dp[i][j][k]$ where $i$ denotes the current position, $j$ denotes the state of first string and $k$ denotes the state of second string. State of a string is either "free" (next letter can be either 1 or 2), "open" (there is a single 2 and thus the next letter must be 2) and "closed" (there was a pair of 2s before so the $i$th lettter must be 1). The state transitions are not hard once you get this idea. answered 17 Oct '16, 15:38

answered 17 Oct '16, 16:12
Nice ones, especially compared to mine (I wonder how such a mess might work at all) :D https://www.codechef.com/viewsolution/11847204
(17 Oct '16, 16:18)
^That was so clean. Good job!
(17 Oct '16, 16:20)

A pretty fast solution. https://www.codechef.com/viewsolution/11823381 The logic being that at any index i, if ai=bi then we don't need to look out for anything. Now we divide the two strings into partitions  each partition [i,j] such that ai=bi and aj=bj and ak≠bk for k belonging to (i,j). In such partitions we can derive some conditions based on observed pattern. These conditions fulfill all the requirements of a 'good' string. The conditions are clearly written in my solution. The problem was an adhoc one, with no special prerequisite. answered 17 Oct '16, 16:14
I also did something similar, dividing string into parts where ai=bi=1. https://www.codechef.com/viewsolution/11825823
(17 Oct '16, 19:30)

The state space is small  N x 3 x 3. You could hard code and solve as an adhoc problem, but a dp solution would be easier to understand. answered 17 Oct '16, 17:06

My solution did not pass all test cases only 6 but still my approach was as follows I identified some conditions the string must satisy to be a good string. 1) second last element of the string must be 1, if 2 it is a bad string 2) 2 cannot appear independently it must always appear as 221 (except as last element) So what I did was I looped through a[i] & b[i] dividing the elements into 'N' segments (a[p],b[p])>(a[q],b[q]) such that they are isolated by a[p1]=b[p1]=1 and a[q+1]=b[q+1].122122112211> 112211221221 each such segment can have 2 ways of swapping their elements. So n such elements have pow(2,N) ways of swapping. Also count the no: places where a[i]=b[i] as countident. elements at identical places can be swapped in pow(2,countident) ways So final answer=pow(2,N+countident) Also make sure that in cases where a[i]=b[i]=2,a[i+1]=b[i+1]=2,a[i+2]=b[i+2]=1 both countident and N will count them so that condition must be checked seperately. answered 18 Oct '16, 14:12
