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

Автор hereicomewf, история, 9 лет назад, По-английски

Can anyone explain the solution to this question ? http://acm.hdu.edu.cn/showproblem.php?pid=4253

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

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

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

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

I've first seen this problem on spoj, as it was given as a part of bubblecup's qualification round in 2013. Bubblecup has a tradition of publishing qualification round solutions using explanations provided by contestants that solved them.

Here is the solution booklet from 2013 in which you can search for "Two famous companies".

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

Can someone prove this idea?

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

    I couldn't prove it formally but the main idea is that if you add P to all edges of some company, then the optimal MST (under the given constraints) itself doesn't change because the answer differs by a constant. If you add P to all edges of the first company for example, then the answer would be simply ans + P * K where ans is the answer of the unmodified problem.

    This means that you have to find the optimal answer for some P. Obviously if you can find some P for which the MST has exactly K edges then you're done, but such P may not exist, so there is a trick explained in the last few sentences of the editorial explaining that you can simply find the smallest P for which the edges of company A chosen are less than K and then replace some edges with a formula.

    I do understand why it works but I couldn't formally prove it. However, it is very intuitive once you understand the idea.

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

      Why don't binary search P ? If this is possible then the constraint of edge length can be bigger. May be the solution relies on the fact that MAX_EDGE is much smaller than the number of edges ?

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

        It would be very useful to submit binary search approach to check whether it fails, because in my opinion it should work. I can't check it at the moment, but I will tomorrow.