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 » Fri Jan 14, 2005 3:04 pm

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

User avatar
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 » Tue Jan 18, 2005 12:42 pm

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?

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

Post by sohel » Wed Jan 19, 2005 9:43 am

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 » Wed Jan 19, 2005 2:10 pm

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

User avatar
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 » Wed Jan 19, 2005 7:33 pm

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 » Wed Jan 19, 2005 9:53 pm

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 » Thu Jan 20, 2005 3:31 am

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

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

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

Post by Ndiyaa ndako » Sat Feb 05, 2005 6:25 am

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 » Sun Feb 20, 2005 12:30 pm

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 » Mon Feb 21, 2005 12:18 am

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 » Mon Feb 21, 2005 5:07 am

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 » Wed May 18, 2005 8:16 am

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;
}

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 » Fri May 20, 2005 3:57 am

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 » Fri May 20, 2005 5:35 am

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 » Tue May 24, 2005 8:17 am

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)”