You are not logged in. Please login at www.codechef.com to post your questions!

×

WEICOM - Editorial

PROBLEM LINK:

Practice
Contest

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.

$$\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:

asked 24 Oct '17, 18:38

melfice's gravatar image

4★melfice
811737
accept rate: 0%

edited 30 Oct '17, 13:47

admin's gravatar image

0★admin ♦♦
19.6k349497539

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) harrypotter04★

Authors's and Testers's solutions aren't working

link

answered 30 Oct '17, 14:11

ramini's gravatar image

2★ramini
615
accept rate: 8%

@admin takes wrong solution :). Correct one: https://www.codechef.com/viewsolution/16014971 .

link

answered 30 Oct '17, 21:03

chemthan's gravatar image

7★chemthan
1913
accept rate: 12%

edited 30 Oct '17, 21:04

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 :(

link

answered 11 Dec '17, 11:55

akash_kmr's gravatar image

4★akash_kmr
284
accept rate: 20%

"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 ?

link

answered 30 Oct '17, 20:35

pk301's gravatar image

3★pk301
62710
accept rate: 16%

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 !!

link

answered 11 Dec '17, 07:39

harrypotter0's gravatar image

4★harrypotter0
318110
accept rate: 1%

edited 11 Dec '17, 07:54

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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,198
×1,219
×178
×64
×3

question asked: 24 Oct '17, 18:38

question was seen: 2,687 times

last updated: 11 Dec '17, 11:55