ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
back to board

Discussion of Problem 2025. Line Fighting

SPOILER: My proof on why solution idea works
Posted by John 14 Jan 2022 16:36
So we must try to make teams have equal size. Why?
Consider two teams with x and y members respectively, and consider x > y. Sending a member from first team to second team will only affect matches between these two teams. At first we have x*y different matches between the teams. If we send a player to the second team, there are now x-1 and y+1 members in each team. The matches are now
(x-1)*(y+1) = x*y + (x-y) - 1
As we said x > y, x-y > 0, so x-y-1 >= 0 and our change can't reduce the total number of matches, so it is an optimal change.
This also shows that nothing changes when x = y+1, so if we can't make all teams equal size, just add each of the ones remaining into a different team, making a difference of at most 1 in the sizes of teams.

Now it's your job to compute the number of matches, I won't show that, but it can be done with a one line formula. Good luck :)