534 - Frogger

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

Moderator: Board moderators

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

534 - Frogger

Post by Dominik Michniewski » Wed Sep 25, 2002 8:10 am

Could anyone help me?
I use to solve this problem following algorith:

1. read data
2. build full graph - compute connections to all other stones from any.
3. use BFS to find minimal distance which is necessary to reach every stone from all other.
4. output result

What do I miss?
Could anyone send me some special cases?
Is there a problem with rouding errors ?

Best regards
Dominik

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

Post by yiuyuho » Tue Apr 08, 2003 6:12 am

BFS to find minimal distance?

I don't understand, may be you implement it differently. But a BFS will reach all vertices and stop, right, which you only compute the distance from one stone to all others, but nothing about inter-connection?

Or Am I misunderstanding?

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

Post by yiuyuho » Tue Apr 08, 2003 6:16 am

Is there another way of doing this problem by MST, Prims?

turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:

Post by turuthok » Tue Apr 08, 2003 7:34 am

I just got this AC-ed this morning ... I used Floyd-Warshall for this problem ...

-turuthok-
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Tue Apr 08, 2003 7:45 am

I change my implementation to Floyd and got Acc too ....

Thanks all
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam » Tue Apr 08, 2003 9:10 am

i also used dfs for the first time and got TLE..
then i just changed it to floyd and got ac..
actually the statement of the problem is confusing...
---
anupam :oops: :oops: :oops: :oops:
"Everything should be made simple, but not always simpler"

sunkist
New poster
Posts: 5
Joined: Sun Jun 15, 2003 2:11 am

Post by sunkist » Sun Jun 15, 2003 2:27 am

Can someone please either give me some cases or help check my code, because my solution got wa even though the implementation is correct

[c]
#include <stdio.h>
#include <string.h>
#include <math.h>

int n,i,j,count = 1;
long k,l;
int coord[200][2];
long matrix[200][200];

long min(long a,long b) {
if (a > b) return b;
else return a;
}

int main () {
while (1) {
scanf("%d",&n);
if (n == 0) return 0;
memset(matrix,0,sizeof(matrix));
for (i = 0;i < n;i++) scanf("%d %d",&coord[0],&coord[1]);
for (i = 0;i < n;i++) {
for (j = 0;j < n;j++) {
if (i != j) {
k = (long) (coord[0] - coord[j][0]);
l = (long) (coord[1] - coord[j][1]);
matrix[j] = k * k + l * l;
}
}
}
for (i = 0;i < n;i++) {
for (j = 0;j < n;j++) {
for (k = 0;k < n;k++) {
if ((i != j) && (j != k))
if (matrix[k] > min(matrix[j],matrix[j][k]))
matrix[k] = min(matrix[j],matrix[j][k]);
}
}
}
printf("Scenario #%d\n",count);
printf("Frog Distance = %.3lf\n\n",sqrt((double)matrix[0][1]));
count++;
}
}
[/c]

sunkist
New poster
Posts: 5
Joined: Sun Jun 15, 2003 2:11 am

Post by sunkist » Sun Jun 15, 2003 2:31 am

Can someone please either give me some cases or help check my code, because my solution got wa even though the implementation is correct

[c]
#include <stdio.h>
#include <string.h>
#include <math.h>

int n,i,j,count = 1;
long k,l;
int coord[200][2];
long matrix[200][200];

long min(long a,long b) {
if (a > b) return b;
else return a;
}

int main () {
while (1) {
scanf("%d",&n);
if (n == 0) return 0;
memset(matrix,0,sizeof(matrix));
for (i = 0;i < n;i++) scanf("%d %d",&coord[0],&coord[1]);
for (i = 0;i < n;i++) {
for (j = 0;j < n;j++) {
if (i != j) {
k = (long) (coord[0] - coord[j][0]);
l = (long) (coord[1] - coord[j][1]);
matrix[j] = k * k + l * l;
}
}
}
for (i = 0;i < n;i++) {
for (j = 0;j < n;j++) {
for (k = 0;k < n;k++) {
if ((i != j) && (j != k))
if (matrix[k] > min(matrix[j],matrix[j][k]))
matrix[k] = min(matrix[j],matrix[j][k]);
}
}
}
printf("Scenario #%d\n",count);
printf("Frog Distance = %.3lf\n\n",sqrt((double)matrix[0][1]));
count++;
}
}
[/c]

sunkist
New poster
Posts: 5
Joined: Sun Jun 15, 2003 2:11 am

Post by sunkist » Sun Jun 15, 2003 2:41 am

Can someone please either give me some cases or help check my code, because my solution got wa even though the implementation is correct

[c]
#include <stdio.h>
#include <string.h>
#include <math.h>

int n,i,j,count = 1;
long k,l;
int coord[200][2];
long matrix[200][200];

long max(long a,long b) {
if (a < b) return b;
else return a;
}

