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

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho » Mon Jun 13, 2005 1:23 pm

Hi all,

I got ACC - so no need to answer. Thanks anyway.

What have I learnt ? Just to share it , so that it is easier for
the others which face same problems later.

1) Using Claudio's approach
( new vertices defined in queries ) I can get ACC.

2) Using mf's approach ( not defining new vertices when I
meet these vertices only in queries ) I also get ACC.

Judging from 1) and 2) I could say the Judge data does not contain
such cases. I mean all queries ( X, some_ttl ) include only such
values for X which have previously been mentioned in the
edge's list.

3) Maybe the most important thing to note is why I was
getting WA at the moment I wrote the previous post.

Well, my problem was the following: I was assuming the numbers
given in the input are separated by at least one SPACE.
Well, the Judge has cases in which the numbers are separated
only by TABs ( no spaces ).

CDiMa
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova

Post by CDiMa » Tue Jun 14, 2005 10:40 am

Sedefcho wrote:Hello all,

1. Is Claudio's output from an ACC program ?
I guess so.
Surely, the fastest one ATM ;)
Sedefcho wrote:I tend to think ( I am quite sure ) Claudio does the same in
his program and it seems mf does the
opposite ( does not define new vertices in such cases ).
At least that explains perfectly the differences which
mf mentions.

Any ideas are welcome.
Yes, my program adds nodes found in queries to the network and it seems that mf's solution doesn't.

My program also tolerates duplicated edges although the problem statement explicitly says that there aren't any in input. In the sample I posted there are cases with self edges and duplicated edges.

Ciao!!!

Claudio

Morning
Experienced poster
Posts: 134
Joined: Fri Aug 01, 2003 2:18 pm
Location: Shanghai China

Post by Morning » Tue Jul 26, 2005 2:29 pm

CDiMa,i'm afraid ur code is wrong

just look at this group of input and output u apply to us

5
1 2 2 3 3 1 4 5 6 2147483647
1 1

ur program's output is 5
which should be 4

isn't it?

and i also got WA,hope someone can help me out

i used a function

Code: Select all

int lookup(int n)
{
	int i;
	for(i = 0;i < numOfNodes;i++)
	{
		if(hash[i] == n) return i;
	}
	hash[i] = n;
	numOfNodes++;
	return i;
}
to store vertices
and my input is

Code: Select all

graph[lookup(beg)][lookup(end)] = graph[lookup(end)][lookup(beg)] = 1;
so what's wrong with my code?

full program

Code: Select all

#include <iostream>
using namespace std;
#define MAX_NODE 100
int graph[MAX_NODE][MAX_NODE];
int visited[MAX_NODE];
int hash[MAX_NODE];
int ttl;
int cnt;
int numOfNodes;
void initGraph()
{
	int i,j;
	for(i = 0;i < MAX_NODE;i++)
	{
		visited[i] = 0;
		for(j = 0;j < MAX_NODE;j++)
			graph[i][j] = 0;
	}
}
void init()
{
	ttl = cnt = numOfNodes = 0;
	initGraph();
	for(int i = 0;i < MAX_NODE;i++)
	{
		hash[i] = -1;
	}
}
int lookup(int n)
{
	int i;
	for(i = 0;i < numOfNodes;i++)
	{
		if(hash[i] == n) return i;
	}
	hash[i] = n;
	numOfNodes++;
	return i;
}
void bfs(int begin,int ttl)
{
	visited[begin] = 1;
	if(ttl == 0) return;
	int i;
	for(i = 0;i < MAX_NODE;i++)
	{
		if(graph[begin][i] == 1 && visited[i] == 0)
		{
			cnt++;
			bfs(i,ttl - 1);
		}
	}
}
int main()
{
	int Cases = 1;
	int numOfEdge;
	int i;
	int beg,end;
	int start;
	while(cin >> numOfEdge)
	{
		if(numOfEdge == 0) break;
		init();

		for(i = 0;i < numOfEdge;i++)
		{
			cin >> beg >> end;
			graph[lookup(beg)][lookup(end)] = graph[lookup(end)][lookup(beg)] = 1;
		}
		while(cin >> start >> ttl)
		{
			if(start == 0 && ttl == 0) break;
			bfs(lookup(start),ttl);
			cout << "Case " << Cases++ << ": " << numOfNodes - cnt - 1 << " nodes not reachable from node " << start << " with TTL = " << ttl << "." << endl;
			ttl = cnt = 0;
			for(i = 0;i < numOfNodes;i++)
				visited[i] = 0;
		}
	}

	return 0;
}
"Learning without thought is useless;thought without learning is dangerous."
"Hold what you really know and tell what you do not know -this will lead to knowledge."-Confucius

