## 10034 - Freckles

Moderator: Board moderators

b3yours3lf
New poster
Posts: 44
Joined: Wed Aug 14, 2002 3:02 am
thanks for reply, Grinder, but that's not the problem...
i have make stupid mistake at the part u point..

i compare set[k] with set[e[j].v2] but value of set[e[j].v2] will change in the loop..

jandujar
New poster
Posts: 8
Joined: Tue Mar 09, 2004 10:17 pm

### 10034 "Problem A: Freckles" Input/Output & WA

I recode this code

I have this code

[cpp]
#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <vector>
#include <math.h>

using namespace std;

/* Tipos */

struct EdgeOfGraph {
int vertex1,vertex2;
float weight;
};

typedef EdgeOfGraph edge;

typedef struct tipo{
float x;
float y;
}tipo;
typedef vector<tipo>punto;

/* Variables globales */

edge *edges,*edgesOfTree;
int v1,v2,nEdges,nVertices,*set;

punto puntos(101); //hay numero de puntos maximo de 100 el 0 no lo utilizo
int numeropuntos=0;

/* Make Set */
void Make_set(int set[])
{
int ctr1;
for(ctr1=1;ctr1<=set[0];ctr1++)
set[ctr1]=ctr1;
};

{
int ctr1,ctr2,prevVal;
if(set[x1]==set[x2]) return ;
if(set[x1]<set[x2])
{prevVal=set[x2];
set[x2]=set[x1];
for(ctr1=1;ctr1<=set[0];ctr1++)
if(set[ctr1]==prevVal) set[ctr1]=set[x2];
return ;
}
if(set[x2]<set[x1])
{prevVal=set[x1];
set[x1]=set[x2];
for(ctr1=1;ctr1<=set[0];ctr1++)
if(set[ctr1]==prevVal) set[ctr1]=set[x1];
return ;
}
}

float distancia(float x1,float y1, float x2, float y2){
return ((x2-x1)*(x2-x1) + (y2-y1)*(y2-y1));
}

void get_Edges(){

int ctrl=1;
int vertice1=1;
int vertice2=2;

while (ctrl<=nEdges){
while (vertice2<=numeropuntos){
edges[ctrl].vertex1=vertice1;
edges[ctrl].vertex2=vertice2;
edges[ctrl].weight=distancia(puntos[vertice1].x,puntos[vertice1].y,puntos[vertice2].x,puntos[vertice2].y);
vertice2++;
ctrl++;
}

vertice1++;
vertice2=vertice1+1;
}

}

/* Sort Edges */
void sort_Edges(edge edges[])
{
int ctr1,ctr2,ctr3;
edge temp;
for(ctr1=2;ctr1<=nEdges;ctr1++)
{
temp=edges[ctr1];
ctr2=ctr1;
while(ctr2>1 && temp.weight<edges[ctr2-1].weight)
{edges[ctr2]=edges[ctr2-1];
ctr2--;
};
if(ctr2!=ctr1)
edges[ctr2]=temp;
}
}

/* Kruskal */

void implementKruskal(edge edges[],edge edgesOfTree[],int set[])
{int ctr1,ctr2=1;
for(ctr1=1;ctr1<=edges[0].vertex1;ctr1++)
{if(set[edges[ctr1].vertex1]!=set[edges[ctr1].vertex2])
{
edgesOfTree[ctr2++]=edges[ctr1];
};
}
edgesOfTree[0].vertex1=edgesOfTree[0].vertex2=edgesOfTree[0].weight=ctr2-1;
}

/* Recorremos los arcos sumando el resultado */
float salida=0;
int i;

for (i=1;i<=edgesOfTree[0].vertex1;i++){
salida+=sqrt(edges.weight);
}
printf("%.2lf\n",salida);
}

/* Ejecucion Kruskal */

