10807 - Prim

All about problems in Volume 108. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

User avatar
lord_burgos
New poster
Posts: 43
Joined: Mon Oct 13, 2003 4:54 pm
Location: Mexico
Contact:

10807 - Prim

Post by lord_burgos » Mon Jan 24, 2005 6:44 am

I do not understand so that so few accepteds, the algorithm is to check all the possibilities of the first kruskal

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Mon Jan 24, 2005 7:23 am

What I don't understand is how people are solving it in under 0.1 seconds. It took me quite some time to get it below 2 seconds with some fancy branch-and-bound. I would really like to know how se
If only I had as much free time as I did in college...

User avatar
lord_burgos
New poster
Posts: 43
Joined: Mon Oct 13, 2003 4:54 pm
Location: Mexico
Contact:

Post by lord_burgos » Mon Jan 24, 2005 8:31 am

Abednego wrote:What I don't understand is how people are solving it in under 0.1 seconds. It took me quite some time to get it below 2 seconds with some fancy branch-and-bound. I would really like to know how se

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Mon Jan 24, 2005 10:04 am

Ah, that's interesting. I didn't think of doing Kruskal's first and then erasing edges from it. I brute forced the first tree and did Kruskal's only for the second one.
If only I had as much free time as I did in college...

Destination Goa
Experienced poster
Posts: 123
Joined: Thu Feb 10, 2005 4:46 am

Post by Destination Goa » Wed Feb 16, 2005 11:07 pm

I used the following (got AC at 1.556 sec):

1. Keep two best edges for each pair i < j. This might eliminate redundancy in the input.

2. Sort all edges ascendingly on length.

3. Calculate partial sums, i.e. b[k] = l[1]+...+l[k]

3. Try all spanning trees for the first graph (1st edge will be contained always)

4. Run Kruskal for all non-taken edges once the 1st tree is built.

Those partial sums (for both trees) being added to current value and compared to found minumum were a good cutoff point. So was the checking of number of remaining edges. I used these cut-offs in both 1st tree (recursive algo) and 2nd tree (pure Kruskal). I didn't use disjoinh sets. I think they will bring more redundancy with only 10 nodes.
To be the best you must become the best!

Destination Goa
Experienced poster
Posts: 123
Joined: Thu Feb 10, 2005 4:46 am

Post by Destination Goa » Wed Feb 16, 2005 11:19 pm

1.906 sec with disjoint sets for both, 1.598 for disjoint sets for 2nd pure Kruskal. Even being applied to the 2nd Kruskal (where it does not suffer from expensive recoils), it adds more overhead then benefits.
To be the best you must become the best!

Destination Goa
Experienced poster
Posts: 123
Joined: Thu Feb 10, 2005 4:46 am

Post by Destination Goa » Thu Feb 17, 2005 8:46 pm

Ha, now got even brighter idea. Instead of trying 1st tree and then fullfilling the 2nd one only when the 1st one is built, it is better to track both Kruskal colorings at the same time.

The idea is simple: if current edge (edges are sorted) can be placed in either A or B (or both), there is no need to skip it. So, we skip only edges which provide loops for both A and B. Otherwise try one or both suitable cases recursively. Also, like before - take 1st edge to A always.

This way it worked in 0.066 sec.
To be the best you must become the best!

User avatar
lord_burgos
New poster
Posts: 43
Joined: Mon Oct 13, 2003 4:54 pm
Location: Mexico
Contact:

Post by lord_burgos » Thu Feb 17, 2005 9:24 pm

Destination Goa wrote:Ha, now got even brighter idea. Instead of trying 1st tree and then fullfilling the 2nd one only when the 1st one is built, it is better to track both Kruskal colorings at the same time.

The idea is simple: if current edge (edges are sorted) can be placed in either A or B (or both), there is no need to skip it. So, we skip only edges which provide loops for both A and B. Otherwise try one or both suitable cases recursively. Also, like before - take 1st edge to A always.

This way it worked in 0.066 sec.
I'm implement the first idea , it worked in 0.031 sec

Destination Goa
Experienced poster
Posts: 123
Joined: Thu Feb 10, 2005 4:46 am

Post by Destination Goa » Thu Feb 17, 2005 9:33 pm

I wonder how you made it 32 times faster than my solution. Anyway, if we understand each other clearly, your solution has redundancy in such cases:

A X X X X X A A

A-s were assigned to the 1st tree, X-es were skipped and will be fed to the 2nd Kruskal. If the 2nd tree can be built using first 3 X-es, then skipping last 1 or 2 would be redundant recursive step on building A. We can track such cases by updating both trees. I.e. if we take 2nd edge to B (not just skip it), then we can update 2nd coloring and once all 3 skipped edges have gone to B (edges 2,3,4), remaining steps will be tested against A only.
To be the best you must become the best!

User avatar
lord_burgos
New poster
Posts: 43
Joined: Mon Oct 13, 2003 4:54 pm
Location: Mexico
Contact:

Post by lord_burgos » Thu Feb 17, 2005 9:43 pm

