×

easy

observation, dp

# PROBLEM

A string $s$ is called $good$ if you start at the first character and can reach the last character by applying the below moves repeatedly, visiting each character exactly once in the process. When you are at character '1', you can move one step to the left or to the right, similarly at character '2', two steps left or right. The string consists of only 1's and 2's.

In the problem, you are given two string $a, b$, each of length $n$. You have to find number of ways of swapping some subset of indices among them such that the resulting strings $a$ and $b$ both are $good$.

# QUICK EXPLANATION

A string $s$ will be $good$ if it contains 2's, then they should occur as a pair. Also, the string should not end up with $22$

This observation can be used to get a dynamic programming solution.

# EXPLANATION

## Characterization of $good$ string

Let us take some examples.

Trivially, any string of length 1 is $good$, i.e. "1" and "2".

String "11" is also $good$, as you start from first character, you have a character '1' at this position, so you can move one step to the right and end up at the last character. During this process, you visited both first and second characters exactly once.

The string "12" is also $good$.

However the string "21" is not $good$, as you can't go anywhere from the first character, so the second character will never be visited.

The string $22$ is not good.

Now let us first make some observations.

Last character of the string does not matter in the deciding whether it is $good$ or not. As for a $good$ string, we want to end up at the last character, i.e. after landing at last character, we won't be making any more moves. So the last character of string will be unused in making any decision about moves.

Assume currently you are position $i$, and if consecutive two or more of positions $i, i + 1, i + 2 \dots$ are visited. In that case, you can not move in the right direction from position $i$. This is due to the fact that in each move, you can take at most two steps.

The character set of the string is very limited, it contains either '0' or '1'. This restricts our movement a lot. Imagine you are at some character, and you were not able to visit a position that is two or more steps left to it. You will never be able to visit it, along with satisfying all the conditions for a string to be $good$. The idea is if you go back, you won't be able to come back again without revisiting some characters. This can be understood from the observation stated in the previous paragraph.

This motivates us to think that our movement should be almost going from left to right, with a few deviations if possible, but all those deviations will be at most one position to the left. This deviation is only possible in the case when you have come from position $i - 2$ (s.t. $s_{i - 2} = '2'$) to position $i$ with $s_i = '1'$ and $s_{i - 1} = '2'$, so that you after landing at $i - 1$, you can go position $i + 1$ from there.

This leads to us to make a speculation - A string will be a $good$ if it does not contain more than two consecutive 2's. Also, there will a separate case to consider when the string ends up two 2's. In that case also, the string won't be $good$.

This is indeed true. It is easy to see that if the string satisfies this property then string will be $good$. From the previous discussion, we can see that in all other cases, the string will be $bad$. These cases are namely, if the string contains groups of single 2's and more than one 2's. We have already proved that string will be bad in both these scenarios.

A string $s$ will be $good$ if it contains 2's, then they should occur as a pair. Also, the string should not end up with $22$.

## Final Solution

Finding number of ways of swapping subsets of indices in string $a$ and $b$ to make both of them $good$ can solve using dynamic programming and the above definition of $good$ string.

We iterate over both $a$ and $b$ simultaneously in order from left to right. Suppose we are at index $i$ and till now the parts of both the strings $a, b$ are $good$ (i.e. $a[0, i - 1], b[0, i - 1]$ are $good$). Now, we have two choices for position $i$. We make a swap of $a_i, b_i$ or we don't. What information should we keep as a part of state in the dp solution, so that after processing position $i$, we can ensure that the strings $a[0, i], b[0, i]$ are $good$.

According to definition of $good$ string, it should not contain more than two consecutive 2's. So, we should maintain that count of 2's that are at the end of strings $a[0, i - 1]$ and $b[0, i - 1]$. As we know that both of these strings are $good$, so the count of 2's can be either 0 or 1 at max.

So our dp state will be $dp[i][cntTwosInA][cntTwosInB]$.

