Problem of the Month - October 2020

Yes! I’m back with the problem of the month series!

Problem of the month October’20 was hard to pick. This month was a load month for Topcoder, having exciting TCO Rounds and SRMs

So for this month I have chosen the : Hardest Div. 2 Easy in the world for you to solve together. Kidding? No.

TableTennisGame turned out to be the hardest problem of all Div. 2 Easy Problems that have been on Topcoder on the basis of the success rate. The problem was written by laoriu. This was laoriu’s first SRM and congratulations to him on a great round.

The problem is exactly how a table tennis game is played:

• The game is a sequence of exchanges. Each exchange starts by one of the two players serving the ball and ends when one of the players loses the exchange by failing to play the ball correctly. The winner of each exchange gets a point.

• A player wins the game as soon as they have at least 11 points and at the same time they lead their opponent by at least two points.

• The serve changes after every two points. (That is, one player has the serve in the first two exchanges, the other player in the next two, and so on.)

• If the score of the game reaches 10-10 (“deuce”), from that moment the serve changes after each point.

Given the numbers A and B specifying how many times each of the players served the ball during the game. Determine whether these values A and B correspond to some completed game of table tennis. If they don’t, return an empty int[].

If the values A and B do correspond to some completed game of table tennis, the final score of the game can always be uniquely determined from A and B. Determine the numbers W and L of points scored by the winner and the loser of the game. Return the int[] {W, L}.

For example, when A = 8, B = 6, Returns: {11, 3 }

The game proceeded as follows:
Player A served twice, then player B served twice.
Player A served twice, then player B served twice.
Player A served twice, then player B served twice.
Player A served twice.

We can deduce that the final score of the game must have been 11-3. (We do not know who won the game, but we know that the winner must have had W = 11 points and the loser must have had L = 3 points.)

APPROACH AND SOLUTION

Let’s describe the solution. The point is, when a ball is served, it will finally lead to a score for one of the players (obvious, no?) so A + B = W + L = the number of exchanges played. You remember from elementary school that when we have the sum of two numbers, if we have the difference between them we can find each of them.

So, what we need is W - L. The number of exchanges played must be at least 11. So if A + B < 11 let’s return an empty array.

If the game finishes with W = 11 and L < 10, so the number of exchanges played is less than or equal to 20. Otherwise deuce occurred.

Because before deuce the serve changes every 2 exchanges:

• At least A or B needs to be even.

• |A - B| must be less than or equal to 2.

If any of these conditions is not satisfied, the answer is [].
Otherwise, it’s easy to see W = 11 and L = A + B - 11.

Let’s observe the case in which deuce happens.
So W > 11, L = W - 2. A + B = W + L = W + W - 2. So, A + B must be even.

Also, because after deuce the serve changes every exchange, |A - B| <= 1.
If conditions are satisfied, W = (A + B) / 2 + 1, L = (A + B) / 2 - 1.

Code by Arpa:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
    struct TableTennisGame {
      vector < int > finalScore(int A, int B) {
        if (A + B < 11)
          return {};
        if (A + B <= 20) {
          if (A % 2 == 1 && B % 2 == 1)
            return {};
          if (abs(A - B) > 2)
            return {};
          return {
            11,
            (A + B) - 11
          };
        }
        if ((A + B) % 2 == 1 || abs(A - B) > 1)
          return {};

        return {
          (A + B) / 2 + 1,
          (A + B) / 2 - 1
        };
      }
    };