CHEFDIL - Editorial

editorial
, , , , ,
3

Slightly more rigorous proofs here.

2 Likes
4

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

5

My divide and conquer approach

6

nice approach using regular language

1 Like
7

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

5 Likes
8

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
9

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")
10

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

1 Like
11

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

12

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

13

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.

14

bro can you plss see my code .

15

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

16

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!

1 Like
17

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

18

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

19

Never thought of checking odd no of one’s guess i am dumb here is my brute force approach in c++. CodeChef: Practical coding for everyone

1 Like
20

Very good editorial. Thanks for the detailed post

1 Like
21

Here’s my solution, it gives TLE , i am not able to optimize it properly , could anyone help?
try:
T = int(input())
if 1 <= T <= 10 ** 2:
for p in range(T):
input_str = str(input())
int_list = []
for x in input_str:
int_list.append(int(x))
if int_list[0] == 1 and int_list[1] == 1:
int_list[1] = 0
int_list[0] = -1
elif int_list[0] == 1 and int_list[1] == 0:
int_list[1] = 1
int_list[0] = -1
int_list.append(-1)
while int_list.count(1) != 0:
for i in range(1, len(int_list)-1):
if int_list[i] == 1:
int_list[i] = -1
if int_list[i - 1] == 0:
int_list[i - 1] = 1
elif [i - 1] == 1:
int_list[i - 1] = 0
else:
pass
if int_list[i + 1] == 0:
int_list[i + 1] = 1
elif [i + 1] == 1:
int_list[i + 1] = 0
else:
pass
else:
pass
if int_list.count(1)==0:
print(“WIN”)
else: print(“LOSE”)
except:
pass

22

sorry for the late reply…
thanks for your help i understand my mistake