int Kruskal(int nNodos)
{

set=(int *)malloc(sizeof(int) * (nNodos+1));
nEdges=nNodos*(nNodos -1)/2; //Maximo numero de nodos

edges=(edge *)malloc(sizeof(edge) * (nEdges+1));
edgesOfTree=(edge *)malloc(sizeof(edge) * (nEdges+1));

edges[0].vertex1=edges[0].vertex2=edges[0].weight=nEdges;
edgesOfTree[0].vertex1=edgesOfTree[0].vertex2=edgesOfTree[0].weight=nEdges;

// Carga las aristas
get_Edges();

// Ordena
sort_Edges(edges);

// Preparo el set
set[0]=nNodos;
Make_set(set);

// Ejecuto kruskal
implementKruskal(edges,edgesOfTree,set);

return 0;
}

/* A partir de aqui se acaba kruskal */

float distancia_minima(int indice){
float min=100000000;
float temp=100000000;
int i;

for(i=indice+1;i<numeropuntos;i++){

temp=distancia(puntos[indice].x,puntos[indice].y,puntos.x,puntos.y);
//cout<<"temp es:"<<temp<<endl;
if (temp<min){min=temp;}
}

return min;
}

int main(int argc, char *argv[])
{
int numerotest=0;
int i=0;
float x,y;
float salida=0;

// 200 es el tama
Last edited by jandujar on Wed Mar 10, 2004 8:25 am, edited 1 time in total.

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA
It seems that you have used the proper algorithm( Kruskal), but your code is far too long. I think you are considering extra things which is not required. For example, there is no need to define your own sort function, when a built in one is available.

Another thing, I have noticed in your code is you are passing parameters to the main function, which although not wrong, but is unnecessary.

You are also using dynamic memory allocation at various places, this is redundand. Since the number of points is given in advance, just use static array.

jandujar
New poster
Posts: 8
Joined: Tue Mar 09, 2004 10:17 pm

### I still need help

Thank, I know the code isn't acurancy. (I will recode when it's necessary)

I have got a "kruskal" algorithm and then I have recode it.

Seems that works , but always give me Wrong Answer. Why?

alu_mathics
Learning poster
Posts: 55
Joined: Sat Jan 24, 2004 9:30 pm
Location: Chittagong
Contact:
You can replace float by double.(infact all)
You wrote:
float salida=0;
int i;

for (i=1;i<=edgesOfTree[0].vertex1;i++){
salida+=sqrt(edges.weight);
}
printf("%.2lf\n",salida);
}
cuii e

jandujar
New poster
Posts: 8
Joined: Tue Mar 09, 2004 10:17 pm

### Float -> Double

I tried with all floats to doubles and don't work.
Thanks

Any other suggest?

jandujar
New poster
Posts: 8
Joined: Tue Mar 09, 2004 10:17 pm

### I think the problem is output

I Think the problem is output.

I write:

while(numtests>0)

cout<<number whith 2 decimal precition (redonded, shall i try truncated?)
cout<<endl;

end while

Is this correct?

jandujar
New poster
Posts: 8
Joined: Tue Mar 09, 2004 10:17 pm

### INPUT/OUTPUT example

I have this input:
[cpp]
10

2
1.4 0.4
1.0 0.3

1
3.4 5.0

10
4.2 1.6
0.3 4.6
6.2 0.0
8.9 6.8
3.9 6.7
6.0 3.3
9.7 7.4
1.5 0.7
6.5 8.9
2.1 3.0

1
6.6 7.3

9
8.0 3.2
0.9 9.7
6.8 7.6
8.9 2.1
9.6 6.0
8.6 6.2
6.4 9.1
5.0 8.8
3.1 1.8

9
4.0 7.7
4.4 1.7
8.3 2.0
1.8 8.2
2.8 7.0
2.4 2.2
4.4 0.1
7.9 2.4
7.3 6.2

2
0.6 4.0
9.1 8.5

6
8.0 3.4
7.7 5.4
7.7 4.6
9.9 0.3
8.7 6.9
3.4 1.6

1
6.7 7.5

4
9.1 0.8
8.0 9.0
9.0 9.1
7.5 5.1

[/cpp]

And this output

[cpp]
0.41

0.00

22.69

0.00

16.15

15.90

9.62

8.37

0.00

9.21
[/cpp]

Is this correct? Thanks

Nota: I use this program to generate inputs.

[cpp]
#include <iostream.h>
#include <time.h>
#include <stdlib.h>

