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
jpfarias
Learning poster
Posts: 98
Joined: Thu Nov 01, 2001 2:00 am
Location: Brazil
Contact:

336

Post by jpfarias » Sat Oct 12, 2002 8:57 pm

Can anyone tell me why my solution got WA?

Test cases wich it fail will of great help!

[cpp]
/* A Node Too Far */

#include <stdio.h>

int grafo[30][30];
int dist[30][30];

int rotulo[30];
int max;
int get_rotulo(int k) {
for (int i=0;;++i) {
if (rotulo == k) {
return i;
} else if (rotulo < 0) {
rotulo = k;
max = i+1;
return i;

}
}
return -1;
}

int main() {
int n;
int caso = 0;
for (;;) {
scanf("%d",&n);
if (!n) {
break;
}
for (int i=0;i<30;++i) {
for (int j=0;j<30;++j) {
grafo[j] = dist[j] = 0;
if (i==j) {
dist[j] = 1;
}
}
rotulo = -1;
}
max = 0;
for (int i=0;i<n;++i) {
int x,y;
scanf("%d %d",&x, &y);
x = get_rotulo(x);
y = get_rotulo(y);
grafo[x][y] = grafo[y][x] = 1;
dist[x][y] = dist[y][x] = 1;
}
for (int k=0;k<max;++k) {
for (int i=0;i<max;++i) {
for (int j=0;j<max;++j) {
if ((dist[j] == 0 && dist[k] && dist[k][j])
|| (dist[j] && dist[i][k] && dist[k][j] && dist[i][j] > dist[i][k] + dist[k][j])) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
for (;;) {
int x, y;
int num = 0;
scanf("%d %d",&x,&y);
if (!x && !y) {
break;
}
x = get_rotulo(x);
for (int i=0;i<max;++i) {
if (dist[x][i]>y && x != i) {
++num;
}
}
printf("Case %d: %d nodes not reachable from node %d with TTL = %d.\n",
++caso,num,rotulo[x],y);
}
}
return 0;
}
[/cpp]

Thanks

Ivan Golubev
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia

Post by Ivan Golubev » Sat Oct 12, 2002 11:07 pm

Input:
4
1 2 2 3 4 5 5 6
1 5 1 1 4 2 0 0
0

jpfarias
Learning poster
Posts: 98
Joined: Thu Nov 01, 2001 2:00 am
Location: Brazil
Contact:

Post by jpfarias » Sun Oct 13, 2002 2:41 am

Just solved it...

The problem was when I cannot reach some node from another...

Thanx anyway!!

ei01036
New poster
Posts: 12
Joined: Wed Jan 15, 2003 1:13 am

Post by ei01036 » Sun Jan 19, 2003 11:04 pm

I'm getting WA all the time... :roll: I tried all the example test cases, the one above and some other inputs, specially some with no connection between 2 networks... if anyone knows of some special input, please tell me! thanx!

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am

Always - Getting WA ... 336 - A node too Far

Post by Red Scorpion » Fri May 09, 2003 9:07 am

Hi, I don't know why I always got WA. I have try all the possibilities for input.
and it woks. But I don't know why always got WA.
Any hint ?
my method : DFS.

Code: Select all

Cut..
Thanks.
Last edited by Red Scorpion on Mon May 26, 2003 4:41 am, edited 1 time in total.

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

Post by titid_gede » Sat May 17, 2003 4:25 pm

well, i dont have any hint. usually DFS leads to TLE, as i got first. i cant compile your prog, since i use public computer. but i think you cannot use something like flood_fill. like this.
1 2
2 3
3 4
1 4
if we start from node 1 then node 4 will got TTL 3. but it should be 1.
anyway i used DFS and got TLE. after changing algo with something like DP then got AC at once :)

with love & light,

titid
Kalo mau kaya, buat apa sekolah?

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am

Post by Red Scorpion » Mon May 19, 2003 4:35 am

Thanks, for replying.
In my code, node 4 have TTL = 1.

if the input :
4
1 2
2 3
3 4
1 4
1 1
1 2
1 3
1 0
0 0

My output produce:
Case 1: 1 nodes not reachable from node 1 with TTL = 1.
Case 2: 0 nodes not reachable from node 1 with TTL = 2.
Case 3: 0 nodes not reachable from node 1 with TTL = 3.
Case 4: 3 nodes not reachable from node 1 with TTL = 0.

Huge Thanks
RS :lol:

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am

Post by Red Scorpion » Mon May 26, 2003 4:45 am

Thanks,
I've got AC when using BFS algorithms. I really don't know why DFS can't solve this problem...

Huge Thanks,
RS :lol: :lol: :lol:

bigbit
New poster
Posts: 4
Joined: Fri Jun 27, 2003 3:39 pm

Post by bigbit » Sun Jul 13, 2003 1:39 pm

My program gets WA when graph has cycle:
Example:

1
1 1
1 0
0 0
0

my program output:
"Case 1: 1 nodes not reachable from node 1 with TTL = 0."

i modifity this, and get ACC :)

Master
Learning poster
Posts: 82
Joined: Thu Oct 10, 2002 1:15 pm
Location: St. Johns, Canada
Contact:

336 -- why wa

Post by Master » Thu Sep 18, 2003 8:35 am

hello,
I am just start to implement the graph algorithms. I am trying to solve the problem 336. I have test it for all the possible case even for disjoin graph. but it is getting WA. Please anyone give me more input or tell me the tricks.

Thanks in advance

M H Rasel
CUET Old Sailor

playerX
Learning poster
Posts: 63
Joined: Fri Apr 25, 2003 11:57 pm
Location: Coimbra, Portugal

Post by playerX » Mon Sep 29, 2003 11:18 pm

i solved it using TTL-depth BFS.

just remember that the number of the node can be >n, something very big (but fits into long int :) ). if this is your problem, a linear search can pass the time limit :p

Master
Learning poster
Posts: 82
Joined: Thu Oct 10, 2002 1:15 pm
Location: St. Johns, Canada
Contact:

Pls Help - 336

Post by Master » Thu Oct 16, 2003 8:54 am

Hi
I am trying to solve this problem But I am surprised that I cannot able to get accept this problem with my level best effort. To learn about this type of problem (BFS problem) I have collect the judge code also and compare with my code. But I don’t found any difference with this two code. So please anyone help me to find the difference. Here is my code

[cpp]
#include<stdio.h>

#define MAX 35

#define INF 99999

#define WHITE 0
#define GRAY 1
#define BLACK 2

int nodelist[MAX],maxnode;
int adjlist[MAX][MAX];
int adjnum[MAX];
int color[MAX];
int d[MAX];

/**************************** Queue ******************/
int queue[MAX], front,rare;

void initqueue(void)
{
front = rare = 0;
}

int del(void)
{
return queue[rare++];
}

void insert(int i)
{
queue[front++] = i;
}

int isempty(void)
{
return (front==rare);
}
/**************************** End of Queue ******************/

void refresh(void)
{
register int i,j;
for(i=0;i<MAX;i++)
{
adjnum = 0;

for(j=0;j<MAX;j++) // change new
adjlist[j]=0;// change new
}

maxnode = 0;

}

int find(int id) // OK!
{
register int i;

for(i= 0 ; i< maxnode; i++)
if(nodelist==id)
return i;

nodelist[maxnode] = id;
return maxnode++;
}
/**************************** Getting input ******************/
void input(int n)
{
register int i,x,y;
int u,v;

for(i=0;i<n;i++)
{
scanf("%d%d",&u,&v);

x = find(u);//
y = find(v);//

adjlist[x][adjnum[x]++] = y;// Adjacency list????
adjlist[y][adjnum[y]++] = x;// Adjacency list????
}
}
/**************************** End of Getting input ******************/

int bfs(int s,const int ttl)
{
int reach = 0,u,v;
register int i;

for(i=0;i<maxnode;i++)
{
color = WHITE;//ok!
d = INF;//ok!
}

color[s] = GRAY;
d[s] = 0; //

initqueue();// ok!
insert(s); // ok!
reach = 1;// ok!

while(!isempty())//ok!
{
u = del(); // ok!

if(d < ttl)
{
for(i=0;i<adjnum;i++)
{
v = adjlist;
if(color[v] == WHITE) // ok!
{
reach++; //ok!
color[v] = GRAY;//ok!
d[v]= d+1;// ok!
insert(v);//ok!
}
// pre. 100 is here
}
}

color = BLACK; // 100
}
return reach;
}

main(void)
{
int caseno = 0 ,n,s,ttl,x,reach;

while(scanf("%d",&n)!=EOF)// funny
{
if(n==0)//
break;//

refresh();// maxnode = 0
input(n);

while(scanf("%d%d",&s,&ttl))
{
if(s==0 && ttl == 0)// funny
break;

x = find(s);//

reach = bfs(x,ttl);
printf("Case %d: %d nodes not reachable from node %d with TTL = %d.\n",++caseno,maxnode - reach,s,ttl);
}
}
return 0;
}
[/cpp]

The judge code is the following
[cpp]


/* @JUDGE_ID: xxxxxxx 336 C++ */

/* Author: Reuber Guerra Duarte(reuber@dcc.ufmg.br) */

#include <stdio.h>
int m[30][30];
int n, pn;
int nodes[30];
int tail, head;
int queue[30];
int v[30];