int main () {
while (1) {
scanf("%d",&n);
if (n == 0) return 0;
memset(matrix,0,sizeof(matrix));
for (i = 0;i < n;i++) scanf("%d %d",&coord[0],&coord[1]);
for (i = 0;i < n;i++) {
for (j = 0;j < n;j++) {
if (i != j) {
k = (long) (coord[0] - coord[j][0]);
l = (long) (coord[1] - coord[j][1]);
matrix[j] = k * k + l * l;
}
}
}
for (i = 0;i < n;i++) {
for (j = 0;j < n;j++) {
for (k = 0;k < n;k++) {
if ((i != j) && (j != k) && (i != k))
if (matrix[k] > max(matrix[j],matrix[j][k]))
matrix[k] = max(matrix[j],matrix[j][k]);
}
}
}
printf("Scenario #%d\n",count);
printf("Frog Distance = %.3lf\n\n",sqrt((double)matrix[0][1]));
count++;
}
}
[/c]

sunkist
New poster
Posts: 5
Joined: Sun Jun 15, 2003 2:11 am

Post by sunkist » Sun Jun 15, 2003 2:47 am

Can someone please either give me some cases or help check my code, because my solution got wa even though the implementation is correct

[c]
#include <stdio.h>
#include <string.h>
#include <math.h>

int n,i,j,count = 1;
long k,l;
int coord[200][2];
long matrix[200][200];

long max(long a,long b) {
if (a < b) return b;
else return a;
}

int main () {
while (1) {
scanf("%d",&n);
if (n == 0) return 0;
memset(matrix,0,sizeof(matrix));
for (i = 0;i < n;i++) scanf("%d %d",&coord[0],&coord[1]);
for (i = 0;i < n;i++) {
for (j = 0;j < n;j++) {
if (i != j) {
k = (long) (coord[0] - coord[j][0]);
l = (long) (coord[1] - coord[j][1]);
matrix[j] = k * k + l * l;
}
}
}
for (i = 0;i < n;i++) {
for (j = 0;j < n;j++) {
for (k = 0;k < n;k++) {
if ((i != j) && (j != k) && (i != k))
if (matrix[k] > max(matrix[j],matrix[j][k]))
matrix[k] = max(matrix[j],matrix[j][k]);
}
}
}
printf("Scenario #%d\n",count);
printf("Frog Distance = %.3lf\n\n",sqrt((double)matrix[0][1]));
count++;
}
}
[/c]

sunkist
New poster
Posts: 5
Joined: Sun Jun 15, 2003 2:11 am

Post by sunkist » Sun Jun 15, 2003 2:48 am

Can someone please either give me some cases or help check my code, because my solution got wa even though the implementation is correct

Code: Select all

#include <stdio.h>
#include <string.h>
#include <math.h>

int n,i,j,count = 1;
long k,l;
int coord[200][2];
long matrix[200][200];

long max(long a,long b) {
   if (a < b) return b;
   else return a;
}

int main () {
   while (1) {
      scanf("%d",&n);
      if (n == 0) return 0;
      memset(matrix,0,sizeof(matrix));
      for (i = 0;i < n;i++) scanf("%d %d",&coord[i][0],&coord[i][1]);
      for (i = 0;i < n;i++) {
         for (j = 0;j < n;j++) {
            if (i != j) {
               k = (long) (coord[i][0] - coord[j][0]);
               l = (long) (coord[i][1] - coord[j][1]);
               matrix[i][j] = k * k + l * l;
            }
         }
      }
      for (i = 0;i < n;i++) {
         for (j = 0;j < n;j++) {
            for (k = 0;k < n;k++) {
               if ((i != j) && (j != k) && (i != k))
                  if (matrix[i][k] > max(matrix[i][j],matrix[j][k]))
                     matrix[i][k] = max(matrix[i][j],matrix[j][k]);
            }
         }
      }
      printf("Scenario #%d\n",count);
      printf("Frog Distance = %.3lf\n\n",sqrt((double)matrix[0][1]));
      count++;
   }
}

bigbit
New poster
Posts: 4
Joined: Fri Jun 27, 2003 3:39 pm

534-frogger- help!

Post by bigbit » Fri Jun 27, 2003 3:44 pm

What is output for:

5
1 0
2 0
3 0
4 0
4 1

I need more test cases. Please help!

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

534

Post by Eduard » Wed Apr 07, 2004 9:54 pm

Please help me.Tell me where I'm worong.
I use Floyd Warshal's algoritm.
[pascal] Deleted...[/pascal]
Last edited by Eduard on Thu Apr 08, 2004 6:23 pm, edited 1 time in total.
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

Post by Eduard » Thu Apr 08, 2004 6:19 pm

I find my bag ... at the beginning matrix must be infinity(like a maxlongint) not 0.
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

wanderley2k
New poster
Posts: 28
Joined: Mon Mar 01, 2004 11:29 pm

534: Why wrong? Is MST solution?

Post by wanderley2k » Wed Sep 01, 2004 12:20 pm

Hi,

I tried to solve the 534 and implemented MST-Kruskal and nothing.

Do Problem want to know the minimax jumpy? Ok?

Have Someone input for test?

My Code:

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

#define MAX_VERTICES 205
#define MAX_ARESTAS 206*206
#define INFINITO 1000000000000.0

typedef struct {
int x, y;
} Ponto;

typedef struct {
int u, v;
bool usada;
double peso;
} Aresta;

Aresta arestas[MAX_ARESTAS]; // Conjunto de Arestas
int id[MAX_VERTICES]; // id da componente que o vertice esta
int sz[MAX_VERTICES]; // Tamanho da componente
int numArestas; // N

Post Reply

Return to “Volume 5 (500-599)”