PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Simple
PREREQUISITES:
None
PROBLEM:
There are N gladiators, initially all with a skill level of 0.
N-1 times, the following will happen:
- Two gladiators will fight, and one will be eliminated.
If their skill levels are X and Y, the entertainment of the fight is (X+Y).
After the fight, the winner’s skill level will increase by 1.
Find the minimum and maximum total entertainment that can be obtained via a sequence of fights.
EXPLANATION:
First, let’s compute the maximum possible total entertainment.
After every round, the winner’s skill level increases by exactly 1.
This means that after i rounds, the total skill level of all remaining gladiators will be at most i, because there would have only been i increases so far - one after each round.
Note that this particularly implies that the i-th round can only generate an entertainment of (i-1) at most; since the two gladiators fighting in it can have no more than (i-1) total skill between them.
This already gives us an upper bound on the total entertainment that can be achieved: the i-th round can generate at most (i-1) entertainment, so with (N-1) rounds the maximum we can generate is
Now, this is just an upper bound - for it to be the answer, we need to prove that it’s always achievable.
Luckily, there’s a fairly simple way to do this: pick one gladiator to be the “champion”, and in every round, have this champion fight against another gladiator and win.
This will increase the champion’s skill by 1 after every single fight (while all other gladiators will have 0), and since he participates in every fight, the overall entertainment in each fight is just going to be his skill level.
This exactly achieves (0 + 1 + 2 + \ldots + (N-1)), as we wanted - and so the above value is indeed the maximum.
Next, let’s look at the minimum.
Just as we did for the maximum, let’s try to find a lower bound on the answer - and then prove that this lower bound is achievable.
To do this, let’s look at the skill points independently.
Specifically, let’s look at the very first round - it will generate one skill point, which goes to the winner of that round - say gladiator i.
Now, this skill point will contribute to the total entertainment exactly once for each further fight gladiator i participates in.
Further, note that gladiator i, since he won the first fight, must surely fight at least once more - because in the end only one person will remain, and that’s the winner of the final fight.
So, the skill point generated by the first fight will contribute at least 1 to the overall entertainment.
Further, observe that this doesn’t really depend on it being the first fight - the same logic applies to any fight, except the very last one since there are no fights after it.
That is, the logic applies to all the fights 1, 2, 3, \ldots, N-2.
Since each of them contributes at least 1 to the total entertainment, the total entertainment is surely at least N-2.
Now, we need to prove that attaining exactly N-2 is possible.
This turns out to be not too hard. One method is as follows:
- Number the gladiators 1, 2, 3, \ldots, N.
- In the i-th fight, make gladiators i and i+1 fight against each other, with the winner being gladiator i+1.
- This will ensure that in the i-th fight, gladiator i has a skill level of 1, while i+1 has a skill level of 0 (except for i = 1, where both have a skill of 0).
So, each of fights 2, 3, \ldots, N-1 will add 1 to the entertainment, achieving our lower bound of N-2; hence it’s optimal.
So, quite simply, the minimum and maximum possible total entertainment equal
respectively.
TIME COMPLEXITY:
\mathcal{O}(1) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n = int(input())
print(n-2, (n-1)*(n-2)//2)