TTENIS - Editorial

editorial
snck15el

#1

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

" : "LOSE
");
}
}

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'

'.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* - '0';
        }
        cout << (total * 2 > s.length() ? "WIN

" : "LOSE
");
}
}

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* == '1' ? s1 : s0)++;
            if (max(s0, s1) >= 11 and abs(s0 - s1) >= 2) break;
        }
        cout << (s1 > s0 ? "WIN

" : "LOSE
");
}
}

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


#2

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


#3

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.


#4

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.


#5

https://www.codechef.com/viewsolution/11500175 MY SLUTION SHOWS WRONG ANSWER.CAN ANYONE HELP?


#6

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


#7

https://www.codechef.com/viewsolution/12133557 please state what is wrong in my code…I desperately want to see where is the fault


#8

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.


#9

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


#10

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…