10803 - Thunder Mountain

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

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

Post by Eduard »

I got AC.Don't need test data. :D
Eduard.
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

Ndiyaa ndako
New poster
Posts: 21
Joined: Sat Sep 25, 2004 3:35 am
Location: Oaxaca de Ju
Contact:

Wrong answer.

Post by Ndiyaa ndako »

As far as I know, the Floyd Warshall algorithm computes also the transitive closure of a graph. That means that if D(i,j) is finite in the final adjacency matrix, then there exists a path between the vertex i and j of the graph.

I deduce that if in the final matrix there is an entry with my tag for infinite then there is a pair of cities such that you cannot travel from one to the other.

Code: Select all

 conected = 1;
 ....
 // The graph and the closure have been updated by the Floyd-Warshall
 // algorithm up to this point.
 for(i=0;i<n;i++)
  for(j=0;j<n;j++)
   conected = conected && closure[i][j];
 if(!conected)
  return -1.0;

 for(i=0;i<n;i++)
  for(j=0;j<n;j++)
   if(graph[i][j]>max&&(i!=j))
    max = graph[i][j];
I check that but I still get "Wrong Answer". What's wrong?

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel »

Your method seems to be correct..
.. but the problem might occur during floating point comparison.

How do you check whether the distance between two nodes is less than or equal to 10 ?

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry »

How do you do the Floyd/Warshall? Do you assume f(a,a) is true?

Ndiyaa ndako
New poster
Posts: 21
Joined: Sat Sep 25, 2004 3:35 am
Location: Oaxaca de Ju
Contact:

My method.

Post by Ndiyaa ndako »

The closure matrix is of integer type.

To determine if two vertices are conected I check if the square of their distance is less or equal than 100 with integer arithmetic. After that I store in the adjacency matrix the square root of the number. The tag for infinite is -1.

Code: Select all

 for(k=0;k<n;k++)
  for(i=0;i<n;i++)
   for(j=0;j<n;j++)
    {
       if(!clausura[i][j])
        clausura[i][j] = clausura[i][k]&&clausura[k][j];
       if(grafo[i][k] >= 0 && grafo[k][j] >= 0 && grafo[i][j] < 0)
         grafo[i][j] = grafo[i][k] + grafo[k][j];
       if(grafo[i][k] >= 0 && grafo[k][j] >= 0 && grafo[i][j] >= 0)
        if(grafo[i][k] + grafo[k][j] < grafo[i][j])
         grafo[i][j] = grafo[i][k] + grafo[k][j];
    }
I have tried that code with both the cases i==j and i != j.

Monsoon
Learning poster
Posts: 66
Joined: Fri Jul 23, 2004 4:42 pm
Location: Poland

Post by Monsoon »

I think that your implementation of Floyd-Warshall algorithm is wrong. Becouse you should create matrix [1..n,1..n,1..n]. And it should looks like this

Code: Select all

grafo[k-1][i][j] = grafo[k-1][i][k] + grafo[k-1][k][j]; 
ofcourse you can reduce the matrix to [1..2,1..n,1..n].

Maybe i'm wrong, i don't why you use closure??

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry »

Monsoon, you don't need that. A two dimension array is enough.

You can send me your code and I'll check it.

Ndiyaa ndako
New poster
Posts: 21
Joined: Sat Sep 25, 2004 3:35 am
Location: Oaxaca de Ju
Contact:

Post by Ndiyaa ndako »

I got it accepted: it was an stupid error about the output format.

Thanks everybody.

murtaza
New poster
Posts: 7
Joined: Tue Jul 20, 2004 7:42 pm
Location: India

Post by murtaza »

Can any one point out the bug in the code ....


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

#define INF 999999999

int grid[101][2];
float gph[101][101];

float floydWarshal( int );


main( )
{
int cases,towns,i,j,m,tmp;
float len;
scanf( "%d", &cases );
for( i = 0;i < cases;i ++ )
{
scanf( "%d", &towns );
for( j = 0;j < towns; j ++ )
scanf( "%d %d", &grid[j][0], &grid[j][1] );
for( j = 0;j < towns;j ++ )
for( m = 0;m < towns;m ++ )
gph[j][m] = INF;
for( j = 0;j < towns;j ++ )
for( m = 0;m <= j;m ++ )
{
tmp = (grid[j][0]-grid[m][0])*(grid[j][0]-grid[m][0])+(grid[j][1]-grid[m][1])*(grid[j][1]-grid[m][1]);
if(tmp <= 100 )
gph[j][m] = gph[m][j] = sqrtf( (float)tmp );
}
printf( "Case #%d:\n", i+1 );
len = floydWarshal( towns );
if( len == -1 )
{
printf( "Send Kurdy\n" );
}
else
printf( "%.4f\n", len );
printf( "\n" );
}
}

