336 - A Node Too Far

[Mushfiqur Rahman]

A little speech about the problem:

I got at least 6 times WA for the given code ( in the previous post). I posted here bcz I didn't found any bug in my code. I hoped that I will get helped from the great helpers about my problem. But I failed to get help from others.

I think somebody ( cordial persons ) tried to help, but they also failed to help me bcz actually theres no bug in my code. Then whats the problem? The problem is in the judges input data set. I'm telling this bcz in that code I declared an array (int) of size 32. The reason of that is here:

Code: Select all

There will be no more than one (direct) communication line between any pair of nodes, and no network will contain more than 30 nodes.

Then judge was giving me Wrong Ans. But when I changed the size of that array into 32->50 ( by the suggestion of a friend ) then I got Accepted.

Now I think the judge should change his input data set ( where node numbers will not more than 30 ) or should change the statement of the problem according to the judge input data set.

Regards
Mushfiqur Rahman

[rio]

Then judge was giving me Wrong Ans. But when I changed the size of that array into 32->50 ( by the suggestion of a friend ) then I got Accepted.

Now I think the judge should change his input data set ( where node numbers will not more than 30 ) or should change the statement of the problem according to the judge input data set.

The judge data is correct. I verified it using assert(). Node numbers are not more than 30.
I think there was a bug like accessing over bound.
----
Rio

[asmaamagdi]

Hey guy,

I'm really getting frustrated by this problem :S, I don't know what's wrong. I've passed all 153 test cases posted CDiMa & still getting WA. I don't know what's wrong

Code: Select all

struct Graph
{
	int nVertices;
	int nEdges;
	int edges[100][100];
	int degree[100];
}
g;

map<int, int>mp;
bool arr[100][100][100];

void Initialize()
{
	mp.clear();
	map<int,  int>::iterator it;
	int i, j, v, u;
	for(i=0; i<100; i++)
	{
		g.degree[i] = 0;
	}
	for(i=0; i<g.nEdges; i++)
	{
		cin>>v>>u;
		it = mp.find(v);
		if(it == mp.end())
		{
			mp[v] = mp.size();
		}
		it = mp.find(u);
		if(it == mp.end())
		{
			mp[u] = mp.size();
		}
		v = mp[v];
		u = mp[u];
		g.edges[v][g.degree[v]++] = u;
		g.edges[u][g.degree[u]++] = v;
	}
	g.nVertices = mp.size();
}

void TTLL()
{
	int i, j, k, l, n, x, y, temp;
	n = g.nVertices;

	for(i=0; i<n; i++)
	{
		for(j=0; j<n; j++)
		{
			for(k=0; k<n; k++)
			{
				arr[i][j][k] = 0;
				if(i == 0 && j == k)
					arr[i][j][k] = 1;
			}
		}
	}

	for(i=1; i<n; i++)
	{
		for(j=0; j<n; j++)
		{
			for(k=0; k<n; k++)
			{
				if(arr[i-1][j][k])
				{
					arr[i][j][k] = 1;
					for(l=0; l<g.degree[k]; l++)
					{
						arr[i][j][g.edges[k][l]] = 1;
					}
				}
			}
		}
	}
}

& then I just count the number of 1 in arr[ttl][mp[start]] & output mp.size() - number of 1s.

Could any1 plz tell me what's wrong

[linux]

I was getting frequent WA in this problem. I used adjacency lists implemented by arrays. It was handling at most 40 nodes.

After watching this topic I increased the array size and got accepted. Vector implementations though don't have this problem.

It seems there are more than 40 nodes in testcases of judge input. Am I right?

[newton]

enlage size 30 to 100
probably there was a misleading description in specification.

[kangroo]

Hi everyone,
I m repeatedly getting RE for this problem...
below is my code...anyone pls help me...

Code: Select all

vector <int> BFS ( int s , vector < vector <int> > edg)
{
 vector <int> D(1001 , INT_MAX) , color(1001 , 1) , pi(1001 , 0);

 color[s] = 2;
 pi[s] = 0;
 D[s] = 0;
 
 queue <int> Q;
 Q.push (s);
  
 while ( !Q.empty () )
 {
  int u = Q.front();
  Q.pop ();
  for ( int i = 0 ; i < edg[u].size() ; i ++ )
  { 
   int v = edg[u][i];
   if ( color[v] == 1 )
   {
    color[v] = 2;
    D[v] = D[u] + 1;
    pi[v] = u;
    Q.push (v);
   }
   color[u] = 3;
  } 
 } 
 
 return D;
}

