×

# WEICOM - Editorial

Author: Trung Nguyen
Tester: Oleksandr Kulkov
Editorialist: Oleksandr Kulkov

MEDIUM

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.

$$\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 $(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.

# RELATED PROBLEMS:

4★melfice
811737
accept rate: 0%

19.7k350498541

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 k-1 in position of n ,we get (k-1)(k)(2k-1)/2 . I could not understand minimum part . Please someone help !!

(11 Dec '17, 08:23)

 1 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 28●4 accept rate: 20%
 0 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 k-1 in position of n ,we get (k-1)(k)(2k-1)/2 . I could not understand minimum part . Please someone help !! answered 11 Dec '17, 07:39 318●1●10 accept rate: 1%
 1 @admin takes wrong solution :). Correct one: https://www.codechef.com/viewsolution/16014971 . answered 30 Oct '17, 21:03 7★chemthan 191●3 accept rate: 12%
 0 "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 3★pk301 627●10 accept rate: 16%
 1 Authors's and Testers's solutions aren't working answered 30 Oct '17, 14:11 2★ramini 61●5 accept rate: 8%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,498
×1,237
×196
×64
×3

question asked: 24 Oct '17, 18:38

question was seen: 2,751 times

last updated: 11 Dec '17, 11:55