The transitions of this dp can be done easily. At position $i$, we have two possibilities, to swap or not to swap. For both of these possibilities, we check that for $a$ and $b$, if the character at position $i$ is '2', then the corresponding $cntTwos$ should be $1$. If it is '1', then we should make sure that current character is not '2'.

Don't forget to check that in the end, there should not be two 2's in either $a$ or $b$.

Time complexity of this solution will be $\mathcal{O}(n * 2 * 2)$ (for states) $\times$ * $\mathcal{O}(1)$ (for transitions) = $\mathcal{O}(n)$.

# EDITORIALIST'S SOLUTION

Can be found here.

# TESTER'S SOLUTION

Can be found here.

This question is marked "community wiki".

2.5k52135169
accept rate: 20%

19.5k348496535

cannot view setter's and tester's solution. @admin

(19 Oct '16, 22:24)

 1 In the paragraph starting with "Assume currently you are position i" it should be - you cannot move in the right direction from position i. In the very next paragraph it should be - it contains either '1' or '2'. answered 19 Oct '16, 13:19 3★totodile 11●1 accept rate: 0% Thanks, corrected. (20 Oct '16, 06:57)
 0 unable to access the solution by both setter and tester answered 19 Oct '16, 14:59 1 accept rate: 0%
 0 Here is my solution with NO DP and No states. Just simply use a loop considering both string in O(n) time, You just need to find the pattern or analyse it on copy paper.. Solution answered 19 Oct '16, 15:17 2.8k●1●4●17 accept rate: 16%
 0 If it is '1', then we should make sure that current character is not '2'. This isn't clear. Could you explain it? answered 27 Oct '16, 00:03 2★fanatik 1●1 accept rate: 0%
 0 It can be done without DP also. First let us append 1 to both the strings in the starting and remove the last element. This will give us the same output because, if we had not done the above operation if a good string is possible we can swap the last element in each of the arrays as they are insignificant. After performing the above operation(appending 1 and deleting the last element of each string), we can swap the first element of both the array as they are same, but we cant swap the last one (as we removed it). So, performing the operation doesn't change the count. Now, we have an array of pairs of length n. We check if the last pair is (1,1) or not. We proceed if it is cout<<0 otherwise. Also we make sure that no triplet of 2s in the new A[],B[] exists. We cout<<0 if a triplet or more of 2s exist. We proceed otherwise. We know that if there exists a 2, it must exist as a couple for a string to be good, and there can't be a triplet or more. So now, we start from the first pair which is (1,1) (as we had appended it in the starting). We go on traversing till we reach a pair in which both elements are equal. Remember, in the path that we are traversing, from i to j suppose, from i+1 to j-1, all pairs have (Ak,Bk) (i0 we increment the count which was initially 0. Now we increment the count by the number of pairs Ai,Bi where Ai = Bi. Answer is 2^count%mod. Note that this is performed in the new array of pairs. answered 27 Oct '16, 12:49 221●1●4 accept rate: 33%
 0 i am not clear with how are you checking the combination because there can be alot of them please try to explain the last paragraph and how is that implemented in the loop j and loop k in the testers solution answered 27 Oct '16, 13:02 101●4●11 accept rate: 16%
 0 I think this is badly phrased A string s will be good if it contains 2's, then they should occur as a pair. For example, a string like this '..2222....' contains 2's in pairs- (2,2) and (2,2), although it is bad. As mentioned somewhere else in the editorial, a better way to put it would be that every contiguous sequence of 2's must be of length 2 for the string to be good. answered 03 Nov '16, 16:30 5★noob333 104●1●4 accept rate: 0%
 0 @dpraveen Why haven't you mentioned the fact that the string must not end in 221? answered 20 Dec '16, 23:44 143●1●6 accept rate: 10%

# If there is a string like 221121 will it be good ?

2★vchhabra
1059
accept rate: 12%

 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,029
×3,469
×1,901
×62
×20

question asked: 19 Oct '16, 12:41

question was seen: 5,082 times

last updated: 26 Oct '17, 22:08