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.

# | User | Rating |
---|---|---|

1 | tourist | 3690 |

2 | jiangly | 3647 |

3 | Benq | 3581 |

4 | orzdevinwang | 3570 |

5 | Geothermal | 3569 |

5 | cnnfls_csy | 3569 |

7 | Radewoosh | 3509 |

8 | ecnerwala | 3486 |

9 | jqdai0815 | 3474 |

10 | gyh20 | 3447 |

# | User | Contrib. |
---|---|---|

1 | maomao90 | 171 |

2 | adamant | 164 |

3 | awoo | 163 |

4 | TheScrasse | 160 |

5 | nor | 157 |

6 | maroonrk | 155 |

7 | -is-this-fft- | 152 |

8 | Petr | 146 |

9 | orz | 145 |

9 | pajenegod | 145 |

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/24/2024 19:18:02 (i2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Auto comment: topic has been updated by Flvx (previous revision, new revision, compare).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).

Aah, got it. Thanks