LEAGUE Editorial

editorial
, ,
1

PROBLEM LINK:

Contest Division 3
Contest Division 4

Setter and Editorialist : Yashodhan Agnihotri

DIFFICULTY:

883

PREREQUISITES:

None.

PROBLEM:

Find the maximum number of points by which a team can win a N-team league, if each team plays every other team in round robin fashion. Teams get 3 points for a win and 0 points for a loss. (Assume there are no draws).

EXPLANATION:

The answer can mainly be gathered with the following hints.

Winning team wins all

This is necessary to maximise the points of the winner team. Therefore the total number of points of the winning team will be 3*(N-1).

Other teams perform similarly

If the second placed team performs similar to other teams apart from team A(winning team), that helps in minimizing the total points.
So, the second placed team will play a total of N-2 games with teams other than the winning team. If they win half games and lose halfgames, that will help in keeping their points total to a minimum. So, points gathered will be ceil((N-2)/2)*3. Ceil function is used so that in case N is odd, second placed team will win one game more than the last placed team (as you can check for N=3).

Final Answer

Final Answer will be the difference of the points total of the first and the second placed teams.
\therefore ans = 3*(N-1) - ceil((N-2)/2)*3 = 3*(N/2)

If using C++, be sure to use 64 bit integer to avoid unnecessary overflow errors.

SOLUTIONS:

Setter's Solution 
#include<bits/stdc++.h>
using namespace std;

int main() {
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		int64_t ans = (n - 1) * 3 - ceil((double)(n - 2) / 2) * 3;
		cout << ans << "\n";
	}
	return 0;
}

For doubts, please leave them in the comment section, I’ll address them.

1 Like
2

can you tell me why u used this ??
Actually, I’m a beginner so I don’t know the logic behind this.

(n - 1) * 3 - ceil((double)(n - 2) / 2) * 3
1 Like
3

Ceil is a Function Which returns the smallest which is greater than or equal to x if pass x in ceil function…
And other than that All things Are basic calculations…

1 Like
4

Its is assumed that the first placed team have won all the round they played, Hence they are in the top.
Now, In round robin technique every team/ player gets to play against every other team. This means every team has got N-1 rounds to play.

Since the first placed team has won all the round they played , every other team will have exactly N-2 rounds in which they may win or loose.

Now to maximize the difference between the first placed team and the second placed team. Points of the second placed team should be minimum possible without changing its standing.

This will happen only when they won and loose equally.
4 wins 4 looses ( 8 rounds )
or
5 wins 4 looses ( 9 rounds )

This derives the formula.

Round to play = n-2
minimum possible wins without changing its standing = rounds / 2;
points for each round win = 3

therefore,

points for the first placed team = 3 * ( N - 1 )
points for the second placed team = ceil ( double (n-2)/2)*3

Ceil has no effect on integers that is why n-2 is type casted to double type.

3 Likes
5

Hey @satyam08 :wave: ,
If you talk about double values (0.2,0.02…etc) then this function replaces that with round up integer. like (0.5 ,0.1 , 0.9 etc) to 1.
Thus when something is divided and having a ceil function. example ceil(n/k) then it finds first number that is divisible by k greater than equal to n.
example:
ceil(4/2) = 2 (4 is dividing number 2 thus this is the answer)
ceil(5/2) = 3 (because 6 is the next multiple of 2).

2 Likes
6

The answer can be simplified

(n/2)*3 // can be put in place of
(n-1)*3 - ceil((double)(n-2) / 2) * 3