OJ Board

Posted: **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

Posted: **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

Posted: **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

Posted: **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?

Posted: **Sun Sep 21, 2008 8:13 pm**

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

Posted: **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!!

Posted: **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!!

Posted: **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

Posted: **Sat Mar 28, 2009 2:38 pm**

AC. there is no isolated input.

Posted: **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]

Posted: **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....

Posted: **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;
};

Posted: **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

Posted: **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;
}

Posted: **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

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.

OJ Board

336 - A Node Too Far

Re: 336 input wrong or misunderstanding?

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

336 : RE

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

Re:

336 WA

336:-important

Re: Re:

Re: 336 WA

Help: 336 WA

Re: 336 Run Time Error!!

Re: 336 WA