336 - A Node Too Far

[Sedefcho]

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]

Hello all,

1. Is Claudio's output from an ACC program ?
I guess so.

Surely, the fastest one ATM

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]

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

[CDiMa]

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]

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]

yeah,it's dfs,actually.
but it isnt why i got WA,is it?

[CDiMa]

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]

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

[CDiMa]

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]

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

[roni]

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

[roticv]

Use a circular queue.

[shihabrc]

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

[ayon]

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

[shihabrc]

But I'm still gettin WA. 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]