hereicomewf's blog

Spanning Tree Problem
By hereicomewf, history, 9 years ago, In English

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

  • Vote: I like it
  • +11
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone prove this idea?

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 ?

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply