CHEFDIL - Editorial

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!

1 Like

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++. CodeChef: Practical coding for everyone

1 Like

Very good editorial. Thanks for the detailed post

1 Like

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

sorry for the late replyā€¦
thanks for your help i understand my mistake

In the divide and conquer/brute force approach, why does everyone ā€œassumesā€ that we we play the game from left to right. Nothing regarding this issue is mentioned in the question. Can someone explain the intuition behind always choosing to play from left to right or vice versa?

Right-to-left works equally well.

For me, it was just to make the proof easier: if you pick the first face-up card from the left, we have a nice, simple bit of logic that shows that the sub-game to the left will then be trivially winnable via induction, and the proof that the rightmost is winnable too follows easily. The same would be the case if we picked the rightmost one.

Itā€™s quite possible that just picking the 3rd, 5th etc (if present) would probably work equally well; I havenā€™t tried it :slight_smile: (Picking even numbers, I suspect, wonā€™t work - weā€™d probably get an even number of 1ā€™s in both subgames).

Edit:

I just made a modified version that just randomly picks the (2k + 1)th face-up card, and it actually seems not to work, which is surprising:

Sample Failing Runs
Current card state: 0001010000100
Choosing card:                ^
Current card state: 0001010001.10
Choosing card:         ^
Current card state: 001.110001.10
Choosing card:        ^
Current card state: 01..110001.10
Choosing card:           ^
Current card state: 01..0.1001.10
Choosing card:               ^
Current card state: 01..0.101..10
Choosing card:              ^
Current card state: 01..0.11...10
Choosing card:       ^
Current card state: 1...0.11...10
Choosing card:      ^
Current card state: ....0.11...10
Choosing card:                 ^
Current card state: ....0.11....1
Choosing card:                  ^
Current card state: ....0.11.....
Choosing card:            ^
Current card state: ....0..0.....
LOSE
Current card state: 11101110111111101111
Choosing card:        ^
Current card state: 10.11110111111101111
Choosing card:                      ^
Current card state: 10.1111011111111.011
Choosing card:          ^
Current card state: 10.0.01011111111.011
Choosing card:              ^
Current card state: 10.0.011.0111111.011
Choosing card:                         ^
Current card state: 10.0.011.0111111.00.
Choosing card:      ^
Current card state: .1.0.011.0111111.00.
Choosing card:             ^
Current card state: .1.0.00..0111111.00.
Choosing card:       ^
Current card state: ...0.00..0111111.00.
Choosing card:                ^
Current card state: ...0.00..1.01111.00.
Choosing card:                   ^
Current card state: ...0.00..1.00.01.00.
Choosing card:               ^
Current card state: ...0.00....00.01.00.
Choosing card:                     ^
Current card state: ...0.00....00.1..00.
Choosing card:                    ^
Current card state: ...0.00....00....00.
LOSE

Edit: Doh - of course - you canā€™t just pick an odd occurrence of a face-up card, full-stop - it has to the an odd occurrence of a face-up card in a subgame. Fixed:

Sample Fixed Runs
Current card state: 1011011101
Choosing card:               ^
moveToMake: 9
Current card state: 101101111.
Choosing card:            ^
moveToMake: 6
Current card state: 101100.01.
Choosing card:      ^
moveToMake: 0
Current card state: .11100.01.
Choosing card:         ^
moveToMake: 3
Current card state: .10.10.01.
Choosing card:              ^
moveToMake: 8
Current card state: .10.10.1..
Choosing card:          ^
moveToMake: 4
Current card state: .10..1.1..
Choosing card:           ^
moveToMake: 5
Current card state: .10....1..
Choosing card:       ^
moveToMake: 1
Current card state: ..1....1..
Choosing card:             ^
moveToMake: 7
Current card state: ..1.......
Choosing card:        ^
moveToMake: 2
Current card state: ..........
WIN
Current card state: 11111111111011110
Choosing card:                     ^
moveToMake: 15
Current card state: 111111111110110.1
Choosing card:                   ^
moveToMake: 13
Current card state: 1111111111100.1.1
Choosing card:        ^
moveToMake: 2
Current card state: 10.0111111100.1.1
Choosing card:                    ^
moveToMake: 14
Current card state: 10.0111111100...1
Choosing card:                      ^
moveToMake: 16
Current card state: 10.0111111100....
Choosing card:      ^
moveToMake: 0
Current card state: .1.0111111100....
Choosing card:          ^
moveToMake: 4
Current card state: .1.1.01111100....
Choosing card:            ^
moveToMake: 6
Current card state: .1.1.1.011100....
Choosing card:                ^
moveToMake: 10
Current card state: .1.1.1.010.10....
Choosing card:         ^
moveToMake: 3
Current card state: .1...1.010.10....
Choosing card:              ^
moveToMake: 8
Current card state: .1...1.1.1.10....
Choosing card:             ^
moveToMake: 7
Current card state: .1...1...1.10....
Choosing card:               ^
moveToMake: 9
Current card state: .1...1.....10....
Choosing card:           ^
moveToMake: 5
Current card state: .1.........10....
Choosing card:                 ^
moveToMake: 11
Current card state: .1..........1....
Choosing card:       ^
moveToMake: 1
Current card state: ............1....
Choosing card:                  ^
moveToMake: 12
Current card state: .................
WIN

