PROBLEM LINK:Author: Istvan Nagy PREREQUISITES:Ad hoc, string processing PROBLEM:In table tennis, a game is won by the player first scoring 11 points except in the case when both players have 10 points each, then the game shall be won by the first player subsequently gaining a lead of 2 points. Given a valid, finished game in which Chef is one of the players, determine if Chef won. QUICK EXPLANATION:There are many solutions. Here are a few simple ones: Solution 1: Print "WIN" if the last character in $S$ is a '1', otherwise print "LOSE". Solution 2: Print "WIN" if there are more 1s than 0s in $S$, otherwise print "LOSE". EXPLANATION:This is a simple problem. First, note that the sequence of results of the matches is valid and finished. This means that the winner has been determined at the end (and only right after the last match), and the winner has a lead of at least two points from the loser. This means the following:
But each of these facts give us an algorithm to compute the answer!
Here is an implementation of the first algorithm, in C++:
and in Python:
There's also a oneliner codegolf in Python:
Also, here is an implementation of the second algorithm, in C++:
and in Python:
What if there are additional matches?Let's consider a followup problem. Suppose that Chef and his opponent continued after the winner has been determined, i.e. assume there are matches after the winner has been determined. In this case, we cannot do the strategies above anymore, because it might happen that the Chef lost the game, but his opponent didn't take the following matches seriously so Chef won a lot of matches afterwards. In this case, we now have to determine at which point the winner has been determined, and stop there. We just have to remember that the winner has been determined if someone has scored at least 11 points and has gained a lead of at least two against the other opponent. Here's an implementation in C++:
and in Python:
Time Complexity:$O(S)$ AUTHOR'S AND TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 12 Jun '15, 05:47

http://www.codechef.com/viewsolution/7224794 My solution shows TLE. Can anyone suggest modification? answered 15 Jun '15, 03:31

gaddevarunteja, You made the same mistake I just did. Problem statement isn't clear enought (at least for nonenglish speaker). You use the rule "two '1' in a row  win, tow '0' in a row  lose". It's incorrect. You need to use (points1  points2 == 2) > win, (points2points1==2)  lose. answered 10 Sep '16, 18:41

https://www.codechef.com/viewsolution/11500175 MY SLUTION SHOWS WRONG ANSWER.CAN ANYONE HELP? answered 13 Sep '16, 00:38

iam getting wrong answer,i have checked everything is correct and getting correct input and output...please help!!!! answered 21 Sep '16, 11:08

https://www.codechef.com/viewsolution/12133557 please state what is wrong in my code...I desperately want to see where is the fault answered 23 Nov '16, 14:54
I think you program suppose that if the score one time is 1010 than the winner is who earn 1 pont sooner this is not true. E.g the : 1010 > 1110 , 1111, 1211, 1212, 1213, 1214 than the second player won, but your program will be answer the first won..
(23 Nov '16, 15:48)

Hello, I had written a code for this question, which got passed and I got AC. My solution: https://www.codechef.com/viewsolution/17920124 But I figured out a test case (1010101010101010101011000), for which my solution will give "LOSE" but the author's solution will give "WIN". I know that my solution is wrong according to the question. Please check the test cases being used to check our codes. answered 22 Mar '18, 22:00

Whats wrong in my answer? It is working fine,but giving wrong answer!!! Can u tell where it fails? Link to my WA solution http://www.codechef.com/viewsolution/7198216