float floydWarshal( int towns )
{
int i,j,k;
float max;
for( i = 0;i < towns;i ++ )
for( j = 0;j < towns;j ++ )
for( k = 0;k < towns;k ++ )
{
if( gph[j] > (gph[k] + gph[k][j]) )
gph[j] = (gph[k] + gph[k][j]);
}
max = 0;
for( i = 0;i < towns;i ++ )
for( j = 0;j < towns;j ++ )
if( gph[j] == INF )
return -1;
else if( gph[j] > max )
max = gph[j];
return max;

}
Putting n programmers on a problem will not result in the time of solving the problem to reduce by n.

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post by misof »

the order of the cycles in your implementation of floyd-warshall is wrong, k must be incremented in the outermost cycle
of course, the easiest (and recommended) way to remember this is to understand why the algorithm works and what exactly it computes...

murtaza
New poster
Posts: 7
Joined: Tue Jul 20, 2004 7:42 pm
Location: India

Post by murtaza »

Changed that ..... still WA ... can anyone give me some i/o's to check ???
thanx
Putting n programmers on a problem will not result in the time of solving the problem to reduce by n.

wos
New poster
Posts: 8
Joined: Mon Jul 05, 2004 11:08 am

10803 WA help please

Post by wos »

I spent a few days trying to fix this, no luck, i read the other subject on this problem again no luck :D. So if anyone can give me some test data, i would be very thankful, or point out something wrong in my code ?

Code: Select all

#include <cstdio>
#include <climits>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;

double sqr(int n)
{
  return double(n*n);
}

int sqri(int n)
{
  return n*n;
}

double dist(pair<int, int> a, pair<int, int> b)
{  
  if (sqri(a.first - b.first) + sqri(a.second - b.second) <= 100)
    return sqrt(sqr(a.first - b.first) + sqr(a.second - b.second));    
  else
    return INT_MAX;
}

int main()
{
  int cases;
  double graph[500][500];
  scanf("%i", &cases);
  vector<pair<int, int> > towns;
  for (int c = 1; c <= cases; c++)
  {    
    printf("Case #%i:\n", c);
    towns.clear();
    int n;
    scanf("%i", &n);    
    for (int i = 0; i < n; i++)    
      for (int j = 0; j < n; j++)
        graph[i][j] = INT_MAX;
    for (int i = 0; i < n; i++)
    {
      int x, y;
      scanf("%i %i", &x, &y);
      towns.push_back(pair<int, int>(x, y));      
    }
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++)
        if (i != j)
          graph[j][i] = graph[i][j] = dist(towns[i], towns[j]);     
    /*
    for (int i = 0; i < n; i++)
    {
      for (int j = 0; j < n; j++)
        printf("%15.2lf", graph[i][j]);
      printf("\n");
    }
    */
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++)
        for (int k = 0; k < n; k++)
        {
          double tmp = graph[j][i] + graph[i][k];
          if (graph[j][k] > tmp)
            graph[j][k] = tmp;
        }
    double max = 0;
    bool found = false;
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++)
        if (!(abs(graph[i][j] - INT_MAX) < 1e-7) && max < graph[i][j])
        {
          max = graph[i][j];    
          found = true;
        }
    if (!found)
      printf("Send Kurdy\n");
    else
      printf("%.4lf\n", max);
    printf("\n");    
  }
  return 0;
}

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

Post by Abednego »

Your "infinity" value (INT_MAX) is too big. :-) What happens when inside the Floyd-Warshall, you add INT_MAX and, say, 5?

And also, I don't think your code would ever print "Send Kurdy" because the diagonal entries in the graph are 0.

igor
If only I had as much free time as I did in college...

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf »

Abednego wrote:Your "infinity" value (INT_MAX) is too big. :-) What happens when inside the Floyd-Warshall, you add INT_MAX and, say, 5?
The code assigns INT_MAX to a `double,' so there won't be any overflows.

A test case:

Code: Select all

1

2
0 0
10 0
The correct output is obviously

Code: Select all

Case #1:
10.0000

wos
New poster
Posts: 8
Joined: Mon Jul 05, 2004 11:08 am

Post by wos »

Ok i found one problem i was setting the diagonal values to INT_MAX to avoid getting 0 as a result however that was wrong, because FW then fails. I fixed that and the test case gived by mf now works. Also just to be safe i added a check in FW if a value of any of the nodes it's going through is INT_MAX then i skip that step. But still I get WA.

Post Reply

Return to “Volume 108 (10800-10899)”