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

Автор I_love_Hoang_Yen, история, 3 года назад, По-английски

A month after the Vietnamese National contest have passed. This Friday (Dec 11, 2020), there will be the 2020 Vietnam Regional contest. We will also have an online mirror.

Details of Online Mirror:

Details of Official Contest:

Problems prepared by:

Contest difficulty won't be published before the contest. You can see our previous year contests below: (note that this year may be easier, more difficult or the same difficulty):

UPD: The problems are now on Open Kattis

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

»
3 года назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

The open contest will start soon.

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

Will there be any editorial in english?

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

Is there any simple way of solving Edge removal? (The MST problem)

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Not sure what do you mean by "simple". The solution is based on Kruskal algorithm: There can be multiple MSTs, if there are some equal weight edges connecting same components. So:

    • Process edges in increasing order of weight
    • For edges of some weight w, ignore the edges connecting vertices belonging to same components using only edges with weight < w.
    • Amongst the other edges, find those connecting same components.
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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