angelg's blog

By angelg, 10 years ago, In English

Hello, I have been trying to solve a problem from a Gym Contest (http://codeforces.me/gym/100484/attachments — 100484G — Highways). It seems like an straightfoward Kruskal implementation to me. At first, I was using a vector to store all the edges, but that resulted in MLE in testcase 21. Only then I came to realize N could be upto 10^4, and there's no way to store 10^4 * 10^4 edges without getting a MLE veredict.

Is there an heuristic or data structure to quickly calculate the minimum distance between all the points and generate the MST of the given graph?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

why you want to store 10^4 * 10^4 edges the maximum number of edges you need to store is 10^4 edge

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

you do not need to store it , just calculate it every time . Also kruskal will not work in this problem cause u cannot sort 10^8 edges . so use prim with arraylist implementation

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

    what's the wrong with kruskal why you need to store 10^8 edge ?

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

      As far as i can remember , here , there are 10^4 nodes . and 10^5 edges are given that i "cannot" take and i have to make a spanning tree . So total choice of edge can be at most 10^8 — min(0,10^5) . In kruskal i need to take each edge and sort them ascending in weight , which here is not possible

    • »
      »
      »
      10 years ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      As they are 10^4 nodes, there are 10^8 possibles edges to generate a MST with Kruskal. As far as I know, you need to have all the edges and sort them with increasing weight or cost. After that you greedily choose the edges that won't generate a cycle or loop on the MST.

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

    Thank you. I should've thought about implementing Prim's algorithm on this one as it will be avoid storing all the edges, and I will just need to calculate the minimun. I think I was blocked as I already solved a similar version of this problem with a lower N ( 2 < N <= 750).