10147 - Highways

[Tomislav Novak]

Done as you said and got WA

[c]
/* @JUDGE_ID: 45892CA 10147 C "MST - Prim" */
#include <stdio.h>

#define MAXTOWNS 750
#define MAXEXISTING 1000
#define BIG 999999999

typedef struct
{
int x, y;
} dot;

typedef struct
{
int towns[MAXTOWNS];
int ntowns;
} vertex;

dot existing[MAXEXISTING], mini[MAXTOWNS][MAXTOWNS];
vertex vertices[MAXTOWNS];
int ntowns, nexisting, nvertices;
double cd[MAXTOWNS][MAXTOWNS], d[MAXTOWNS][MAXTOWNS];

double distance(int, int, int, int);
void connect_vertices();
void calc_distance();
void mst_prim();

int main()
{
int cases, i, j, c;
dot towns[MAXTOWNS];

scanf("%d", &cases);
for (c = 0; c < cases; c++)
{
scanf("%d", &ntowns);

for (i = 0; i < ntowns; i++)
scanf("%d %d", &towns.x, &towns.y);

scanf("%d", &nexisting);

for (i = 0; i < nexisting; i++)
{
scanf("%d %d", &existing.x, &existing.y);
existing.x--; existing.y--;
}

/* calculate the cartesian distance */
for (i = 0; i < ntowns; i++)
for (j = i; j < ntowns; j++)
if (i == j)
cd[j] = 0;
else cd[j] = cd[j] = distance(towns.x, towns[i].y,
towns[j].x, towns[j].y);

/* consider the connected vertices as one vertex & calculate dist*/
connect_vertices();
calc_distance();

if (nvertices == 1)
printf("No new highways need\n");
else
mst_prim();

if (c < cases - 1) printf("\n");
}

return 0;
}

double distance(int x1, int y1, int x2, int y2)
{
return sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
}

void connect_vertices()
{
int i, j, k, nt, state, was[MAXTOWNS], put[MAXTOWNS][MAXTOWNS];

memset(was, 0, sizeof(was));
memset(vertices, 0, sizeof(vertices));
memset(put, 0, sizeof(put));
nvertices = 0;

for (i = 0; i < ntowns; i++)
if (!was[i])
{
vertices[nvertices].towns[vertices[nvertices].ntowns] = i;
vertices[nvertices].ntowns++;
put[nvertices][i] = 1;

state = 1;
while (state)
{
state = 0;
nt = vertices[nvertices].ntowns;
for (j = 0; j < nt; j++)
{
for (k = 0; k < nexisting; k++)
{
if (existing[k].x == vertices[nvertices].towns[j])
if (!was[existing[k].y] &&
!put[nvertices][existing[k].y])
{
vertices[nvertices].towns[vertices[nvertices].ntowns]
= existing[k].y;
vertices[nvertices].ntowns++;
state = 1;
put[nvertices][existing[k].y] = 1;
}
if (existing[k].y == vertices[nvertices].towns[j])
if (!was[existing[k].x] &&
!put[nvertices][existing[k].x])
{
vertices[nvertices].towns[vertices[nvertices].ntowns]
= existing[k].x;
vertices[nvertices].ntowns++;
state = 1;
put[nvertices][existing[k].x] = 1;
}
}
was[vertices[nvertices].towns[j]] = 1;
}
}

nvertices++;
}
}

void calc_distance()
{
int i, j, k, l, mink, minl;
double min;

for (i = 0; i < nvertices; i++)
for (j = i; j < nvertices; j++)
if (i == j)
d[i][j] = 0, mini[i][j].x = i, mini[i][j].y = j;
else
{
min = BIG;
for (k = 0; k < vertices[i].ntowns; k++)
for (l = 0; l < vertices[j].ntowns; l++)
if (cd[vertices[i].towns[k]][vertices[j].towns[l]] < min)
{
min = cd[vertices[i].towns[k]][vertices[j].towns[l]];
mink = k;
minl = l;
}

d[i][j] = d[j][i] = min;
mini[i][j].x = mini[j][i].x = vertices[i].towns[mink];
mini[i][j].y = mini[j][i].y = vertices[j].towns[minl];
}
}