CDiMa
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova

Post by CDiMa » Wed Jul 27, 2005 10:07 am

Morning wrote:CDiMa,i'm afraid ur code is wrong

just look at this group of input and output u apply to us

5
1 2 2 3 3 1 4 5 6 2147483647
1 1

ur program's output is 5
which should be 4

isn't it?
Hmmm, I applied this sample to my program and it replied 4...
Then I rerun my program on the big sample and it replied 4 again...
So my sample posted is indeed wrong but my program is right.

What I find amazing is that the source code was last modifiend on Apr 20 2004 and the output of my big sample is dated Mar 18 2005.
So I didn't change the source code since I produced the output!!!

Ciao!!!

Claudio

CDiMa
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova

Post by CDiMa » Wed Jul 27, 2005 10:21 am

Morning wrote:

Code: Select all

void bfs(int begin,int ttl)
{
	visited[begin] = 1;
	if(ttl == 0) return;
	int i;
	for(i = 0;i < MAX_NODE;i++)
	{
		if(graph[begin][i] == 1 && visited[i] == 0)
		{
			cnt++;
			bfs(i,ttl - 1);
		}
	}
}
If I understand it correctly your bfs isn't a real bfs...

Ciao!!!

Claudio

Morning
Experienced poster
Posts: 134
Joined: Fri Aug 01, 2003 2:18 pm
Location: Shanghai China

Post by Morning » Wed Jul 27, 2005 12:59 pm

:oops: yeah,it's dfs,actually.
but it isnt why i got WA,is it?
"Learning without thought is useless;thought without learning is dangerous."
"Hold what you really know and tell what you do not know -this will lead to knowledge."-Confucius

CDiMa
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova

Post by CDiMa » Wed Jul 27, 2005 1:20 pm

Morning wrote::oops: yeah,it's dfs,actually.
but it isnt why i got WA,is it?
It is:

Code: Select all

4
1 2 2 3 3 4 1 3
1 2 0 0
0
Your program gives 1 nodes not reachable while it should be 0.

Ciao!!!

Claudio

Morning
Experienced poster
Posts: 134
Joined: Fri Aug 01, 2003 2:18 pm
Location: Shanghai China

Post by Morning » Wed Jul 27, 2005 2:12 pm

I've understand what's wrong with my code
Thank u,MDima

but here's another problem,my code always get TLE now
i even change my graph data structure from adj matrix to adj list,but still got TLE,can u tell me why?

is there any wired input data in test case?like a node presented by a string?

Code: Select all

#include <iostream>
using namespace std;
#define MAX_NODE 31
int graph[MAX_NODE][MAX_NODE];//now it is a adj list
int numOfLinkNode[MAX_NODE];//help to count numberOfLinkNode of every node
int visited[MAX_NODE];
int hash[MAX_NODE];
int ttl;
int cnt;
int numOfNodes;