int main ()
{
 int e , cas = 1;
 while ( true )
 {
  scanf ( "%d" , &e );
  if ( !e ) break;
  vector < vector <int> > edg(1001);
  for ( int i = 0 ; i < e ; i ++ )
  {
   int a , b;
   scanf ( "%d %d" , &a , &b );
   edg[a].push_back (b);
   edg[b].push_back (a);
  }
  int node , ttl;
  vector < pair <int , int> > node_ttl;
  while ( true )
  {
   scanf ( "%d %d" , &node , &ttl );
   if ( node == 0 && ttl == 0 ) break;
   node_ttl.push_back ( pair <int , int> ( node , ttl ) ); 
  }
  
  for ( int i = 0 ; i < node_ttl.size() ; i ++ )
  {
   printf ( "Case %d: " , cas ++ );
   vector <int> Dis;
   Dis = BFS ( node_ttl[i].first , edg );
   int cnt = 0;
   for ( int j = 0 ; j < Dis.size() ; j ++ )
   {
    if ( Dis[j] > node_ttl[i].second && Dis[j] != INT_MAX ) cnt ++;
   }

   printf("%d nodes not reachable from node %d with TTL = %d.\n",cnt,node_ttl[i].first,node_ttl[i].second);
  }
  //edg.clear();
  //node_ttl.clear();
 }
 return 0;
}

Waiting for a reply...
pls help me!!

[kangroo]

Hi everyone,
I m repeatedly getting RE for this problem...
below is my code...anyone pls help me...

Code: Select all

    vector <int> BFS ( int s , vector < vector <int> > edg)
    {
    vector <int> D(1001 , INT_MAX) , color(1001 , 1) , pi(1001 , 0);

    color[s] = 2;
    pi[s] = 0;
    D[s] = 0;

    queue <int> Q;
    Q.push (s);
     
    while ( !Q.empty () )
    {
      int u = Q.front();
      Q.pop ();
      for ( int i = 0 ; i < edg[u].size() ; i ++ )
      {
       int v = edg[u][i];
       if ( color[v] == 1 )
       {
        color[v] = 2;
        D[v] = D[u] + 1;
        pi[v] = u;
        Q.push (v);
       }
       color[u] = 3;
      }
    }

    return D;
    }

    int main ()
    {
    int e , cas = 1;
    while ( true )
    {
      scanf ( "%d" , &e );
      if ( !e ) break;
      vector < vector <int> > edg(1001);
      for ( int i = 0 ; i < e ; i ++ )
      {
       int a , b;
       scanf ( "%d %d" , &a , &b );
       edg[a].push_back (b);
       edg[b].push_back (a);
      }
      int node , ttl;
      vector < pair <int , int> > node_ttl;
      while ( true )
      {
       scanf ( "%d %d" , &node , &ttl );
       if ( node == 0 && ttl == 0 ) break;
       node_ttl.push_back ( pair <int , int> ( node , ttl ) );
      }
     
      for ( int i = 0 ; i < node_ttl.size() ; i ++ )
      {
       printf ( "Case %d: " , cas ++ );
       vector <int> Dis;
       Dis = BFS ( node_ttl[i].first , edg );
       int cnt = 0;
       for ( int j = 0 ; j < Dis.size() ; j ++ )
       {
        if ( Dis[j] > node_ttl[i].second && Dis[j] != INT_MAX ) cnt ++;
       }

       printf("%d nodes not reachable from node %d with TTL = %d.\n",cnt,node_ttl[i].first,node_ttl[i].second);
      }
      //edg.clear();
      //node_ttl.clear();
    }
    return 0;
    }

Waiting for a reply...
pls help me!!

[a13032002]

A little speech about the problem:

I got at least 6 times WA for the given code ( in the previous post). I posted here bcz I didn't found any bug in my code. I hoped that I will get helped from the great helpers about my problem. But I failed to get help from others.

I think somebody ( cordial persons ) tried to help, but they also failed to help me bcz actually theres no bug in my code. Then whats the problem? The problem is in the judges input data set. I'm telling this bcz in that code I declared an array (int) of size 32. The reason of that is here:

Code: Select all

There will be no more than one (direct) communication line between any pair of nodes, and no network will contain more than 30 nodes.

Then judge was giving me Wrong Ans. But when I changed the size of that array into 32->50 ( by the suggestion of a friend ) then I got Accepted.

