PROBLEM LINK:
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|)