void initGraph()
{
	int i;
	for(i = 0;i < MAX_NODE;i++)
	{
		visited[i] = 0;
		numOfLinkNode[i] = 0;
	}
}
void init()
{
	ttl = cnt = numOfNodes = 0;
	initGraph();
	for(int i = 0;i < MAX_NODE;i++)
	{
		hash[i] = -1;
	}
}
int lookup(int n)
{
	int i;
	for(i = 0;i < numOfNodes;i++)
	{
		if(hash[i] == n) return i;
	}
	hash[i] = n;
	numOfNodes++;
	return i;
}
void bfs(int begin,int ttl)
{
	visited[begin] = 1;
	if(ttl == 0) return;
	int i;
	for(i = 0;i < numOfLinkNode[begin];i++)
	{
		if(visited[graph[begin][i]] == 0) cnt++;
		bfs(graph[begin][i],ttl - 1);
	}
}
int main()
{
	int Cases = 1;
	int numOfEdge;
	int i;
	int beg,end;
	int start;
	while(cin >> numOfEdge)
	{
		if(numOfEdge == 0) break;
		init();

		for(i = 0;i < numOfEdge;i++)
		{
			cin >> beg >> end;
			beg = lookup(beg);
			end = lookup(end);
			graph[beg][numOfLinkNode[beg]++] = end;
			graph[end][numOfLinkNode[end]++] = beg;
		}
		while(cin >> start >> ttl)
		{
			if(start == 0 && ttl == 0) break;
			bfs(lookup(start),ttl);
			cout << "Case " << Cases++ << ": " << numOfNodes - cnt - 1 << " nodes not reachable from node " << start << " with TTL = " << ttl << "." << endl;
			cnt = 0;
			for(i = 0;i < numOfNodes;i++)
				visited[i] = 0;
		}
	}

	return 0;
}
and i've tried to send the standard sample solution of this problem to judger,and got TLE,too

so wired
"Learning without thought is useless;thought without learning is dangerous."
"Hold what you really know and tell what you do not know -this will lead to knowledge."-Confucius

CDiMa
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova

Post by CDiMa » Wed Jul 27, 2005 2:37 pm

Morning wrote:I've understand what's wrong with my code
Thank u,MDima

but here's another problem,my code always get TLE now
i even change my graph data structure from adj matrix to adj list,but still got TLE,can u tell me why?

is there any wired input data in test case?like a node presented by a string?
I don't think there is any weird input such as non integer nodes, as I would fail too.
If I understand your code correctly your program is slow because the recursion in your bfs is wrong. A standard bfs would take O(e) where e is the number of edges in the connected component of the starting node. Your recursion terminates when ttl drops to 0 and so I think your complexity reaches something like O(ttl*e^2)

Ciao!!!

Claudio

Morning
Experienced poster
Posts: 134
Joined: Fri Aug 01, 2003 2:18 pm
Location: Shanghai China

Post by Morning » Wed Jul 27, 2005 6:39 pm

CDiMa,thank u indeed,u helped me a lot.
I've correct my code,but it still get WA.but i hope i can find the mistakes myself.
Anyway,thanks again :)
"Learning without thought is useless;thought without learning is dangerous."
"Hold what you really know and tell what you do not know -this will lead to knowledge."-Confucius

roni
New poster
Posts: 11
Joined: Tue Aug 09, 2005 11:57 am
Location: SUST, BANGLADESH
Contact:

336__HELPPPP!!!

Post by roni » Sat Sep 03, 2005 1:13 am

