AtCoder Grand Contest 010 will be held on Saturday (time). The writer is yutaka1999.
The point values are 300 — 500 — 700 — 1000 — 1600 — 1600.
Let's discuss problems after the contest.
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3821 |
3 | Benq | 3736 |
4 | Radewoosh | 3631 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3388 |
10 | gamegame | 3386 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 161 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
AtCoder Grand Contest 010 will be held on Saturday (time). The writer is yutaka1999.
The point values are 300 — 500 — 700 — 1000 — 1600 — 1600.
Let's discuss problems after the contest.
Name |
---|
reminder(3hours)
That moment when you edit a few lines in your code and AC F after contest -_-
Very nice problems, as usual!
Can anyone explain B more elaborately ? I could not understand the editorial . Thanks in advance .
1) Notice, that after each operation we subtract n * (n + 1) / 2 in total. Thus, sum of all numbers should be divisible by this value.
2) Let k = 2 * sum / (n * (n + 1)). We'll perform exactly k operations in total.
3) Let d[i] = a[i + 1] — a[i] (differences between adjacent elements). Notice, that after each operation all of the differences decrease by 1, but one of them may (or may not if we subtract permutation 1, 2, 3 ... n) be increased by n — 1.
4) First of all, pretend that there are no operations that increase the differences — just subtract k from all of them.
Our goal is to achieve the array of differences filled with 0.
Consider some difference d[i] < 0 for some i. At some step we decreased it by 1, but we could've increase it by n — 1 instead. Thus, we may add n to it couple of times to make it 0. Please note, that we should make no more than k such operations in total. if ABS(d[i]) is not divisible by n — the answer is NO
If d[i] == 0 — we leave this value alone.
if d[i] > 0 — the answer is NO.
If everything is good in the end (we made no more than k increasing operations described above and ended up with array filled with zeroes) — the answer is YES.
Compared to D, F seems too easy to be F, but I like these problems :)
My screencast
How to solve C ?
The editorial has been published, but my solution differs a little bit from the one described there, so I'll try to explain it.
Let's root our tree in any non-leaf vertex (special case: n == 2)
Consider the vertex v such as all of it's children are leaves with values a[0] ... a[k]. We have 2 options for paths containing these leaves:
1) Pair these leaves with each other (paths of the first type)
2) Pair these leaves with some other leaves in some other sub-tree. (paths of the second type)
Consider we decided to have exactly c path of the first type. The thing is that we can calculate the exact value of c.
Let sum = a[0] + a[1] + ... + a[k].
Then a[v] = c + (sum — 2c) = sum — c (We'll subtract c from a[v] when we'll use the paths of the first type; please note, that after that we'll have to use exactly sum — 2c paths of the second type)
c = sum — a[v].
But, there are 2 limitations on c:
1) it has to be non-negative
2) We should be able to actually create c paths of the first type.
To check the second condition calculate the maximum achievable number of paths of the first type. Let max = MAX(a[0],a[1]...a[k]). It's easy to see, that if (2*max <= sum) then maxC = sum / 2; else maxC = sum — max.
If these conditions do not hold — the answer is NO.
Now we can consider the vertex v as a leaf with value (sum — 2c) and solve the problem recursively.
If everything was OK for all of the vertices and (sum — 2c) == 0 for the root — the answer is YES, otherwise the answer is NO
What is the clear solution for problem B?
Editorial (English version starts from the page 4)
My explanation of that solution
BTW, I have a question.
Why the color of the Um_nik's handle in the standings page is not red?
Starting from some rating (I don't actually know treshold) you can choose color if you want to.
I think it's 3200.
Tests for task D are weak. My AC solution on this task fails simple test with just two numbers (3 and 4).