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
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 
(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;
}
}
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 
2 Likes
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
3 Likes
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.
3 Likes
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
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.
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