Editorial for COCI '14 Contest 3 #4 Coci

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Let the ordered pair $(x, y)$ ~(x, y)~ denote the contestant that won $x$ ~x~ points in the first round and $y$ ~y~ points in the second round.

Let's concentrate on a contestant $(a, b)$ ~(a, b)~. In order to find his best possible place, we need to count the contestants $(x, y)$ ~(x, y)~ that are surely better than $(a, b)$ ~(a, b)~ on the total ranking list: their number incremented by $1$ ~1~ is the required best place of contestant $(a, b)$ ~(a, b)~.

If $x > a$ ~x > a~ and $y > b$ ~y > b~, contestant $(x, y)$ ~(x, y)~ is surely better than $(a, b)$ ~(a, b)~. Are there any other contestants that are better? No, there aren't! The rest of the contestants can be in front of $(a, b)$ ~(a, b)~ after the first two rounds for a maximum of $650$ ~650~ points (because they weren't better than him at least in one round), so if all of them win $0$ ~0~ points in the third round, $(a, b)$ ~(a, b)~ catches up if he wins $650$ ~650~ points. Therefore, it is sufficient to only count the contestants $(x, y)$ ~(x, y)~ such that $x > a$ ~x > a~ and $y > b$ ~y > b~.

Let us now find the worst possible place for contestant $(a, b)$ ~(a, b)~. Let us assume that he wins $0$ ~0~ points in the third round. Which contestants $(x, y)$ ~(x, y)~ can be better than him on the total ranking list? Clearly, those aren't the ones with $x < a$ ~x < a~ and $y < b$ ~y < b~ because they also win $0$ ~0~ points. Let us assume that all other contestants $(x, y)$ ~(x, y)~ win $650$ ~650~ points in the third round. In at least one round, they had more or equal points as $(a, b)$ ~(a, b)~. If they had equal points as $(a, b)$ ~(a, b)~, and lost from $(a, b)$ ~(a, b)~ by $650$ ~650~ points in the remaining round, after three rounds they will have the equal sum of points as $(a, b)$ ~(a, b)~ so they are not better than him. In all other cases, they are better.

In a nutshell: in the worst possible scenario for $(a, b)$ ~(a, b)~, contestants $(x, y)$ ~(x, y)~ that are NOT better than him are the ones with $x < a$ ~x < a~ and $y < b$ ~y < b~ and those with $x = a$ ~x = a~, $y = 0$ ~y = 0~, $b = 650$ ~b = 650~ or $y = b$ ~y = b~, $x = 0$ ~x = 0~, $a = 650$ ~a = 650~. The number of such contestants subtracted from $N-1$ ~N-1~ gives us the number of contestants that are better than $(a, b)$ ~(a, b)~ so that number increased by $1$ ~1~ gives the worst possible position of contestant $(a, b)$ ~(a, b)~ after the first three rounds.

Therefore, the task comes down to counting pairs $(x, y)$ ~(x, y)~ such that $x > a$ ~x > a~ and $y > b$ ~y > b~, as well as those such that $x < a$ ~x < a~ and $y < b$ ~y < b~. If the number of pairs $(x, y)$ ~(x, y)~ is stored in a matrix at position $[x][y]$ ~[x][y]~, we need to be able to quickly find the sum of a rectangle in that matrix. We do this by first dynamically calculating the sums of all rectangles starting at corner $(0, 0)$ ~(0, 0)~ and quickly calculate the sum of any rectangle by their mutual subtractions.

Common mistakes of contestants on this task:

some of them who used logarithmic structure (Fenwick tree) forgot that it starts from $1$ ~1~, not from $0$ ~0~
a lot of them didn't notice that contestant $(0, b)$ ~(0, b)~ cannot overtake contestant $(650, b)$ ~(650, b)~ even though the latter one doesn't "majorize" him. In all other "non-majorizing" cases, overtaking is possible.

Comments

There are no comments at the moment.