Big one:

Current card state: 0111101110101111001010000010111111101001100
Choosing card:       ^
Current card state: 1.01101110101111001010000010111111101001100
Choosing card:                                     ^
Current card state: 1.01101110101111001010000010110.01101001100
Choosing card:                                       ^
Current card state: 1.01101110101111001010000010110.1.001001100
Choosing card:                                ^
Current card state: 1.011011101011110010100001.1110.1.001001100
Choosing card:         ^
Current card state: 1.1.0011101011110010100001.1110.1.001001100
Choosing card:        ^
Current card state: 1...0011101011110010100001.1110.1.001001100
Choosing card:                                          ^
Current card state: 1...0011101011110010100001.1110.1.01.101100
Choosing card:                  ^
Current card state: 1...00111011.0110010100001.1110.1.01.101100
Choosing card:            ^
Current card state: 1...01.01011.0110010100001.1110.1.01.101100
Choosing card:                                 ^
Current card state: 1...01.01011.0110010100001..010.1.01.101100
Choosing card:              ^
Current card state: 1...01.1.111.0110010100001..010.1.01.101100
Choosing card:               ^
Current card state: 1...01.1..01.0110010100001..010.1.01.101100
Choosing card:             ^
Current card state: 1...01....01.0110010100001..010.1.01.101100
Choosing card:                    ^
Current card state: 1...01....01.1.00010100001..010.1.01.101100
Choosing card:                                      ^
Current card state: 1...01....01.1.00010100001..010...01.101100
Choosing card:                                   ^
Current card state: 1...01....01.1.00010100001..1.1...01.101100
Choosing card:                                           ^
Current card state: 1...01....01.1.00010100001..1.1...01..11100
Choosing card:                                              ^
Current card state: 1...01....01.1.00010100001..1.1...01..10.10
Choosing card:                 ^
Current card state: 1...01....1..1.00010100001..1.1...01..10.10
Choosing card:      ^
Current card state: ....01....1..1.00010100001..1.1...01..10.10
Choosing card:                ^
Current card state: ....01.......1.00010100001..1.1...01..10.10
Choosing card:                                               ^
Current card state: ....01.......1.00010100001..1.1...01..10..1
Choosing card:                                         ^
Current card state: ....01.......1.00010100001..1.1...1...10..1
Choosing card:                                        ^
Current card state: ....01.......1.00010100001..1.1.......10..1
Choosing card:                                            ^
Current card state: ....01.......1.00010100001..1.1........1..1
Choosing card:                        ^
Current card state: ....01.......1.001.1100001..1.1........1..1
Choosing card:                                                ^
Current card state: ....01.......1.001.1100001..1.1........1...
Choosing card:                         ^
Current card state: ....01.......1.001..000001..1.1........1...
Choosing card:                   ^
Current card state: ....01.........001..000001..1.1........1...
Choosing card:                       ^
Current card state: ....01.........01...000001..1.1........1...
Choosing card:                                             ^
Current card state: ....01.........01...000001..1.1............
Choosing card:                               ^
Current card state: ....01.........01...00001...1.1............
Choosing card:                              ^
Current card state: ....01.........01...0001....1.1............
Choosing card:                                  ^
Current card state: ....01.........01...0001......1............
Choosing card:                      ^
Current card state: ....01.........1....0001......1............
Choosing card:                                    ^
Current card state: ....01.........1....0001...................
Choosing card:                     ^
Current card state: ....01..............0001...................
Choosing card:           ^
Current card state: ....1...............0001...................
Choosing card:                             ^
Current card state: ....1...............001....................
Choosing card:          ^
Current card state: ....................001....................
Choosing card:                            ^
Current card state: ....................01.....................
Choosing card:                           ^
Current card state: ....................1......................
Choosing card:                          ^
Current card state: ...........................................
WIN

Edit:

May as well include the code so you can generate your own :slight_smile: I compile to an exe named a.out, so I just do

./a.out --test | ./a.out

Code that Picks Random Odd Face Up Card in Subgame
// Simon St James (ssjgz) - 2019-08-03
#define SUBMISSION
#ifdef SUBMISSION
#define NDEBUG
#endif
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

#include <cassert>

#include <sys/time.h>

using namespace std;

template <typename T>
T read()
{
    T toRead;
    cin >> toRead;
    assert(cin);
    return toRead;
}