int search(int id)
{
int i;
for (i = 0; i < n; i++)
if (nodes == id)
return i;
for (i = 0; i <= n; i++)
{
m[n] = 0;
m[n] = 0;
}

nodes[n] = id;

return n++;
}

void visit(int start, int ttl)
{
int t, count, j;
tail = 0;
head = 0;
count = 1;
queue[tail++] = start;

for (j = 0; j < n; j++)
v[j] = -1;
v[start] = 0;

while (tail != head)
{

t = queue[head++];
if (v[t] < ttl)
for (j = 0; j < n; j++)
if (v[j] < 0 && m[t][j])
{
v[j] = v[t] + 1;
queue[tail++] = j;
count++;
}
}

printf("Case %d: %d nodes not reachable from node %d with TTL = %d.\n",++pn, n - count, nodes[start], ttl);

}

int main()
{
int i, j, e1, e2;
while (1 == scanf("%d", &j))
{
if (j == 0)
break;
n = 0;
for (i = 1; i <= j; i++)
{
scanf("%d %d", &e1, &e2);
e1 = search(e1);
e2 = search(e2);
m[e1][e2] = 1;
m[e2][e1] = 1;
}

while (1)
{
scanf("%d %d", &e1, &e2);
if (e1 == 0 && e2 == 0)
break;
e1 = search(e1);
visit(e1, e2);
}
}
return 0;
}
[/cpp]


Thanks in advance
M H Rasel.
CUET OLD SAILOR

sumankar
A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta
Contact:

336:

Post by sumankar » Fri Oct 31, 2003 10:07 am

Any body willing to chk my code ?
Suman.

Cucu
New poster
Posts: 4
Joined: Wed Nov 20, 2002 9:43 pm

336: Output Limit Exceeded!!

Post by Cucu » Thu Nov 06, 2003 12:51 am

I'm trying to solve 336 and i'm having Output Limit Exceeded...
I think I should have a problem with I/O, can you help me??? Please!! I'me getting crazy!!!

[cpp]#include <iostream.h>
#include <map.h>
#include <stack.h>
//#include <queue.h>
#include <stdio.h>

using namespace std;

int visitar (int n0, int n, int max, bool ady [40][40]) {
int i,j,k, visitados=0, d=0,v;
int dist [40];
queue<int> q;

for (i=0; i < n; i++) dist =-1;
dist [n0]=0;
q.push (n0);
q.push (-1);
do {
v=q.front ();
q.pop ();
if (v<0) {
d++;
v=q.front ();
q.push (-1);
} else {
visitados++;
for (i=0; i < n; i++)
if (ady [v] && dist < 0) {
q.push (i);
dist = d+1;
}
}
} while (v>=0 && d <= max);

return visitados;
}

int main () {
int i,j,n,ultimo, p1, p2, c1, c2;
bool ady [40][40];
map<int,int> mapa;
map<int,int>::const_iterator it;
int cont=0;
do {
cin >> n;
if (!n) return 0;
if (!cin) return 0;

if (n < 0) while (true) ultimo++;
ultimo=0;
mapa.clear ();
for (i=0; i < n; i++)
for (j=0; j < n; j++)
ady [j]=false;

for (i=0; i < n; i++) {
cin >> c1 >> c2;
if ((it=mapa.find (c1)) == mapa.end ()) {
p1=ultimo;
mapa [c1]=p1;
ultimo++;
} else p1=it->second;

if ((it=mapa.find (c2)) == mapa.end ()) {
p2=ultimo;
mapa [c2]=p2;
ultimo++;
} else p2=it->second;

ady [p1][p2]=true;
ady [p2][p1]=true;
}

//if (ultimo > 40) while (true) ultimo++;

int n0, ttl, nr;
do {
cin >> n0 >> ttl;
if (!cin) return 0;

if (!n0 && !ttl) break;
if ( (it=mapa.find (n0)) == mapa.end ()) nr = ultimo;
else nr=ultimo-visitar (mapa [n0],ultimo, ttl, ady);
printf ("Case %d: %d nodes not reachable from node %d with TTL = %d.\n",++cont,nr,n0,ttl);
} while (true);

} while (true);
}[/cpp]

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

336 A Node Too Far - What could be wrong?

Post by Observer » Sat Dec 20, 2003 10:33 am

I'm attempting Q336 A Node Too Far, yet I'm getting WA >_<"

Well I must say I couldn't find anything wrong with my code... actually I've solved a great deal of BFS problems before....

So instead of posting my code here, I would like to ask if there's anything I need to take extra care in solving this task. Test cases are also welcomed. Thanks in advance.

P.S. Is the input file terminated by a case where NC = 0?
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Post Reply

Return to “Volume 3 (300-399)”