PimpedButterfly's blog

Doubt in 1889B (Codeforces Round 906 Div 1.)
By PimpedButterfly, history, 8 months ago, In English

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.

  • Vote: I like it
  • -1
  • Vote: I do not like it

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
8 months ago, # |
  Vote: I like it +5 Vote: I do not like it

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).

→ Reply