PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: Utkarsh Gupta
Tester: Abhinav Sharma, Aryan
Editorialist: Lavish Gupta
DIFFICULTY:
Easy-Medium
PREREQUISITES:
None
PROBLEM:
Chef has two binary strings A and B, each of length N. He can perform the following operation on A any number of times:
- Choose L and R (1 \leq L \leq R \leq N), such that, in the substring A[L,R], the number of 1s is not equal to the number of 0s and reverse the substring A[L,R].
Find whether Chef can convert the string A into the string B by performing the above operation any (possibly zero) number of times on A.
QUICK EXPLANATION:
- If A and B are not anagrams, then the answer is NO
- If any one of A or B has only alternate 0's and 1's (like 101010 or 010101), then the answer is YES iff A = B, otherwise answer is NO
- Otherwise, there exists an index i such that A_i = A_{i+1}. Similarly, there exists an index j such that B_j = B_{j+1}.
- We can show that if there is an index i such that A_i = A_{i+1}, we can sort the string A using the above operations. Similarly, we can sort B, and because the operations are reversible, we can show that A can be converted to B (by first sorting A, and then following the operations used in sorting B in reverse order).
EXPLANATION:
Because the mentioned operation cannot change the number of 0's or 1's in the string, the answer will always be NO if A and B are not anagrams.
Now let’s say that for every i( 1 \leq i \lt N), A_i \neq A_{i+1}. In other words, A has alternate 0's and 1's. In this case, note that every even length substring has equal number of 0's and 1's, and therefore we can only reverse substrings of odd lengths. However, every odd length substring is a palindrome, and hence reversing it doesn’t modify A. In simpler words, we can never modify A using the above operations. So, the answer will be YES only if A = B, otherwise the answer will be NO.
Note that the operations are reversible, and converting A to B is equivalent to converting B to A. Hence, if B has alternate 0's and 1's, then the above argument holds.
Now we have an index i such that A_i = A_{i+1}. Similarly, we have an index j such that B_j = B_{j+1}. We will show that if there is such an index, then we can sort our string. If this is true, we can first sort A. Let S be the ordered set of operations which are applied to B while sorting it. Because of the reversible nature of the operation, we can apply the operations of S in the reverse order to string A, and get the string B. Note that this is true because A and B are anagrams.
Sorting string A when A_i = A_{i+1}
Without loss of generality, let A_i = 0
Bringing all 1's which are present on the left side of the pair to the right side
Let’s see this through an example. We will use 0-based indexing.
Let A = 1010001. Let us consider the pair \{ A_4, A_5\}. We will start iterating towards left until we reach the first 1. In this case, the substring would be 1000, where the last two 0’s represents our pair. We will always have unequal number of 0’s and 1’s as there is single 1, while at least two 0s.
We can reverse this substring, bringing the 1 towards the right side (and effectively shifting our pair towards left). We can continue this process to bring all the 1s towards right.
Bringing all 0's which are present on the right side of the pair to the left side
We will start iterating towards right until we reach the first 0 at k^{th} index. So, our substring is A_iA_{i+1} \ldots A_k , with A_i, A_{i+1}, A_k = 0.
If A_{i+2} \ldots A_k is valid, then we can directly reverse this substring. If not, then both A_i A_{i+1} \ldots A_k and A_{i+1} \ldots A_k are both valid. So, we can have A_iA_{i+1} \ldots A_k \rightarrow A_kA_{k-1}\ldots A_{i+1}A_i \rightarrow A_kA_iA_{i+1} \ldots A_{k-1}, and hence effectively bringing A_k to the left side.
If we have A_i = 1, then we essentially need to do the same thing. Hence we have shown that if there are two consecutive equal characters, we can sort our string, and therefore, we can convert A to B as explained above.
TIME COMPLEXITY:
O(N) or O(N \cdot \log{N}) for each test case, depending on the implementation.