Contest

EASY

Greedy

# PROBLEM:

There are N teams. Each team plays with every other team, exactly once. A team gets 2 points on winning, and 0 on losing. Determine the maximum possible number of points a team finishing at position K can score (If multiple teams have the same score, the team with the higher number achieves a better rank).

# EXPLANATION:

### TL;DR

The solution can be represented compactly in one line

2\times\bigg(\bigg\lfloor\frac{K-1}{2}\bigg\rfloor+N-K\bigg)

To ease the explanation, letâ€™s say team i finishes at the i^{th} position (team 1 gets rank 1, team 2 rank 2 and so on). Note that this doesnâ€™t affect the problem, since the team numbers have no part in the solution.
It is clear that the score of team i \ge score of team j, for all i\le j.

Letâ€™s first solve for when K=N.
If team N wins X rounds, then all others teams should win at least X rounds. Then, since there are a total of N\choose 2 rounds (which is equal to the total number of wins over all teams), the value of X is bounded by

X\le {N\choose 2}\div N = \frac{N-1}{2}

Letâ€™s see if it is possible for team N to win the maximum permissible limit of X = \lfloor\frac{N-1}{2}\rfloor rounds. A bit of bruteforce/greedy caseworking shows that it is always possible!

Proof

Case 1: N is odd.

• Team 1 wins against teams 2,3,\dots,1+X
• Team 2 wins against teams 3,4,\dots,2+X
• \dots
• Team N wins against teams 1,2,\dots,X

Case 2: N is even.

Same as the above, but here, team i also wins against team i+X+1, for all 1\le i\le\frac{N}{2}.

The correctness of the solution can be verified without much difficulty.

Now, solving for any K is much clearer.

Using a greedy intuition, we set team i to win against team j, for all 1\le i\le K and all K < j \le N. So, team K wins N-K rounds against the last N-K teams.
(The proof of this strategy is left to the reader as an exercise).

Then, similar to the previous approach, we deduce that the maximum number of rounds team K can win against the first K-1 teams is equal to \lfloor\frac{K-1}{2}\rfloor.

Therefore, the maximum total number of rounds team K can win equals

N-K+\bigg\lfloor\frac{K-1}{2}\bigg\rfloor

and multiplying this value by 2 (since each win adds 2 to our score) gives us the desired answer!

O(1)

per test case.

# SOLUTIONS:

Editorialistâ€™s solution can be found here

Experimental: For evaluation purposes, please rate the editorial (1 being poor and 5 excellent)

• 1
• 2
• 3
• 4
• 5

0 voters

1 Like