Unofficial Editorial: Chef and Two String : CHEFTWOS

I used state machine concept. Identified 5 different states using two character combination.
See this in my solution


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:

  1. String is in state (0, 1) and the next character is ‘2’, then the new
    state would be (0, 2).

  2. Current state is (2, 1) and the next character is ‘2’, the new state
    would be (0, 2).

  3. Current state is (2, 1) the the next character is ‘1’ then the new
    state would be (0, 1).

  4. Current state is (2, 2) and the next character is ‘1’ then the new state
    would be (2, 1).

This is explained in the code.

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.

My code


Seeing other people’s solution, I guess my implementation was the best(very short).


@rachitjain: Well.


A pretty fast solution.

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 ad-hoc one, with no special prerequisite.

1 Like

Nice ones, especially compared to mine (I wonder how such a mess might work at all) :smiley:

^That was so clean. Good job!

The state space is small - N x 3 x 3. You could hard code and solve as an ad-hoc problem, but a dp solution would be easier to understand.

1 Like

I think you should see my solution if you are not very good in dp(dynamic programming)

By making some “good strings” manually you can easily see that following two conditions should be hold-

  1. always exactly two “2” will come together eg. 1221 but not “2222 or 1211”.
  2. always second last digit of strings should be “1”.

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 .


I also did something similar, dividing string into parts where ai=bi=1.

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
such that they are isolated by a[p-1]=b[p-1]=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,count
ident) 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 count
ident and N will count them so that condition must be checked seperately.

1 Like

codechef is very slow in updating editorials

1 Like