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 
(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 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;
}
}
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 
Depends on the problem 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 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
Haha, damnnn . Honestly I’ve not seen many approach cp in such a structured way as you do
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.
Thankyou - that means a lot
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
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 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
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.
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