bool calcCanChefWin(const string& cardsStateOriginal)
{
    string cardState = cardsStateOriginal;
    const char removedCard = '.';
    while (true)
    {
        cout << "Current card state: " << cardState << endl; 
        vector<int> positionsOfOddFaceUp;
        int numFaceUpSeen = 0;
        for (int i = 0; i < cardState.size(); i++)
        {
            if (cardState[i] == removedCard)
            {
                // New sub-game - reset count.
                numFaceUpSeen = 0;
            }
            if (cardState[i] == '1')
            {
                numFaceUpSeen++;
                if ((numFaceUpSeen % 2) == 1)
                {
                    positionsOfOddFaceUp.push_back(i);
                }
            }
        }
        if (positionsOfOddFaceUp.empty())
        {
            const auto numCards = std::count_if(cardState.begin(), cardState.end(), [](const auto card) { return card != removedCard; });
            if (numCards > 0)
                return false;
            else
                return true;
        }
        const int moveToMake = positionsOfOddFaceUp[rand() % positionsOfOddFaceUp.size()];
        cout << "Choosing card:     " << string(moveToMake + 1, ' ') << "^" << endl;
        cardState[moveToMake] = removedCard;
        if (moveToMake != 0 && cardState[moveToMake - 1] != removedCard)
        {
            cardState[moveToMake - 1] = '0' + ('1' - cardState[moveToMake - 1]);
        }
        if (moveToMake != cardState.size() - 1 && cardState[moveToMake + 1] != removedCard)
        {
            cardState[moveToMake + 1] = '0' + ('1' - cardState[moveToMake + 1]);
        }
    }
}

int main(int argc, char* argv[])
{
    if (argc == 2 && argv[1] == string("--test"))
    {
        // Generate a set up cards with an odd number facing up.
        struct timeval time;
        gettimeofday(&time,NULL);
        srand((time.tv_sec * 1000) + (time.tv_usec / 1000));

        const int numCards = rand() % 70 + 1;
        int numFaceUp = rand() % numCards;
        if (numFaceUp % 2 == 0)
        {
            if (numFaceUp != 0)
                numFaceUp--;
            else
                numFaceUp++;
        }
        string cards;
        for (int i = 0; i < numCards; i++)
        {
            if (i < numFaceUp)
                cards.push_back('1');
            else
                cards.push_back('0');
        }
        random_shuffle(cards.begin(), cards.end());
        cout << 1 << endl;
        cout << cards << endl;
        return 0;

    }

    const auto T = read<int>();
    for (auto t = 0; t < T; t++)
    {
        const string cardsState = read<string>();

        const auto canChefWin = calcCanChefWin(cardsState);
        cout << (canChefWin ? "WIN" : "LOSE") << endl;
    }
}
2 Likes

My god, just out of curiosity, how much time does it take for you to write the full solution with documentation?
Itā€™s awesome.
I just treated this as an observation problem with count of ones, reading the full reasoning was nice :slight_smile:

2 Likes

Depends on the problem :slight_smile: CHGORAM was one of the hardest (as Iā€™m sure @vijju123 can attest :)), and took quite a bit of pondering before even writing out the initial draft. Actually typing it up tends to be fairly quick, so letā€™s say about - 4 hours or so for CHGORAM?

Others are easier - according to my git logs, the documentation for CHEFDIL seems to have taken about 45 mins, which isnā€™t too bad :slight_smile: I also actually did the ā€œobservation problemā€ approach first, and then tried to figure out why on earth it worked XD

BACREP was probably about 3 hours or so.

Cleaning up and refactoring the code to be readable is usually the quickest part, and the most fun :slight_smile:

3 Likes

Haha, damnnn . Honestly Iā€™ve not seen many approach cp in such a structured way as you do :slight_smile:
People like you and @vijju123 are an inspiration.
More power to you.
I think Iā€™ve seen you on Hackerrank if Iā€™m not mistaken ?
Does your math background come in handy for establishing proofs?
And would you attribute your skills to just repeated practise?
Congrats on 5 star in just 3 contests btw.

3 Likes

Thankyou - that means a lot :slight_smile:

Thatā€™s right - this is my Hackerrank profile - https://www.hackerrank.com/ssjgz . I moved to Codechef as I had some of my own Problems I wanted to submit but Hackerrank is no longer a suitable site for them, sadly. I prefer it here, though - much better sense of community :slight_smile:

Definitely, though not (interestingly) for solving mathematical problems - if Iā€™d been in Div 1 in the much more maths-y September Long Contest, Iā€™d have been screwed :slight_smile: I put this down to the fact that I finished my degree so long ago, it was before many people on this forum were even born XD

Absolutely:

[simon@simon-laptop][10:39:34]
[~/devel/hackerrank]>find . -iname "*.cpp" | grep -v otherpeople | grep -v experiments | grep -v "my-own-problems" | grep -v blah.cpp | grep -v "code-template.cpp" | grep -v  "snippets.cpp" | grep -v "\-generator.cpp" | wc -l
253

Thanks again :slight_smile:

3 Likes

can anyone explain the solution in a more easy way???

I suggest you brush up Divide and Conquer category before trying to understand the editorial. :slight_smile:

i am having a confusion in the case 001 because when 1 is removed, the 0ā€™s are flipped it becomes 11->0 now only one 0 is left so shouldā€™nt the answer be LOSE???

Only adjacent characters are flipped. So its 001->01->1->empty string

1 Like