1 / 5
Apr 2007

Somebody nows why, when i do the parcial "Minimum spanning tree solution" i receibe less points than i printf the naive solution??

  • created

    Apr '07
  • last reply

    May '07
  • 4

    replies

  • 648

    views

  • 4

    users

Most likely you've implemented MST incorrectly stuck_out_tongue
(It could be also that your program takes far too long to calculate it, but thats less likely.)

In case you mean the result on the status pages, that's because the score is directly proportional to to the length of the network you compute.

And since the the MST is by definition smaller than or equal to an arbitrary tree (or of course any arbitrary connected graph on the vertices) , the result will never be greater than the one of a valid naive solution. (Leaving running time aside).

Regards,
Hive

I was implement this kind of solution in another times.

17 days later

In this problem we want to minimize the score, so less points in the situation you described is not only expected, it is good smile