### rng_58's blog

By rng_58, history, 2 years ago, , AtCoder Grand Contest 010 will be held on Saturday (time). The writer is yutaka1999.

Contest Announcement

The point values are 300 — 500 — 700 — 1000 — 1600 — 1600.

Let's discuss problems after the contest. agc, Comments (16)
 » 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 NOIf 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.
•  » » » Thank you so much!
 » 2 years ago, # | ← Rev. 2 →   Compared to D, F seems too easy to be F, but I like these problems :)
 »
 » 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 ... 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 + a + ... + 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-negative2) 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,a...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?
•  » »
 » 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).