rng_58's blog

By rng_58, history, 17 months ago, In English,

AtCoder Grand Contest 010 will be held on Saturday (time). The writer is yutaka1999.

Contest Link

Contest Announcement

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

Let's discuss problems after the contest.

 
 
 
 
  • Vote: I like it  
  • +106
  • Vote: I do not like it  

»
17 months ago, # |
  Vote: I like it +33 Vote: I do not like it

reminder(3hours)

»
17 months ago, # |
  Vote: I like it +5 Vote: I do not like it

That moment when you edit a few lines in your code and AC F after contest -_-

»
17 months ago, # |
  Vote: I like it +138 Vote: I do not like it

Very nice problems, as usual!

»
17 months ago, # |
  Vote: I like it +13 Vote: I do not like it

Can anyone explain B more elaborately ? I could not understand the editorial . Thanks in advance .

  • »
    »
    17 months ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    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.

»
17 months ago, # |
Rev. 2   Vote: I like it +81 Vote: I do not like it

Compared to D, F seems too easy to be F, but I like these problems :)

»
17 months ago, # |
  Vote: I like it +40 Vote: I do not like it
»
17 months ago, # |
  Vote: I like it +10 Vote: I do not like it

How to solve C ?

  • »
    »
    17 months ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    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

»
17 months ago, # |
  Vote: I like it +10 Vote: I do not like it

What is the clear solution for problem B?

»
17 months ago, # |
  Vote: I like it +40 Vote: I do not like it

BTW, I have a question.

Why the color of the Um_nik's handle in the standings page is not red?

  • »
    »
    17 months ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    Starting from some rating (I don't actually know treshold) you can choose color if you want to.

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Tests for task D are weak. My AC solution on this task fails simple test with just two numbers (3 and 4).