PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07
Tester: iceknight1093
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
A three-player game is held with N rounds.
Each round is won by a single player.
If there’s no clear winner after N rounds, more will be held till a clear winner emerges.
Find the maximum number of rounds that can be held.
EXPLANATION:
For there to not be a clear winner after N rounds, either all three players must have the same score, or two of them must have the same score and this must be higher than the third score.
Let’s look at both scenarios and see which is more beneficial to us.
Case 1: All scores equal
Suppose all three players have a score of x after N rounds.
Then, as soon as the next round is held, the winner will have a score of x+1 and be the clear winner - so we are forced to stop at N+1 rounds.
This is better than stopping at N, but not by much (and is only available in the first place when N is a multiple of 3.)
Case 2: Two scores equal.
Suppose the scores of the players after N rounds are x, x, y where x \gt y.
If either of the players with score x wins a round, they will become the clear winner and we must stop.
The only way to prevent this is for the third player to repeatedly become the winner.
However, this cannot last forever: after y-x wins, the third player will also reach a score of x after which the next round will create a clear winner.
Thus, we can have only y-x+1 additional rounds, after the first N.
Our aim should clearly be to maximize y-x.
This can be done as follows:
- If N is even, choose x = \frac{N}{2} and y = 0.
In this case, we’ll end up holding a total of \frac{3N}{2} + 1 rounds. - If N is odd, choose x = \frac{N-1}{2} and y = 1.
In this case, we’ll end up holding a total of \frac{3\cdot (N-1)}{2} + 1 rounds.
(This reasoning technically doesn’t work for N = 1 because we end up with x = 0 and y = 1 and hence x \lt y, but luckily the answer is 1 in that case which is what the formula gives anyway.)
In either case, this is better (or not worse) than the N+1 obtained from the previous case, so we always use this case.
Both parities of N can be combined to obtain the formula
TIME COMPLEXITY:
\mathcal{O}(1) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n = int(input())
print(3 * (n//2) + 1)