Блог пользователя Flvx

Doubt in 1889B (Codeforces Round 906 Div 1.)
Автор Flvx, история, 7 месяцев назад, По-английски

Problem Statement: this Is there a way to prove that if we are not able to connect the vertices to 1 in the greedy order that has been suggested, then there exists no other answer?

Thanks.

  • Проголосовать: нравится
  • -1
  • Проголосовать: не нравится

»
7 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by Flvx (previous revision, new revision, compare).

→ Ответить
»
7 месяцев назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Let's call sum of Ak as Sk

If we can connect (i,j) (i,j != 1), it means Si + Sj >= i * j * c

If Si > Sj, then Si + Si >= i * j * c, Si >= i * (j/2) * c

j/2 >= 1, so Si >= i * 1 * c, We can connect (i, 1) and (1, j).

→ Ответить