PROBLEM LINK:
Setter- Utkarsh Garg
Tester- Suchan Park
Editorialist- Abhishek Pandey
DIFFICULTY:
Easy
PRE-REQUISITES:
Basic Game Theory, Observation.
PROBLEM:
Given a string of 0's and 1's - you can perform the following operation-
- Remove a 1 and flip its adjancent elements from 0 to 1 and vice versa.
Tell if its possible to remove all characters of the string or not.
QUICK-EXPLANATION:
Key to AC- Realize that its all a game of parity!
After some trivial observations, we will see that the answer is always WIN if number of 1's in the string is odd. Else the answer is always LOSE. The latter can be proved by a proof on lines of divide and conquer.
EXPLANATION:
We will divide the editorial into 2 cases, each of them proving one part of the Quick Explanation Section.
- Proof that answer is
WINif number of 1's is odd. - Proof that answer is
LOSEif number of 1's is even.
Before starting, lets first define the conventions used in the editorial. I will be using standard symbols of regular expression, but just for sake of clarity-
- 0^* - Means 0 or more occurrences of character '0'. Similar meaning for 1^*.
- 0^+ - Means 1 or more occurrences of character `0`. Similar for 1^+.
The question needed observations to solve, and hence editorial will consist of some hand-worked examples to see how the intuition can be developed.
When number of 1's is odd
Lets first discuss a base case. What will the answer be for strings of type 0^*1 and 10^*??? Note that, when I say 0^*1, I mean all strings with 0 or more character '0' s at beginning, ending with a 1. Some examples are [1,01,001,0001,...],
For both of these type of strings, we just flip the 1, and then its adjacent 0 becomes 1. We then flip that 1 and the chain goes on and on till the entire string is finished. Easy enough?
What about string 0^*10^*?? Here also, we just flip the 1, and both the 0's adjacent to it (if existing) become 1 and we carry on until the entire string is exhausted. Pretty nice.
Now, lets with multiple 1's and see what happens. Recall that we are currently dealing with the case of odd 1's in the string.
Let the indices where 1 occurs in the string be i_1,i_2,i_3,...,i_k, when going from left to right. Note that in our present case, k is odd.
(For visual purposes, or ease of imagination, take an exemplar string 0101010.)
Lets follow the following strategy-
- Flip the 1 at i_1. Since this is the first occurrence of 1 when going from left to right, there will not be any other 1 before it. Hence, all 0's occurring before i_1 will get exhausted easily.
- Lets focus on 0s occurring after i_1. What happens? Recall our base case of 10^*. Flipping the 1 at i_1 causes the next 0 (if any) to become 1 and then we flip it. This goes on and on until we reach index i_2, where another 1 occurs. This 1 will get flipped to 0 once we remove the card at index i_2-1.
- Look at index i_3. The 1 at i_2 got flipped to 0 now, and the next 1 after i_2 occurs at i_3. Recall our case of 0^*10^*. Hence, we make a flip at i_3 and carry on. As clear from our hand crafted examples, the characters in range [i_2,i_3-1], which are all 0's get exhausted. (Recall that i_3 is the index of third 1 when going left to right!).
Work it out for a string with five 1's? With seven 1's ?
Observe the pattern above. We flip from the leftmost 1, it keeps on removing characters till it encounters the next 1 at its right, which gets flipped to 0. But since the number of 1's is odd, there has to be one more occurrence of 1 to its right, which we can flip to ultimately empty the string.
Another crisp, short proof is given in the bonus corner 
Case when number of 1's is even
Now, the case when number of 1's was odd was easy. What if its even? Obviously our above strategy does not work. Lets first look at some base cases (There is honestly, just 1 base case, but let me break it up to make it easier for you )
-
0^+ - i.e. when there are zero 1's in the string. The answer is obviously
LOSE. -
10^*1 - This is a string of type [11,101,1000001]. Note that, the answer for this is also
LOSE, because no matter how you flip, the last to flip 1 will become a 0 when flipping the second last 1. -
0^*10^*10^* - This is also the above case only, except that there can be 0's at start and end of the string here, which anyway get eliminated. Following the flipping as above, we get the answer of
LOSEhere also.
Getting a LOSE on all base cases we make is a hint that we should explore if the answer for this case is always LOSE. Its always a good idea to first check for some more base cases, like strings with number of 1's equal to some other even number, like 4,6,8...etc. You can do try that right now if you like.
Lets start with the proof.
Let there be 1's at indices i_1,i_2,i_3,...,i_k where k is even. Consider a 1 at any of the given indices, say at index j. We will make cases on basis of what characters can be adjacent to this 1, hence let X denote the character to left of this 1, and Y denote the character at right of this 1.
Now, note that we are dealing with case where frequency of 1's in the string is even. If we remove the 1 at index j, then number of 1's will be odd. Without loss of generality, let there of odd number of 1's in subarray [1,j-1] and even number of 1's in subarray [j+1,N] where N is length of the string.
Now, lets make cases on basis of X and Y, i.e. characters at index j-1 and index j+1.
- X=0,Y=0 - On flipping the 1 at index j, both X and Y become 1 and the parity of left and right subarray changes. Now the left subarray has even 1's and right subarray has odd 1's. We can now exhaust each subarray independently (since after removing the 1 at index j, both the subarrays are disconnected!!!). The right subarray, with odd number of 1's is easily exhausted using our previous strategy. The left subarray is a smaller string with even number of 1's, lets get to it later.
- X=1,Y=0 - The left subarray loses a 1 and right subarray gains a 1. The same story said above repeats - i.e. the parity of both subarrays changes and we proceed as done above.
- X=0,Y=1 - Same as above.
- X=1,Y=1 - Again, the parity of both the arrays change as they both lose a 1. Same story repeats.
What happened above? We were able to completely exhaust one side of the array which had odd 1's and we got a smaller subarray with even number of 1's. Note that, since after removing 1 at index j both the arrays become disconnected, as (j-1,j+1) are not considered adjacent after removing card/character at index j, we can independently solve for each side. This forms the base for divide and conquer strategy we followed!
Now, repeat the above methodology again on the even part of the subarray. Again, it gets divided into 2 sides, and we erase the odd side. The even side of subarray keeps on getting smaller and smaller, until it reduces to our base case (i.e. 0^*10^*10^*) for which the answer is LOSE. Since that part cannot be exhausted no matter what, the overall answer is always LOSE for this case.
SOLUTION
Setter
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define pll pair<ll int,ll int>
#define vii vector<int,int>
#define vll vector<ll int,ll int>
#define deb(x) cout << #x << " --> " << x << endl;
#define deb2(x,y) cout << #x << " --> " << x << " || " << #y << " --> " << y << endl;
#define boost() ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define cases int t;cin >> t; while(t--)
int main()
{
// freopen("input.txt","r",stdin);
int t;
cin >> t;
while(t--)
{
string s;
cin >> s;
int n = s.length();
int ans=0;
for(int i=0;i<n;i++)
{
if(s[i]=='1')
{
ans++;
}
}
if(ans&1)
cout << "WIN\n";
else
cout << "LOSE\n";
}
}
Tester (KOTLIN)
fun main(args: Array<String>) {
repeat(readLine()!!.toInt()) {
println(listOf("LOSE", "WIN").elementAt(readLine()!!.map{ it.toInt() }.sum() % 2))
}
}
Time Complexity=O(N)
Space Complexity=O(N)
CHEF VIJJU’S CORNER 
Prove or disprove the following -
- The case 0^*10^*10^* is a superset of cases [11,10^*1,0^*11,110^*] .
- Consider the modified version of the problem-
- We are able to chose which adjacent element to flip, and we can flip atmost 1 adjacent element. Prove or disprove that the answer is always
WINif there is a 1 at a cornerpoint of the array, irrespective of frequency of 1's in overall string.
- We are able to chose which adjacent element to flip, and we can flip atmost 1 adjacent element. Prove or disprove that the answer is always
- An O(LogN) solution of this problem exists, ignoring the time taken by input.
- An O(1) solution of this problem exists, ignoring the time taken in input.
Alternate Proof for case of odd 1's
Start removing 1's from left to right.
Note that, every 1 will remove itself, all 0's before it and all 0's till the next 1 and lastly flip the next 1 to 0. You can see that every 1 “consumes” the next 1 after it by flipping it to 0. But since there are odd number of 1's, there will be one more 1 left at the end. Hence our string reduces to 0^*10^*.
Setter's Notes
We have some face-up cards and some face-down cards. A person will be able to remove all the cards if no of faceup cards are odd. So we need to check the no of 1's in the string.
