RRR - Editorial

editorial
, , ,
1

PROBLEM LINK:

Contest

DIFFICULTY:

EASY

PREREQUISITES:

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!

TIME COMPLEXITY:

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