PROBLEM LINK:Author: Trung Nguyen 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(n1)}{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+(a1)^2b^2a^2=2(ba+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 $k1$ score. Thus maximum total gain is $\sum\limits_{k=0}^{n1} 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 $ba\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 {n1}{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 $(ik) \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. $$\begin{pmatrix}0\end{pmatrix}\to \begin{pmatrix}0 & 0 & 1 \\ 1 & 0 & 0\\ 0 & 1 & 0 \end{pmatrix} \to \begin{pmatrix} 0 & 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 & 1 \\ 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 \end{pmatrix} \to \begin{pmatrix} 0 & 0 & 0 & 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 0 \end{pmatrix}$$ 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 $(n1)^2$ from $k$ and consider only other $(n1)$ players. Otherwise $k$ is not greater than $(n1)^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. RELATED PROBLEMS:asked 24 Oct '17, 18:38

Authors's and Testers's solutions aren't working answered 30 Oct '17, 14:11

@admin takes wrong solution :). Correct one: https://www.codechef.com/viewsolution/16014971 . answered 30 Oct '17, 21:03

I want to ask a question. This question is not related to the editorial. Please give me some karma points. By the way, I don't like that we should have some karma points to post questions :( answered 11 Dec '17, 11:55

"Otherwise kk is not greater than (n−1)2(n−1)2 which was obtained in at most O(n)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(n2)O(n2) iterations to finish." can u please explain a bit why it is O(n) now ? answered 30 Oct '17, 20:35

Hello Guys I am stuck with this problem ... Can anyone explain it in more simple ways ?? I understood that maximum sum can be found by Σn^2=n(n+1)(2n+1)/2 . Now put k1 in position of n ,we get (k1)(k)(2k1)/2 . I could not understand minimum part . Please someone help !! answered 11 Dec '17, 07:39

Hello Guys I am stuck with this problem ... Can anyone explain it in more simple ways ?? I understood that maximum sum can be found by Σn^2=n(n+1)(2n+1)/2 . Now put k1 in position of n ,we get (k1)(k)(2k1)/2 . I could not understand minimum part . Please someone help !!