336 - A Node Too Far

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

Moderator: Board moderators

Post Reply
Mushfiqur Rahman
Learning poster
Posts: 56
Joined: Tue Jun 13, 2006 5:18 pm
Location: (CSE, SUST) Sylhet, Bangladesh
Contact:

Post by Mushfiqur Rahman » Tue Jul 03, 2007 6:49 am

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

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Tue Jul 03, 2007 7:23 am

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
New poster
Posts: 27
Joined: Tue Dec 20, 2005 9:14 am
Location: Egypt

Post by asmaamagdi » Sat Mar 01, 2008 3:32 am

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
---
Asmaa Magdi

User avatar
linux
Learning poster
Posts: 56
Joined: Sat Jul 01, 2006 12:21 pm
Location: CA-95054
Contact:

Re: 336 input wrong or misunderstanding?

Post by linux » Sun Sep 21, 2008 10:19 am

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?
Last edited by linux on Fri Oct 10, 2008 5:59 pm, edited 1 time in total.
Solving for fun..

User avatar
newton
Experienced poster
Posts: 162
Joined: Thu Jul 13, 2006 7:07 am
Location: Campus Area. Dhaka.Bangladesh
Contact:

Re: Prob 336(A Node Too Far)-- Runtime Error

Post by newton » Sun Sep 21, 2008 8:13 pm

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

kangroo
New poster
Posts: 13
Joined: Fri Sep 12, 2008 9:12 am

336 : RE

Post by kangroo » Fri Oct 10, 2008 4:36 pm

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
New poster
Posts: 13
Joined: Fri Sep 12, 2008 9:12 am

Re: Prob 336(A Node Too Far)-- Runtime Error

Post by kangroo » Sat Oct 11, 2008 8:07 am

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
New poster
Posts: 5
Joined: Wed Aug 27, 2008 7:05 pm

Re:

Post by a13032002 » Mon Mar 09, 2009 4:59 pm

Mushfiqur Rahman wrote: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
Learning poster
Posts: 76
Joined: Mon Jul 21, 2008 8:50 am
Location: SUST,SYLHET,BANGLADESH.
Contact:

336 WA

Post by calicratis19 » Sat Mar 28, 2009 2:38 pm

AC. there is no isolated input.
Last edited by calicratis19 on Thu Apr 23, 2009 5:11 pm, edited 1 time in total.
Heal The World

sazzadcsedu
Experienced poster
Posts: 136
Joined: Sat Nov 29, 2008 8:01 am
Location: narayangong,bangladesh.
Contact:

336:-important

Post by sazzadcsedu » Mon Mar 30, 2009 9:12 pm


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]
Life is more complicated than algorithm.
http://felix-halim.net/uva/hunting.php?id=32359
For Hints: http://salimsazzad.wordpress.com

x140l31
Learning poster
Posts: 69
Joined: Tue Jan 30, 2007 12:51 am

Re: Re:

Post by x140l31 » Sun Jun 07, 2009 2:48 am

a13032002 wrote:
Mushfiqur Rahman wrote: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
New poster
Posts: 20
Joined: Mon Apr 07, 2008 11:05 am

Re: 336 WA

Post by poixp » Fri Jan 22, 2010 4:38 pm

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
New poster
Posts: 4
Joined: Wed Jul 07, 2010 11:17 pm

Help: 336 WA

Post by nishith » Sun Aug 01, 2010 11:06 am

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
Learning poster
Posts: 82
Joined: Wed Jul 16, 2008 7:34 am

Re: 336 Run Time Error!!

Post by abid_iut » Fri Apr 08, 2011 12:16 pm

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;
}
i love to wait... wait for better... and better will come...
http://akanoi.webs.com/

remerson
New poster
Posts: 4
Joined: Sun Jun 05, 2011 6:32 pm

Re: 336 WA

Post by remerson » Sun Jun 05, 2011 7:27 pm

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 :D

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.
Attachments
3.png
3.png (83.1 KiB) Viewed 5672 times
2.png
2.png (80.98 KiB) Viewed 5672 times
1.png
1.png (80.91 KiB) Viewed 5672 times

Post Reply

Return to “Volume 3 (300-399)”