BADDYSTR - Editorial

PROBLEM LINK:

Badminton Strings

Author and Editorialist: Kabir Kanha Arora
Testers: Illisha Singh, Jackson Jose, Nishank Suresh, Vaibhav Gautam

DIFFICULTY:

CAKEWALK

PREREQUISITES:

Observation/Implementation.

PROBLEM:

Illisha and Vaibhav are playing a badminton match (best of three sets).
Given a string, the i^{th} character of which denotes who won the i^{th} point, we are supposed to find the winner.

QUICK EXPLANATION:

The person who wins the last point wins the match.

EXPLANATION:

The line above would probably have struck many of you with the force of a hundred elephants.
Most of the solutions we saw in-contest took the extremely long and arduous route, by iterating over the entire string, character by character, and maintaining the points, as well as the number of sets won by each player.

This method, although correct, is prone to a lot of errors, and is also far more time consuming.
A key to doing well in CP is trying to find hidden stuff in problems and this is a prime example of it. If the points form a valid match, whoever won the last point had won the match too.

COMMON MISTAKES:

  • Counting who won more points.
    This doesn’t work. Consider the case where the final results of a match are 0-21, 21-19, 21-19. The person who won more points lost the match.

  • Not accounting for the ‘difference of two points’ rule.
    Some of you, who took the long route, did not take into account that the player has to have a difference of two points to win a set.

SOLUTIONS:

Setter's Solution (Kabir Kanha Arora) - Java
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        while (t-- > 0) {
            int n = scanner.nextInt();
            String str = scanner.next();
            // Just check who won the last point.
            if (str.charAt(n - 1) == 'V')
                System.out.println("Vaibhav");
            else
                System.out.println("Illisha");
        }
    }
}
Tester's Solution (Vaibhav Gautam) - Python
t=int(input())
while(t>0):
    n=int(input())
    s=input()
    if(s[len(s)-1]=='V'):
        print('Vaibhav')
    else:
        print('Illisha')
    t-=1 
Tester's Solution (Nishank Suresh) - C++
#include "bits/stdc++.h"
using namespace std;
using ll = long long int;
 
int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    int t; cin >> t;
    while (t--) {
        int n; cin >> n;
        string s; cin >> s;
        if (s.back() == 'I') cout << "Illisha\n";
        else cout << "Vaibhav\n";
    }
} 
Tester's Solution (Nishank Suresh) - Python - Long route
t = int(input())
out = ''
for _ in range(t):
	n = int(input())
	s = input()
	i, v = 0, 0
	ig, vg = 0, 0
	for point in s:
		if point == 'I':
			i += 1
		else:
			v += 1
		if i >= 21 and i >= v+2:
			ig += 1
			i, v = 0, 0
		elif v >= 21 and v >= i+2:
			vg += 1
			i, v = 0, 0
	if ig > vg:
		out += 'Illisha\n'
	else:
		out += 'Vaibhav\n'
print(out) 
1 Like