PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Tester: iceknight1093
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
Sonu and Titu play a best of N sets match of tennis.
They will stop playing once it is clear that one player is definitely the winner, no matter the result of the following games.
You know that they stopped playing when they’d won X and Y sets, respectively. Find N.
EXPLANATION:
First, let’s think about when Sonu and Titu would stop playing if N is known.
If one player wins more than half the matches, the other player can never reach them so they’ll definitely stop playing.
Conversely, if both Sonu and Titu have won less than half the matches, they wouldn’t stop playing because there’s still a way for both players to win.
Why?
Suppose Sonu has A wins and Titu has B. Without loss of generality, let A \leq B.
This means there are x = N - A - B sets remaining.
Since we’re assuming both A and B are at most half of N, and N is odd, we know x \neq 0.
Clearly, if Titu wins all the remaining sets, he’ll win the overall match as well, since B+x\gt A.
However, if Sonu wins all the remaining sets, he’ll win the overall match too!
B was at most half of N, so N-B is greater than half of N; meaning N-B is greater than B.
So, they stop playing exactly when one player wins greater than half of the sets.
We know X and Y, and we know from above that they stopped as soon as one player won more than half of the sets.
That is, \max(X, Y) is the smallest number greater than N/2.
This tells us that N = 2\cdot\max(X, Y)-1 is the answer.
TIME COMPLEXITY:
\mathcal{O}(1) per testcase.
CODE:
Editorialist's code (Python)
for _ in range(int(input())):
x, y = map(int, input().split())
print(2*max(x,y) - 1)