PROBLEM LINK:
Author: Trung Nguyen
Tester: Oleksandr Kulkov
Editorialist: Oleksandr Kulkov
DIFFICULTY:
MEDIUM
PREREQUISITES:
None
PROBLEM:
n players participated in tournaments. Each player compete with each other once. Winner earns 1 point, loser earns 0 points. After the tournament player that won g_i games is awarded by g_i^2 money. You have to check if it is possible that overall earns of players equals k.
QUICK EXPLANATION:
Construct answer with the minimum total score and then iteratively increase it till you get k.
EXPLANATION:
Let’s think of what score at all can we gain? First of all we should note that parity of sum of squares is the same as parity of the sum since x^2 =x \mod 2. Also sum of victories for all players is fixed and always equals to \dfrac{n(n-1)}{2}. Thus gain’s parity should be the same as of this value.
Let’s think of what’s the maximum gain we can earn. If there is match in which player with score a won against player with score b such that b\geq a then if we change the result of match we will gain (b+1)^2+(a-1)^2-b^2-a^2=2(b-a+1)>0. Thus for maximum gain player with score won match against every player with lower score and there are no two players with equal score. This situation is equivalent to one when player k won matches against all players with number less than k and gain k-1 score. Thus maximum total gain is \sum\limits_{k=0}^{n-1} k^2. Note that from that equality yields that flipping the result of game between players with same score increases the answer by 2.
And what about minimum gain? We can see that if there are two numbers with b-a\geq 2 then we can lower the score by decreasing b and increasing a. Thus we can set the lower bound as the situation in which every player scored either \left\lfloor\dfrac n 2\right\rfloor or \left\lfloor\dfrac {n-1}{2}\right\rfloor. Luckily this situation can be obtained.
Consider the following algorithm which builds the matrix a_{ij} with minimum gain for odd n. Let player i win the battle against all players (i-k) \mod n where k is from 1 to \dfrac{n+1}{2} and lose to the others. As you can see i won against j iff j didn’t win against i thus matrix is well defined.
It turns out that to get matrix for even n it’s enough to construct it for n+1 and remove (n+1)^{th} player.
As was mentioned earlier, if we flip the result of game for players who scored same number of games, the total gain will be increased by 2. Keeping doing this optimal way we can get to the answer and maybe fit TL. However it still will be O(n^3) with small constant. To achieve O(n^2) complexity we should do the following thing. While it doesn’t make our gain more than k, choose a player which have maximum score now and make him win all games. Now subtract (n-1)^2 from k and consider only other (n-1) players. Otherwise k is not greater than (n-1)^2 which was obtained in at most O(n) steps and now we can in a fair way do the algorithm which chooses two players with same score and flip their game, it will need only O(n^2) iterations to finish.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.
