You are not logged in. Please login at www.codechef.com to post your questions!

×

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

This question is marked "community wiki".

asked 12 Jun '15, 05:47

kevinsogo's gravatar image

7★kevinsogo
1.7k586142
accept rate: 11%

edited 13 Jun '15, 02:49

admin's gravatar image

0★admin ♦♦
19.7k350498541

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

(13 Jun '15, 14:27) sandeep93★

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

link

answered 15 Jun '15, 03:31

karantirthani's gravatar image

2★karantirthani
1
accept rate: 0%

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.

link

answered 15 Jun '15, 20:41

gaddevarunteja's gravatar image

2★gaddevarunteja
1
accept rate: 0%

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.

link

answered 10 Sep '16, 18:41

pev285's gravatar image

2★pev285
11
accept rate: 0%

edited 10 Sep '16, 18:42

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

link

answered 13 Sep '16, 00:38

vjtron2610's gravatar image

1★vjtron2610
1
accept rate: 0%

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

link

answered 21 Sep '16, 11:08

vivek7119's gravatar image

2★vivek7119
1
accept rate: 0%

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

link

answered 23 Nov '16, 14:54

blaze_nitd's gravatar image

4★blaze_nitd
1
accept rate: 0%

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..

(23 Nov '16, 15:48) iscsi6★

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.

link

answered 22 Mar '18, 22:00

sprea27's gravatar image

2★sprea27
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,494
×51

question asked: 12 Jun '15, 05:47

question was seen: 4,123 times

last updated: 22 Mar '18, 22:00