:( i cann't get wrong of my code. It gets runtime error.
Please help anyone.
Is the numbers cannot be stored in long?
here my code:

Code: Select all

#include<stdio.h>					// RUNTIME ERROR

#define MAX 35	

int end, head, number, connection, vertex, ttl, count;
int distance[MAX], queue[MAX*MAX], graph[MAX][MAX];
long value[MAX];
char color[MAX];

void enqueue(int u)
{
	queue[end++]=u;
	number++;
}

int dequeue()
{
	number--;
	return queue[head++];
}

void bfs(int s)	
{
	int i, u;

	for(i = 0;i < vertex; i++)	// n => no. of vertex
	{
		if(i != s)	// s => source
		{
			color[i] = 'w';
			distance[i] = 32560;
		}
	}
	color[s] = 'g';
	distance[s] = 0;

	queue[0] = '/0';
	number = 0; head = 1; end = 1;
	enqueue(s);
	while(number)
	{
		u = dequeue();
		for(i = 0;i < vertex; i++)
		{
			if(graph[u][i])
			{
				if(color[i]=='w')
				{
					color[i]='g';
					distance[i]=distance[u]+1;

					if(distance[i] > ttl)	count++;
					enqueue(i);
				}
			}
		}

		color[u]='b';
	}
}


void main()
{
	int i, j, kase = 1;
	long from, to, u, v, start;
freopen("E:\\test.txt", "rt", stdin);

	while((scanf("%d",&connection)==1) && connection)
	{
		for(i = 0; i < MAX; i++)
			value[i] = 0;

		for(i = 0;i < MAX; i++)
			for(j = 0; j < MAX; j++)
				graph[i][j] = 0;

		vertex=0;
		for(i = 0; i < connection; i++)
		{
			scanf("%ld %ld", &from, &to);

			u = -1;v = -1;
			for(j = 0; j < vertex; j++)
				if(value[j] == from)
					u = j;
				else if(value[j] == to)
					v = j;
				
			if(u == -1)
			{
				u = vertex;
				value[vertex++] = from;
			}

			if(v == -1)
			{
				v = vertex;
				value[vertex++] = to;
			}

			//graph[u][v] = 1;
			//graph[v][u] = 1;
		
			if (u != v) graph[u][v] = graph[v][u] = 1; 
		}

		while(scanf("%ld %d", &start, &ttl) == 2)
		{
			if((start == 0) && (ttl == 0))	break;

			count = 0; 
			for(j = 0; j < vertex; j++)
				if(value[j] == start)
					u = j;

			bfs(u);

			/* For unconnected nodes*/
			for(i = 0; i < vertex; i++)
				if(color[i] == 'w')
					count++;

			printf("Case %d: %d nodes not reachable from node %ld with TTL = %d.\n", kase++, count, start, ttl);
		}
	}
}
roni(SUST)

roticv
Learning poster
Posts: 63
Joined: Sat Dec 11, 2004 9:28 am

Post by roticv » Tue Sep 06, 2005 3:04 am

Use a circular queue.

shihabrc
New poster
Posts: 49
Joined: Sun Sep 18, 2005 10:20 am
Location: CSE,BUET
Contact:

336 A node too far. WA getting mad. Plz someone help

Post by shihabrc » Thu Dec 29, 2005 9:30 pm

I used BFS to solve this.But its givin WA. I don't know why. I've tried lots of input (including loops,disconnected network). All is correct. But Still having WA. Plz some one help.

Should i have 2 consider cases where a node is not in the description but is in the query. Like:

4
0 0 1 2 2 3 3 3
5 1 0 0
My code is:

Code: Select all

//removed after AC
Pleaze help me(with tricky inputs,suggetions anything);

Shihab
Last edited by shihabrc on Thu Jan 05, 2006 10:19 pm, edited 1 time in total.
Shihab
CSE,BUET

ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
Location: buet, dhaka, bangladesh

Re: 336 A node too far. WA getting mad. Plz someone help

Post by ayon » Fri Dec 30, 2005 3:26 pm

shihabrc wrote:Should i have 2 consider cases where a node is not in the description but is in the query.
No, there wont be such cases
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program

shihabrc
New poster
Posts: 49
Joined: Sun Sep 18, 2005 10:20 am
Location: CSE,BUET
Contact:

Post by shihabrc » Wed Jan 04, 2006 6:35 pm

But I'm still gettin WA. :cry: Can anyone gettin AC give me some I/O.(Though i've tried a lot) Sould i have 2 consider any special cases.

-Shihab [/quote]
Shihab
CSE,BUET

Post Reply

Return to “Volume 3 (300-399)”