Now I think the judge should change his input data set ( where node numbers will not more than 30 ) or should change the statement of the problem according to the judge input data set.

Regards
Mushfiqur Rahman

I got WA for 7 times.But after I changed the size of the array that I declared for the vertex from 30 to 50.And I got Ac

[calicratis19]

AC. there is no isolated input.

[sazzadcsedu]

there is no isoleted vertex in judge input.
so for input-

Code: Select all

1
10 11
10 0 10 1 10 2 12 1 10 0 10 1 10 2 0 0

12 1 is not valid .

i sent code with isoleted & non-isoleted version.
both are being acc.
[/b]

[x140l31]

A little speech about the problem:

I got at least 6 times WA for the given code ( in the previous post). I posted here bcz I didn't found any bug in my code. I hoped that I will get helped from the great helpers about my problem. But I failed to get help from others.

I think somebody ( cordial persons ) tried to help, but they also failed to help me bcz actually theres no bug in my code. Then whats the problem? The problem is in the judges input data set. I'm telling this bcz in that code I declared an array (int) of size 32. The reason of that is here:

Code: Select all

There will be no more than one (direct) communication line between any pair of nodes, and no network will contain more than 30 nodes.

Then judge was giving me Wrong Ans. But when I changed the size of that array into 32->50 ( by the suggestion of a friend ) then I got Accepted.

Now I think the judge should change his input data set ( where node numbers will not more than 30 ) or should change the statement of the problem according to the judge input data set.

Regards
Mushfiqur Rahman

I got WA for 7 times.But after I changed the size of the array that I declared for the vertex from 30 to 50.And I got Ac

Hi,

I also change 30 to 50 in my code, and I get AC. I also tried other sizes, and I get the best time (3th best time with Floyd O.O), with size 31...

It's possible that we have done some mistakes? Or it's uva statement wrong?? We don't know....

[poixp]

I also get WA until i haven't increased the maximum number of connection to node like this:

Code: Select all

struct Node
{
	int Link[2*MAX_N];
	int Count;
};

[nishith]

Getting WA , don't know why.
please give me some critical inputs or help me to find the bugs.

Code: Select all

ACC

[abid_iut]

Can anyone tell where is the problem please...
here is the code

Code: Select all

#include<iostream>
#include<cstdio>
#include<queue>
#define MAX 100
using namespace std;

int path[MAX][MAX];
int distinct[MAX];
int flag[MAX];
int n,index;
int ccount;
long dist[MAX];
queue<int>map;

void initiation(){
	int i,j;
	for(i=0; i<MAX; i++){
		for(j=0; j<MAX; j++){
			path[i][j] = 0;
		}
		distinct[i] = 0;
		flag[i] = 0;
	}
}

void distini(){
	int i;
	for(i=0; i<MAX; i++)
		dist[i] = 2147483647;
}

void bfs(int start){
	int temp;
	int flag = 0;
	while(!map.empty()){
		map.pop();
	}
	
	map.push(start);
	dist[start] = 0;
	while(!map.empty()){
		temp = map.front();
		map.pop();
		for(int i=0; i<index; i++){
			if(distinct[i] != temp){
				if(path[temp][distinct[i]]==1){
					if(dist[distinct[i]] > dist[temp] + 1){
						dist[distinct[i]] = dist[temp] + 1;
						map.push(distinct[i]);
					}
				}
			}
		}
	}
}

int main(){
	int i,j;
	int a,b;
	ccount = 0;
	int c = 0;
	int init = 1;
	int nrc;
	initiation();
	while(scanf("%d",&n)==1&&n){
		index = 0;
		for(i=0; i<n; i++){
			scanf("%d %d",&a,&b);
			if(flag[a] == 0){
				distinct[index] = a;
				flag[a] = 1;
				index++;
			}
			if(flag[b] == 0){
				distinct[index] = b;
				flag[b] = 1;
				index++;
			}
			path[a][b] = path[b][a] = 1;
		}
		int dest,ttl;
		while(scanf("%d %d",&dest,&ttl)==2){
			if(dest==0 && ttl==0)break;
			distini();
			bfs(dest);
			nrc = 0;
			for(j=0; j<index; j++){
				if(dist[distinct[j]]>ttl){
					nrc++;
				}
			}
			printf("Case %d: %d nodes not reachable from node %d with TTL = %d.\n",init,nrc,dest,ttl);
			init++;
		}
		for(j=0; j<MAX; j++){distinct[j] = 0;flag[j] = 0;}
	}
	return 0;
}