void mst_prim()
{
int key[MAXTOWNS], was[MAXTOWNS], pi[MAXTOWNS];
int i, j, k, u, v;
double min;

for (i = 0; i < nvertices; i++)
key[i] = BIG, was[i] = 0, pi[i] = -1;

key[0] = min = 0;
while (min != BIG)
{
min = BIG;
for (i = 0; i < nvertices; i++)
if (!was[i] && key[i] < min)
min = key[i], u = i;

was = 1;

for (v = 0; v < nvertices; v++)
if (!was[v] && d[v] != 0)
if (d[v] < key[v])
key[v] = d[v], pi[v] = u;
}

for (k = 1; k < nvertices; k++)
printf("%d %d\n", mini[pi[k]][k].x + 1, mini[pi[k]][k].y + 1);

}
[/c]

After studying your posts for a while, I came to a conclusion that Kruskal's algorithm is much more suitable for this problem (which is actually an easy problem).

[Tomislav Novak]

Hi!

Excuse me for opening another thread, but now I have a different kind of problem...
I've implemented Kruskal's algorithm and union set (including union by rank and path compression!) like in CLRS's "Introduction to Algorithms", and still got TLE...

Here's my code:
[c]
#include <stdio.h>

#define MAXTOWNS 750

typedef struct
{
int x, y;
double w;
} edge;

typedef struct
{
int x, y;
} dot;

edge edges[MAXTOWNS * MAXTOWNS];
int parent[MAXTOWNS], rank[MAXTOWNS];
int ntowns, nexisting, nedges;

void make_set(int);
void union_sets(int, int);
void link(int, int);
int find_set(int);
double distance(dot, dot);
int cmp(const void *, const void *);
void mst_kruskal();

int main()
{
dot towns[MAXTOWNS];
int i, j, x, y, casenum, c;

scanf("%d", &casenum);
for (c = 0; c < casenum; c++)
{
scanf("%d", &ntowns);
for (i = 0; i < ntowns; i++)
{
scanf("%d %d", &towns.x, &towns.y);
make_set(i);
}

scanf("%d", &nexisting);
for (i = 0; i < nexisting; i++)
{
scanf("%d %d", &x, &y);
union_sets(x - 1, y - 1);
}

nedges = 0;
for (i = 0; i < ntowns - 1; i++)
for (j = i + 1; j < ntowns; j++)
{
edges[nedges].x = i;
edges[nedges].y = j;
edges[nedges].w = distance(towns, towns[j]);
nedges++;
}

mst_kruskal();

if (c < casenum - 1) printf("\n");
}

return 0;
}

double distance(dot a, dot b)
{
return sqrt((b.x - a.x) * (b.x - a.x) + (b.y - a.y) * (b.y - a.y));
}

void mst_kruskal()
{
int i, built = 0;

qsort(edges, nedges, sizeof(edge), cmp);
for (i = 0; i < nedges; i++)
if (find_set(edges.x) != find_set(edges.y))
{
printf("%d %d\n", edges.x + 1, edges.y + 1);
union_sets(edges.x, edges.y);
built++;
}

if (!built) printf("No new highways need\n");
}

int cmp(const void *e1, const void *e2)
{
double w1, w2;

w1 = ((const edge *)e1)->w;
w2 = ((const edge *)e2)->w;

if (w1 - w2 < 0.001) return -1;
else if (w2 - w1 < 0.001) return 1;
else return 0;
}

void make_set(int u)
{
parent = u;
rank = 0;
}

void union_sets(int u, int v)
{
link(find_set(u), find_set(v));
}

int find_set(int u)
{
if (u != parent)
parent = find_set(parent);

return parent;
}

void link(int u, int v)
{
if (rank > rank[v])
parent[v] = u;
else parent = v;

if (rank == rank[v])
rank[v]++;
}
[/c]
Could qsort() from stdlib be too slow?! Are there any more optimizations I could do?

Thanks in advance,
Tomislav

[nibbler]

qsort is hardly too slow, it can sort over a million numbers in a second.
I haven't tried this problem, but i always prefer Prim for MST because i find it simpler to code, although kruskal is sometimes faster. can't you help more

[Tomislav Novak]

I haven't tried this problem, but i always prefer Prim for MST because i find it simpler to code, although kruskal is sometimes faster.