Destination Goa wrote:I wonder how you made it 32 times faster than my solution. Anyway, if we understand each other clearly, your solution has redundancy in such cases:

A X X X X X A A

A-s were assigned to the 1st tree, X-es were skipped and will be fed to the 2nd Kruskal. If the 2nd tree can be built using first 3 X-es, then skipping last 1 or 2 would be redundant recursive step on building A. We can track such cases by updating both trees. I.e. if we take 2nd edge to B (not just skip it), then we can update 2nd coloring and once all 3 skipped edges have gone to B (edges 2,3,4), remaining steps will be tested against A only.
my first solution I take .092 sec, but with which I say Igor I put some prunings and checked that it did not grow the first kruskal in such a way that it could not against reducing it with the second

Destination Goa
Experienced poster
Posts: 123
Joined: Thu Feb 10, 2005 4:46 am

Post by Destination Goa » Thu Feb 17, 2005 10:36 pm

Ok. Perhaps that's because you used a better cut-off method. My bounds were:
a) I have enough edges to complete both Kruskals (ne-pos >= rem1+rem2)
b) curent_value + sum of minimal following rem1+rem2 edges is less than found minimum. Or formally cv + b[pos+rem1+rem2] - b[pos] < mv
To be the best you must become the best!

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Thu Dec 08, 2005 1:43 am

The OJ has really poor input data for this one :-( The following solution got AC:

Repeat several times:
- pick a random number x from 0 to 2^m
- run Kruskal on edges where x has zeros
- run Kruskal on edges where x has ones
- add those two and update the result

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Thu Dec 08, 2005 2:14 am

I've found a better approach which gave me AC in 0.008s (the one that I described earlier was in 0.311s).

jan_holmes
Experienced poster
Posts: 136
Joined: Fri Apr 15, 2005 3:47 pm
Location: Singapore
Contact:

10807 - Why WA... Please Help...

Post by jan_holmes » Thu Jun 01, 2006 9:28 pm

Why WA ??? Please Help :

Code: Select all

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <iostream>

//WA...


using namespace std;

struct X {
       int a,b,c;
} grid[1000];

int main () {
    int n,m,usedp,small,smallp;
    bool stat[55];
    bool stat2[55];
    bool found = false;
    int temp = 0;
    int x,y,z;
    while (true) {
          int minLength = 0;
          memset(grid,10000000,sizeof(grid));
          memset(stat,false,sizeof(stat));
          memset(stat2,false,sizeof(stat2));
          scanf("%d",&n);
          if (!n) return 0;
          scanf("%d",&m);
          for (int i=0;i<m;i++) {
              scanf("%d %d %d",&x,&y,&z);
              grid[i].a = x-1;
              grid[i].b = y-1;
              grid[i].c = z;
          }
          usedp = 1;
          stat[0] = true; 
          while (usedp < n) {
                found = false;
                small = -100;
                for (int i=0;i<n;i++) if (stat[i])
                    for (int j=0;j<n;j++) if (!stat[j]) {
                        for (int k=0;k<m;k++) {
                            if (stat2[k]) continue;
                            if (grid[k].a == i && grid[k].b ==j || grid[k].a == j && grid[k].b == i) {
                                          if (small == -100 ||  grid[k].c < small) {
                                                    temp = k;
                                                    found = true;
                                                    small = grid[k].c;
                                                    smallp = j;
                                          }
                            }
                        }
                        if(!found && small == -100) { small = 10000000; smallp = j;}
                        if (found) stat2[temp] = true;
                        found = false;
                    }
                minLength+=small;
                stat[smallp] = true;
                usedp++;
          }
          int minLength2 = 0;
          usedp = 1;
          memset(stat,false,sizeof(stat));
          stat[0] = true;
          while (usedp < n) {
                found = false;
                small = -100;
                for (int i=0;i<n;i++) if (stat[i])
                    for (int j=0;j<n;j++) if (!stat[j]) {
                        for (int k=0;k<m;k++) {
                            if (stat2[k]) continue;
                            if (grid[k].a == i && grid[k].b ==j || grid[k].a == j && grid[k].b == i) {
                                          if (small == -100 ||  grid[k].c < small) {
                                                    temp = k;
                                                    found = true;
                                                    small = grid[k].c;
                                                    smallp = j;
                                          }
                            }
                        }
                        if(!found && small == -100) { small = 10000000; smallp = j;} 
                        if (found) stat2[temp] = true;
                        found = false;
                    }
                minLength2+=small;
                stat[smallp] = true;
                usedp++;
          }
          //printf("%d %d\n",minLength,minLength2);
          if (minLength >= 10000000 || minLength2 >= 10000000) printf("No way!\n");
          else printf("%d\n",minLength+minLength2);
    }
    return 0;
}

                                 
                 
          
Please give me some critical input also... Thx... :D

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Re: 10807 - Why WA... Please Help...

Post by Martin Macko » Fri Jun 02, 2006 8:08 pm

There is already a topic on this problem: http://online-judge.uva.es/board/viewtopic.php?t=7361. Have you read it?

Post Reply

Return to “Volume 108 (10800-10899)”