CHEFDIL - Editorial

PROBLEM LINK:

Div1
Div2
Practice

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.

  1. Proof that answer is WIN if number of 1's is odd.
  2. Proof that answer is LOSE if 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 :slight_smile:

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 :slight_smile: )

  1. 0^+ - i.e. when there are zero 1's in the string. The answer is obviously LOSE.
  2. 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.
  3. 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 LOSE here 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. :slight_smile:

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.

  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.
  2. 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.
  3. X=0,Y=1 - Same as above.
  4. 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 :smiley:

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 WIN if there is a 1 at a cornerpoint of the array, irrespective of frequency of 1's in overall string.
  • 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.

Related Problems
6 Likes

my dp based approach.

Slightly more rigorous proofs here.

2 Likes

Its same as the one in editorial - based on divide and conquer.

My divide and conquer approach

nice approach using regular language

1 Like

Alternate proofs including watching a numberphile video. :upside_down_face:
I mean the problem wasn’t even slightly changed.

5 Likes

For those who don’t know why the solution give WIN every time the no. of 1’s is odd.
Here is my approach (O(n)) which calculates the answer by playing the game.

STATUS : SOLUTION 100% ON PYPY(0.46s)

# looping to cover all test cases
for case in range(int(input())):
    string = input()                # string of 0 and 1 depicting cards

    # string of cards is converted to a list of 0 and 1
    cards = []
    for card in string:
        cards.append(int(card))
    i = 0                           # i denote the index of the card we are analysing
    n = len(cards)
    count = n                       # count depict no. of cards remaining to be analysed

    # following loop will loop over all cards in the list from starting from first card while
    # flipping the face up cards and then flipping its adjacent cards
    while True:
        if cards[i] == 1:             # if the card is face up flip it
            cards[i] = -1              # flipped cards will be represented as -1 in the cards list
            count -= 1
            # flipping the adjacent cards
            x = i-1
            y = i+1
            # flipping previous card
            if x>= 0:
                if cards[x] == 1:
                    cards[x] = 0
                elif cards[x] == 0:
                    cards[x] = 1
            if y < n:
                #'flipping next card'
                if cards[y] == 1:
                    cards[y] = 0
                elif cards[y] == 0:
                    cards[y] = 1

        # now we have to check whether flipping the adjacent cards have created another face
        # up card behind the current card so we review the previous card
        if i != 0 and cards[i-1] == 1:      # i != 0 condition to check if we are the first card
            i -= 1
        else:
            i += 1

        if i == n or count == 0:   # if all cards are analysed
            if count == 0:
                print('WIN')
                break
            else:
                print('LOSE')
                break
2 Likes

my code

for _ in range(int(input())):
    s=list(input())
    s.append("1")
    n1,n2=0,0
    l=len(s)
    for j in range(l-1):
# counting the consecutive zeroes before any 1
        if(s[j]=="0"):
            n1+=1
# flipping every 0's cards which are in left of any 1
        if(s[j]=="1"):
            n2+=n1+1
            n1=0
# flipping the next card
            if(s[j+1]=="1"):
                s[j+1]="0"
            else:
                s[j+1]=  "1"
# checking if all the cards have been flipped or no
    if(n2==(l-1)):
        print("WIN")
    else:
        print("LOSE")

In question It is also mentioned that removing such a card which is adjacent to an empty space created by removing a card does not cause other card to be flipped ,then how could be your answer correct

What will be the solution if after removal , string become contiguous

What will be the solution if after card is removed, string become contiguous

Initially it was in the bonus section, but I removed it later because I did not get time to explore it. Mostly it will become a game theory problem where either more observations, or grundy numbers may help.

bro can you plss see my code .

can you plz tell why my code is getting a tle error.Thanks in advance
https://www.codechef.com/viewsolution/25571033

Python in 2 simple lines. Then I read all of your solutions to just count 1’s. So many gifted people on this site.

for _ in xrange(input()):
	print "WIN" if reduce(lambda a,b:a^b, map(int,raw_input())) else "LOSE"

So much for overthinking the problem! Ha!

Let me try to explain it as simply as possible, your solution loops over all the string elements(cards) for reversing them, however in your while loop condition you are using d.count(‘1’) which itself loops over the entire list to count the number of 1’s in the string. So basicially you are using a 2 loops so your solution turns out to be O(n^2) which you can’t afford. You can easily replace your loop condition to prevent extra looping(I think you can figure it out by yourself, however I will help if needed).
Hope this helps
Thanks

A normal brute force approach worked for me :slight_smile: : My solution

Never thought of checking odd no of one’s guess i am dumb here is my brute force approach in c++. https://www.codechef.com/viewsolution/25649666

1 Like

Very good editorial. Thanks for the detailed post

1 Like