TTENIS - Editorial

PROBLEM LINK:

Contest
Practice

Author: Istvan Nagy
Tester: Kevin Atienza and Gedi Zheng
Editorialist: Kevin Atienza

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:

  • The last match is won by the overall winner of the contest.

  • At the end, the winner has won more matches than the loser, and so all we have to do is to check if Chef has won more matches than his opponent!

But each of these facts give us an algorithm to compute the answer!

  • If the last match is won by the overall winner, then all we have to do is to check if Chef has won the last match!
  • If, at the end, the winner has won more matches than the loser, then all we have to do is to check if Chef has won more matches than his opponent!

Here is an implementation of the first algorithm, in C++:

#include <iostream>
#include <ios>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    int z;
    cin >> z;
    while (z--) {
        string s;
        cin >> s;
        cout << (s[s.length()-1] == '1' ? "WIN\n" : "LOSE\n");
    }
}

and in Python:

for cas in xrange(input()):
    print "WIN" if raw_input()[-1] == '1' else "LOSE"

There’s also a one-liner code-golf in Python:

print'\n'.join(["LOSE","WIN"][input()&1]for _ in range(input()))

Also, here is an implementation of the second algorithm, in C++:

#include <iostream>
#include <ios>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    int z;
    cin >> z;
    while (z--) {
        string s;
        cin >> s;
        int total = 0;
        for (int i = 0; i < s.length(); i++) {
            total += s[i] - '0';
        }
        cout << (total * 2 > s.length() ? "WIN\n" : "LOSE\n");
    }
}

and in Python:

for cas in xrange(input()):
    s = raw_input()
    print "WIN" if 2*sum(map(int, s)) > len(s) else "LOSE"

What if there are additional matches?

Let’s consider a follow-up 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++:

#include <iostream>
#include <ios>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    int z;
    cin >> z;
    while (z--) {
        string s;
        cin >> s;
        int s0 = 0, s1 = 0;
        for (int i = 0; i < s.length(); i++) {
            (s[i] == '1' ? s1 : s0)++;
            if (max(s0, s1) >= 11 and abs(s0 - s1) >= 2) break;
        }
        cout << (s1 > s0 ? "WIN\n" : "LOSE\n");
    }
}

and in Python:

for cas in xrange(input()):
    s = [0,0]
    for c in map(int, raw_input()):
        s[c] += 1
        if max(s) >= 11 and abs(s[0] - s[1]) >= 2:
            break
    print "WIN" if s[1] > s[0] else "LOSE"

Time Complexity:

O(|S|)

AUTHOR’S AND TESTER’S SOLUTIONS:

Setter
Tester 1
Tester 2

1 Like

http://www.codechef.com/viewsolution/7224794
My solution shows TLE.
Can anyone suggest modification?

link text My solution is showing wrong answer.I had checked it for many test cases and got correct output.
Can anyone find the mistake.

gaddevarunteja,
You made the same mistake I just did. Problem statement isn’t clear enought (at least for non-english 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, (points2-points1==2) – lose.

1 Like

CodeChef: Practical coding for everyone MY SLUTION SHOWS WRONG ANSWER.CAN ANYONE HELP?

iam getting wrong answer,i have checked everything is correct and getting correct input and output…please help!!!

CodeChef: Practical coding for everyone please state what is wrong in my code…I desperately want to see where is the fault

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.

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

I think you program suppose that if the score one time is 10-10 than the winner is who earn 1 pont sooner this is not true. E.g the :
10-10 -> 11-10 , 11-11, 12-11, 12-12, 12-13, 12-14 than the second player won, but your program will be answer the first won…

@iscsi I think p1 won in this case, as p1 scored earliest 12 in the game after the draw. RIght?

I think just checking the last character is always a sufficient condition to determine the winner. Because the last point is always won by the winner.So this should be just done in O(1).
This is the link to my solution:
https://www.codechef.com/viewsolution/30266292

1 Like

i didnt understand this question. can anyone explain me this question in easy way??

Simple and easy c++ solution

int main() {

int t;
string s;
cin>>t;
while (t--)
{
	cin>>s;
	int zeroes=0,ones=0;
	bool flag = false;
	int index=0;
	while (index<s.length())
	{
		if (s[index]=='0') zeroes++;
		else ones++;
		if (ones>10 && ones-zeroes>=2)
	    {
	       flag=true; break;
		}
		index++;
	}
	if (flag) cout<<"WIN\n";
	else cout<<"LOSE\n";
}

return 0;

}

2 Likes

test cases (1010101010101010101011000), is invalid according to problem

it can be only till 1010101010101010101011
as the chef points are 12, opponents pts are 10
and 12-10 = 2 pts lead for chef [ at the end of the 22nd match ]
GAME OVER !
no need to play those extra 3 match as the winner is already declared.

I don’t understand why editorialist @ Kevin Atienza say “The last match is won by the overall winner of the contest.” where it is given in problem statement man?
Kindly please solve my doubt.

1010101010101010101010
then why output is “LOSS” ?

https://www.codechef.com/viewsolution/46614465
this is my solution…can anyone help where i am wrong?
@iscsi ?
i think i have taken every case given in question

my opinion bhaii
@ketul22_12 bhai aapka input pe last 2 digits ke phle dono ke score becomes 10 and 10
to ab 2 consecutive win chahiye kisi ek user ke liye…your input is not a valid case according to question

Maybe try with this input:
1
111111111100000000000111