[remerson]

I've finally solved this after one wrong answer and a few hours. It is more fiddly than it first looks. I managed rank 62/2333

Some gotchas/hints:

1) Algorithm is graph BFS and with a non-recursive depth track twist. I personally did this with an adjacency list but a matrix should work equally well.

2) Like several other people, if I increased my MAX_EDGES constant from 32 to 64, this was the only difference between AC and WA. I think there's an inaccuracy in the specification here.

3) Part of the reason why I spent so much time is that I also got my algorithm generate graphviz output (coloured nodes - visited blue, unvisited red). I found this useful for diagnosing edge cases and was quite quick to add. I'll leave this as exercise to the reader to implement in their own code

Here is example graphviz output (matching 1.png below):

Code: Select all

graph "start = 1 TTL = 5" {  100 [fillcolor=blue,style=filled]; 2 [fillcolor=blue,style=filled]; 3 [fillcolor=blue,style=filled]; 4 [fillcolor=blue,style=filled]; 5 [fillcolor=blue,style=filled]; 6 [fillcolor=blue,style=filled]; 7 [fillcolor=blue,style=filled]; 8 [fillcolor=blue,style=filled]; 9 [fillcolor=blue,style=filled]; 1000 [fillcolor=blue,style=filled]; 100100 [fillcolor=blue,style=filled]; 1002 [fillcolor=red,style=filled]; 1003 [fillcolor=red,style=filled]; 1004 [fillcolor=blue,style=filled]; 1005 [fillcolor=blue,style=filled]; 1006 [fillcolor=blue,style=filled]; 1007 [fillcolor=blue,style=filled]; 1008 [fillcolor=blue,style=filled]; 1009 [fillcolor=blue,style=filled]; 20 [fillcolor=blue,style=filled]; 2100 [fillcolor=blue,style=filled]; 22 [fillcolor=blue,style=filled]; 23 [fillcolor=blue,style=filled]; 100 -- 2; 100 -- 4; 100 -- 7; 2 -- 3; 3 -- 4; 3 -- 9; 5 -- 6; 5 -- 22; 6 -- 7; 7 -- 8; 7 -- 2100; 8 -- 9; 8 -- 1006; 8 -- 100100; 9 -- 1000; 1000 -- 100100; 1000 -- 20; 1002 -- 1003; 1003 -- 1004; 1004 -- 1005; 1005 -- 1006; 1006 -- 1007; 1007 -- 1008; 1008 -- 1009; 1009 -- 20; 20 -- 2100; 2100 -- 22; 22 -- 23; 
}

4) As was also pointed out above, the large sample input given on this forum is helpful a bit misleading in one specific edge case. From analysing the mismatches between this and my AC code, I think most of the differences are cases where a query is made from a non-existent node. E.g. if only nodes 10,11 defined then asking for query from node 12. I think behaviour of this type of query is undefined and the judge input (rightly) does not care about these cases.

5) In the judge sample input, I've inferred that there are no nodes with self-referential edges i.e. no edge linking node a to node a. I figured this out from comparing with Mark Greve's (excellent) UVA Toolkit site/reference solutions, which show differences in this case with my AC solution (yet both his and my solution are AC by the judge). Hence, again I think the judge input does not include such cases.

Here is another test case - this does not include any queries from undefined nodes. This has long/short cycles and is non-trivial and avoids cases (4) and (5) noted above.

INPUT

Code: Select all

28
100 2 2 3 3 4 4 100
5 6 6 7 7 8 8 9 9 1000 1000 100100 9 3 100 7
1002 1003 1003 1004 1004 1005 1005 1006 1006 1007 1007 1008 1008 1009 1009 20 20 2100 2100 22 22 23
1006 8 1000 20 22 5 7 2100 8 100100
100 5 7 3 1005 3 1004 5 2100 6 1000 99 0 0

0

OUTPUT

Code: Select all

Case 1: 2 nodes not reachable from node 100 with TTL = 5.
Case 2: 4 nodes not reachable from node 7 with TTL = 3.
Case 3: 12 nodes not reachable from node 1005 with TTL = 3.
Case 4: 6 nodes not reachable from node 1004 with TTL = 5.
Case 5: 1 nodes not reachable from node 2100 with TTL = 6.
Case 6: 0 nodes not reachable from node 1000 with TTL = 99.

Attached also are graphviz (dot) graphs for the first 3 cases in the above input (this is the maximum number of file attachments, unfortunately!).

Hope this is useful to someone.