void puntorandom(){
int input1, input2;

input1 = rand() * 10 / (RAND_MAX + 1);
input2 = rand() * 10 / (RAND_MAX + 1);

cout<<input1<<"."<<input2;
}

int main()
{
int puntos,i,j;
srand(time(NULL));

cout<<10<<endl<<endl;

for (i=0; i<10 ; i++)
{
puntos= rand() * 10 / (RAND_MAX + 1) +1;
cout<<puntos<<endl;
for (j=0;j<puntos;j++){

puntorandom();
cout<<" ";
puntorandom();
cout<<endl;
}
cout<<endl;

}
}
[/cpp]

Subeen
Experienced poster
Posts: 127
Joined: Tue Nov 06, 2001 2:00 am
Contact:
jandujar, my acepted program prints the following output for your given input:

Code: Select all

``````0.41

0.00

23.94

0.00

20.06

18.22

9.62

12.42

0.00

9.52
``````

jandujar
New poster
Posts: 8
Joined: Tue Mar 09, 2004 10:17 pm
Thanks Subeen!!!

So, my code is incorrect (only works in some cases!!!!)

jandujar
New poster
Posts: 8
Joined: Tue Mar 09, 2004 10:17 pm

### Finaly I Did it

Thanks to Subeen your output save me.

Finally I implement Prim's Algorithm but i hava "Presentation Errors"

Basicaly I do.

[cpp]
While (num--){
...
...

printf("%.2lf\n\n",salida);

}

[/cpp]

with

[cpp]
While (num--){
...
...

printf("%.2lf\n",salida);
if (num>0){
cout<<endl;
}

}

[/cpp]

I tried too , and have the same problem PE

alu_mathics
Learning poster
Posts: 55
Joined: Sat Jan 24, 2004 9:30 pm
Location: Chittagong
Contact:
try this.

scanf("%d",&test);

while(test--)
{
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf(...);//inputs
}

printf("%.2lf\n",salida);
if(test)printf("\n");
}
cuii e

New poster
Posts: 14
Joined: Sat Jul 03, 2004 1:18 pm
Contact:

### 10034 P.E.?

I am getting presentation error WHY?????
Done by prims algo.

Code:
#include<stdio.h>
#include<math.h>
main()
{
int t[100][2],nr[101],n,m,i,j,k;
unsigned long c;
float cost[101][101];
float x[101],y[101],x1,y1;
float min,temp;
scanf("%lu",&c);
while(c)
{ min=0.0;c--;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%f %f",&x1,&y1);
x=x1*10;y=y1*10;
}
for(i=1;i<=n;i++) cost=0.0;
for(i=1;i<=n;i++)
for(j=i+1;j<=n;j++)
{
cost[j]=(x-x[j])*(x-x[j])+(y-y[j])*(y-y[j]);
cost[j]=cost[i][j];
}
for(i=2;i<=n;i++) nr[i]=1;
nr[1]=0;

for(i=1;i<n;i++)
{ m=-2;
for(j=2;j<=n;j++)
{
if(nr[j]!=0 && m==-2) m=j;
if(nr[j]!=0)
if(cost[j][nr[j]]<cost[m][nr[m]]) m=j;
}
temp=cost[m][nr[m]]*100;
temp=sqrt(temp);
min=min+temp ;
nr[m]=0;
for(k=2;k<=n;k++)
{
if(nr[k]!=0)
if(cost[k][nr[k]]>cost[k][m]) nr[k]=m;
}
}
printf("%.2f",min/100);
if(c!=0) printf("\n\n");
}
}
sobhani

Solaris
Learning poster
Posts: 99
Joined: Sun Apr 06, 2003 5:53 am
Contact:
I am not sure, but I got RTE for the following input

1

4
0.0 0.0
1.0 0.0
5.0 0.0
7.0 0.0
Where's the "Any" key?

troy
New poster
Posts: 8
Joined: Fri Jul 23, 2004 10:39 am
Location: New Zealand

### 10034 Freckles - Java Help!! WA

Hi,

I keep getting WA for this problem.
I used Prims Alg to find the MST.

Is there a special Input case Im Missing?

Any suggestions?

// Code content Removed //.