# PROBLEM LINK:

# DIFFICULTY:

EASY

# PREREQUISITES:

# 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

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

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

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

# TIME COMPLEXITY:

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