Oh, I tried Prim, believe me but this is partial MST problem, so Kruskal is more suitable (not to mention it's easier to code)... I've read topics about 10147, most people use Kruskal and don't get TLE...

[CDiMa]

Hi!

Excuse me for opening another thread, but now I have a different kind of problem...
I've implemented Kruskal's algorithm and union set (including union by rank and path compression!) like in CLRS's "Introduction to Algorithms", and still got TLE...

[...]

Could qsort() from stdlib be too slow?! Are there any more optimizations I could do?

Thanks in advance,
Tomislav

This problem is time critical, so it needs to be optimized a bit to stay within time limit.
Definitely qsort() isn't the culprit.
You (as does my ACed solution and many other) are building the complete connection graph, this is O(n^2) and is the slowest part of the prog. Other critical parts are union/find operations and mst_kruskal.
For a start, since you don't need the value of the distance other than for sorting the edges, you may drop the sqrt and inline the calculation to avoid the function call overhead (OJ compiles without this kind of optimizations).
Secondly I'd check your union/find operations. I didn't study your code thoroughly but I think you aren't doing any path compression.
Third, mst_kruskal(). Usually kruskal is fast, but in your case you don't terminate your loop as soon as your mst is complete, meaning that you loop again through all your edges (O(n^2)). By fixing only this you may get within time limit.

As a side note I think that you cmp function should be changed to allow equality
[c]int cmp(const void *e1, const void *e2)
{
double w1, w2;

w1 = ((const edge *)e1)->w;
w2 = ((const edge *)e2)->w;

if (w1 - w2 < -0.001) return -1;
else if (w2 - w1 < -0.001) return 1;
else return 0;
}[/c]

Ciao!!!

Claudio

[Tomislav Novak]

Secondly I'd check your union/find operations. I didn't study your code thoroughly but I think you aren't doing any path compression.

Well, I think I am
[c]
if (u != parent)
parent = find_set(parent);

return parent;
[/c]

Third, mst_kruskal(). Usually kruskal is fast, but in your case you don't terminate your loop as soon as your mst is complete, meaning that you loop again through all your edges (O(n^2)). By fixing only this you may get within time limit.

How can I do that (check whether mst is complete) in a very fast way? I've tried this:
[c]
/* ... in main() ... */
for (i = 0; i < nexisting; i++)
{
scanf("%d %d", &x, &y);
if (find_set(x - 1) != find_set(y - 1))
{
union_sets(x - 1, y - 1);
done++;
}
}
/* ... in mst_kruskal() ... */
for (i = 0; i < nedges; i++)
{
if (done + built + 1 >= ntowns) break;
/* ... */
[/c]
... but still TLE.

Thanks for help anyway... If you have any more ideas, please post...

[CDiMa]

Well, I think I am
[c]
if (u != parent)
parent = find_set(parent);

return parent;
[/c]

I was misled by the recursive formulation...

How can I do that (check whether mst is complete) in a very fast way? I've tried this:
[c]
/* ... in main() ... */
for (i = 0; i < nexisting; i++)
{
scanf("%d %d", &x, &y);
if (find_set(x - 1) != find_set(y - 1))
{
union_sets(x - 1, y - 1);
done++;
}
}
/* ... in mst_kruskal() ... */
for (i = 0; i < nedges; i++)
{
if (done + built + 1 >= ntowns) break;
/* ... */
[/c]
... but still TLE.

This is ok!

Thanks for help anyway... If you have any more ideas, please post...

Not only drop sqrt, drop doubles at all! Your cmp functions needs only to return (e1->w - e2->w).
With this modifications your prog takes a time comparable to mine on a sample with 750 towns and 22 highways.

Good luck!

Ciao!!!

Claudio

[Tomislav Novak]

Not only drop sqrt, drop doubles at all! Your cmp functions needs only to return (e1->w - e2->w).

[c]
int cmp(const void *e1, const void *e2)
{
return ((const edge *)e1)->w1 - ((const edge *)e2)->w2;
}
[/c]
This way program gives incorrect answer for the sample input... Did you have that in mind?

With this modifications your prog takes a time comparable to mine on a sample with 750 towns and 22 highways.

I saw you having 0:00.180 on this problem. Where's the catch?

[CDiMa]

Not only drop sqrt, drop doubles at all! Your cmp functions needs only to return (e1->w - e2->w).

[c]
int cmp(const void *e1, const void *e2)
{
return ((const edge *)e1)->w1 - ((const edge *)e2)->w2;
}
[/c]
This way program gives incorrect answer for the sample input... Did you have that in mind?

Maybe I should have been more explicit
I said to drop doubles so I changed your edge typedef this way:
[c]typedef struct
{
int x, y;
int w;
} edge;[/c]
and dropped sqrt:
[c]dx=towns.x-towns[j].x;
dy=towns.y-towns[j].y:
edges[nedges].w=dx*dx+dy*dy;[/c]
This way you are sorting on int values and the cmp function above works.

With this modifications your prog takes a time comparable to mine on a sample with 750 towns and 22 highways.

I saw you having 0:00.180 on this problem. Where's the catch?

Well, I was comparing my first AC program that implemented the same algorithm as yours.
That prog took more than 6 seconds on the OJ. Comparing the speed of your prog with mine on my samples I saw that it was around 50% slower and so it could easily get TLE. I then changed your prog to not use doubles and got the same speeds as mine.
As for my fast time I used another approach that is briefly explained in the algorithms forum. And BTW I got it ACed only yesterday!

Ciao!!!

Claudio

[Tomislav Novak]

Maybe I should have been more explicit
I said to drop doubles so I changed your edge typedef this way:
[c]typedef struct
{
int x, y;
int w;
} edge;[/c]
and dropped sqrt:
[c]dx=towns.x-towns[j].x;
dy=towns.y-towns[j].y:
edges[nedges].w=dx*dx+dy*dy;[/c]
This way you are sorting on int values and the cmp function above works.

I've done that now and got AC with the running time of 0:08.475

Well, I was comparing my first AC program that implemented the same algorithm as yours.
That prog took more than 6 seconds on the OJ. Comparing the speed of your prog with mine on my samples I saw that it was around 50% slower and so it could easily get TLE. I then changed your prog to not use doubles and got the same speeds as mine.
As for my fast time I used another approach that is briefly explained in the algorithms forum. And BTW I got it ACed only yesterday!

Could sqrt() from math.h be too slow? It really didn't cross my mind that it could be someting that trivial like removing sqrt... Usually that kind of optimization isn't required on programming contests...

I'll take a look at you post in Algorithms forum...

Anyway, thanks for the help!

[CDiMa]

I've done that now and got AC with the running time of 0:08.475

Well done!

Could sqrt() from math.h be too slow? It really didn't cross my mind that it could be someting that trivial like removing sqrt... Usually that kind of optimization isn't required on programming contests...

Only removing sqrt isn't sufficient. The speed improvement comes from dropping doubles both in the edge construction and the comparison used during qsort.
Using an O(n^2) algorithm is slow for the data set of the OJ and to fit within time limit you need all optimizations possible.

Ciao!!!

Claudio

[Tomislav Novak]

Only removing sqrt isn't sufficient. The speed improvement comes from dropping doubles both in the edge construction and the comparison used during qsort.
Using an O(n^2) algorithm is slow for the data set of the OJ and to fit within time limit you need all optimizations possible.

I'll keep that in mind when trying to solve similar problems... I've got AC in 10397 (Connect the Campus) too... It ran only 2 second, although limits are the same as in 10147 (max 750 buildings, max 1000 existing edges).

Thanks.

[Rocky]

Hi
I get acc in 10397 but i get wa in 10147...i think both are so simmiler isn't??can any body help me.....

Thank's In Advance
Rocky

[sclo]

Here, it is not necessary to code union find if we use Kruskal. The reason is that we need to compute O(n^2) distances anyway, and Kruskal without fast union find excluding the sorting part would be O(n^2). The O(n^2) factor from the computation of distances dominates, so we can get by using a very simple and slow kruskal.

[898989]

Salamo Alelko
I get accepted in this problem just from 2 minutes in 9.533s
I know this hard problem to get withen time.
I use the above code exactly but with only one diffrence

in the above code you read the existent nodes and union them (1)

and then after reconstructing data and sorting edges you start again
you start to search about your mst (2)
But the problem occur here You may test the edges that you union in first step (1)
i mean : You union the built edges, then come back to check is it exist!!?

Code: Select all

qsort(edges, nedges, sizeof(edge), cmp); 
for (i = 0; i < nedges; i++) 
if (find_set(edges[i].x) != find_set(edges[i].y)) 
{ 
printf("%d %d\n", edges[i].x + 1, edges[i].y + 1); 
union_sets(edges[i].x, edges[i].y); 
built++; 
} 
the previous is a pattern of ur code which gives TLE

As for me, i do this
typedef struct 
{ 
int x, y; 
double w;
bool used;
} edge;
and with this way, i avoid asking for pre-built edges....by maing this edges
e[i].x = i;
e[i].y = j;
e[i].used = true;