336 - A Node Too Far

[sohel]

This is a straight forward problem. Just handle the node numbers carefully and apply BFS.

[Observer]

Got Accepted by raising the length of my edge list... Maybe next time I shall try to implement it with linked lists........

But wait... doesn't the problem description say that "there will be no more than one direct communication line between any pair of nodes"?? If it's really so, then there's a mistake in my BFS implementation...???

[technobug]

I had a problem when two graphs were not connected...
I got it AC using F-Warshal.... less than one second as the number of edges is really small...

Guilherme Silveira

[CDiMa]

hi all!

I've been stuck on this one for quite a while.
I found an accepted solution on the board and compared its output to mine on several inputs obtaining always the same answer.
The accepted solution uses an adjacency matrix while I preferred a solution that uses adjacency lists.
To look after the differences between the accepted solution and mine I modified the accepted solution to use adjacency lists. Finally my source and the accepted one differ only in the handling of adjacency while the rest of the source is exactly the same. Still my solution gives WA.

Finally I made a check to see if the count of adjacent nodes to each other is more than 30 and in fact there seems to be more than 30 adjacent nodes to a single node.

The problem statement says that "no network will contain more than 30 nodes" and that "There will be no more than one (direct) communication line between any pair of nodes".
Since the pairs in the input identify the nodes that are connected by a communication line I assumed that I wouldn't get in input redundant couples.

Should I interpret the problem statement in the sense that if multiple pairs of nodes appear I should only consider one edge in the network?

Ciao!!!

Claudio

[CDiMa]

[quote="Master"]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

[CDiMa]

Got Accepted by raising the length of my edge list... Maybe next time I shall try to implement it with linked lists........

But wait... doesn't the problem description say that "there will be no more than one direct communication line between any pair of nodes"?? If it's really so, then there's a mistake in my BFS implementation...???

Check this: http://online-judge.uva.es/board/viewtopic.php?t=5503

Ciao!!!

Claudio

[miras]

[strach]

hi
i have a problem with my program.
For every input i can imagine it works well. I'd appreciate if someone could find a testcase, for which it does wrong.

[cpp]#include <cstdio>
using namespace std;

#define FOR(i,a,b) for(int i=a; i<=b;i++)

const int NN = 50;
int t[NN];
int n;
int E[NN][NN];
int achieved[NN];

void init()
{
FOR(i,0,NN-1)
t=-1;
n=0;
FOR(i,0,NN-1)
FOR(j,0,NN-1)
E[j]=0;

}

int f(int x)
{
int i=0;
while (t!=-1)
{
if (t==x) return i;
i++;
}
t=x;
n=i+1;
return i;
}

void propagate(int node, int TTL)
{
achieved[node]=1;
if (TTL!=0)
{
FOR(i,0,n-1)
if (E[node]==1&&!achieved)
propagate(i,TTL-1);
}

}
int how_many(int node, int TTL)
{
int count=0;
FOR(i,0,NN-1) achieved=0;
propagate(f(node),TTL);
FOR(i,0,n-1) if (achieved==0) count++;
return count;
}

///////////////////////////////////


int main()
{
int k,a,b,test_case=1;
scanf("%d",&k);
while (k>0)
{
init();
FOR(i,0,k-1)
{
scanf("%d %d",&a,&b);
E[f(a)][f(b)]=1;
E[f(b)][f(a)]=1;
};
scanf("%d %d",&a,&b);
while (a!=0)
{
printf("Case %d: %d nodes not reachable from node %d with TTL = %d.\n",test_case, how_many(a,b),a,b);
test_case++;
scanf("%d %d",&a,&b);
}
scanf("%d",&k);
}
return 0;
}
[/cpp]

[Ali Arman Tamal]

I'm getting WA in 336.
I've tried this program using both BFS and Floyd-warshall but still WA.
I've got a lot of WA in this one so please help

I take the node values and keep them in a table as I update the adjacency matrix. Next I do warshall and then start taking the root and TTL. Next I count the unreachable nodes which have a weight greater than TTL.

Am I correct this far

See, what will happen if the TTL is 0 or a very large number. I use 20000 as infinity in my warshall matrix.

Here is my code, please help

Code: Select all

// CUT

int get(int num) 
{ 
   int i=0; 

   for(i=0;i<count;i++)if(table[i]==num)return i; 

   table[i]=num; 
   count++; 
   return count-1; 

} 

// CUT

void main(){

// CUT

while(m) 
   { 
      scanf("%d %d",&i,&j); 
                                
	if(i!=j){ 

      i=get(i); 
      j=get(j); 

      a[i][j]=1; 
      a[j][i]=1; 

	} 

	else get(i);

      m--; 
   } 

// CUT

Please help

[mf]

There may be edges from the vertex to itself, this was a problem is my code too.

Instead of

Code: Select all

 
      a[i][j]=1;
      a[j][i]=1;

you should put something like:

Code: Select all

    if (i != j) a[i][j] = a[j][i] = 1;

[Ali Arman Tamal]

Thanks for your reply. I've changed the code as you suggested (see the changed code ) but still WA .

What's wrong ? Where is the mistake? I'm still trying hard to find it out but no luck yet.

Tell me how you take the vertexes and assign them in adjacency matrix. I may have problems there.

There is one more thing - can there be any isolated vertex. the problem description says

There will be no more than one (direct) communication line between any pair of nodes

but it doesn't say that all the vertices will have at least one edge. How does your code handle this. My code will surely fail in a condition like this.

[CDiMa]

There is one more thing - can there be any isolated vertex. the problem description says

There will be no more than one (direct) communication line between any pair of nodes

but it doesn't say that all the vertices will have at least one edge. How does your code handle this. My code will surely fail in a condition like this.

It is possible to have isolated vertices.
Here you get a collection of my sample inputs to play with:

Code: Select all

16
10 15  15 20  20 25  10 30  30 47  47 50  25 45  45 65
15 35  35 55  20 40  50 55  35 40  55 60  40 60  60 65
35  2  35  3   0  0

14
1 2  2 7  1 3  3 4  3 5  5 10  5 11
4 6  7 6  7 8  7 9  8 9  8  6  6 11
1 1  1 2  3 2  3 3  0 0
16
10 15  15 20  20 25  10 30  30 47  47 50  25 45  45 65
15 35  35 55  20 40  50 55  35 40  55 60  40 60  60 65
35  2  35  3   1  3   0  0

16
1 2  2 7  1 3  3 4  3 5  5 10  5 11
4 6  7 6  7 8  7 9  8 9  8  6  6 11 21 22 22 23
1 1  1 2  3 2  3 3  21 1 0 0

1
1 3
2 0
0 0 

1
1 1
1 0
0 0
 
4
1 2 2 3 4 5 5 6
1 5 1 1 4 2 0 0 

4
1 2
2 3
3 4
1 4
1 1
1 2
1 3
1 0
0 0


5
1 2 2 3 3 1 4 5 6 2147483647
1 1 1 0 4 1 4 2 5 1 6 2 8 2 0 0

10
1 2 1 3 3 5 2 5 3 4 5 4 6 4 7 10 10 9 8 9
2 3 7 2 10 1 0 0
 
4
0 0 1 2 2 3 4 4
1 0 1 1 1 2 1 3 1 4 2 0 2 1 2 2 2 3 2 4 3 0 3 1 3 2 3 3 4 0 4 1 4 2
0 0
 
30
1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 0 0 1
11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 1
21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 1
1 0 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 1 15 1 16 
1 17 1 18 1 19 1 20 1 21 18 0 18 1 18 2 18 3 18 4 18 5 18 6 18 7 18 8 18 9 
18 10 18 11 18 12 18 13 18 14 18 15 0 0
32
1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 0 0 1 5 14 24 13
11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 1
21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 1
1 0 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 1 15 1 16 
1 17 1 18 1 19 1 20 1 21 18 0 18 1 18 2 18 3 18 4 18 5 18 6 18 7 18 8 18 9 
18 10 18 11 18 12 18 13 18 14 18 15 0 0
3
1 2 2 3 4 5
1 0 1 1 1 2 1 3 2 0 2 1 2 2 2 3 3 0 3 1 3 2 3 3 4 0 4 1 4 2 4 3 5 0 5 1 5 2 5 3
0 0
 
1
10 11
10 0 10 1 10 2 12 1 10 0 10 1 10 2 0 0
0

And here is my output:

Code: Select all

Case 1: 5 nodes not reachable from node 35 with TTL = 2.
Case 2: 1 nodes not reachable from node 35 with TTL = 3.
Case 3: 8 nodes not reachable from node 1 with TTL = 1.
Case 4: 5 nodes not reachable from node 1 with TTL = 2.
Case 5: 3 nodes not reachable from node 3 with TTL = 2.
Case 6: 1 nodes not reachable from node 3 with TTL = 3.
Case 7: 6 nodes not reachable from node 35 with TTL = 2.
Case 8: 2 nodes not reachable from node 35 with TTL = 3.
Case 9: 13 nodes not reachable from node 1 with TTL = 3.
Case 10: 11 nodes not reachable from node 1 with TTL = 1.
Case 11: 8 nodes not reachable from node 1 with TTL = 2.
Case 12: 6 nodes not reachable from node 3 with TTL = 2.
Case 13: 4 nodes not reachable from node 3 with TTL = 3.
Case 14: 12 nodes not reachable from node 21 with TTL = 1.
Case 15: 2 nodes not reachable from node 2 with TTL = 0.
Case 16: 0 nodes not reachable from node 1 with TTL = 0.
Case 17: 3 nodes not reachable from node 1 with TTL = 5.
Case 18: 4 nodes not reachable from node 1 with TTL = 1.
Case 19: 3 nodes not reachable from node 4 with TTL = 2.
Case 20: 1 nodes not reachable from node 1 with TTL = 1.
Case 21: 0 nodes not reachable from node 1 with TTL = 2.
Case 22: 0 nodes not reachable from node 1 with TTL = 3.
Case 23: 3 nodes not reachable from node 1 with TTL = 0.
Case 24: 5 nodes not reachable from node 1 with TTL = 1.
Case 25: 7 nodes not reachable from node 1 with TTL = 0.
Case 26: 6 nodes not reachable from node 4 with TTL = 1.
Case 27: 6 nodes not reachable from node 4 with TTL = 2.
Case 28: 6 nodes not reachable from node 5 with TTL = 1.
Case 29: 6 nodes not reachable from node 6 with TTL = 2.
Case 30: 7 nodes not reachable from node 8 with TTL = 2.
Case 31: 4 nodes not reachable from node 2 with TTL = 3.
Case 32: 7 nodes not reachable from node 7 with TTL = 2.
Case 33: 7 nodes not reachable from node 10 with TTL = 1.
Case 34: 4 nodes not reachable from node 1 with TTL = 0.
Case 35: 3 nodes not reachable from node 1 with TTL = 1.
Case 36: 2 nodes not reachable from node 1 with TTL = 2.
Case 37: 2 nodes not reachable from node 1 with TTL = 3.
Case 38: 2 nodes not reachable from node 1 with TTL = 4.
Case 39: 4 nodes not reachable from node 2 with TTL = 0.
Case 40: 2 nodes not reachable from node 2 with TTL = 1.
Case 41: 2 nodes not reachable from node 2 with TTL = 2.
Case 42: 2 nodes not reachable from node 2 with TTL = 3.
Case 43: 2 nodes not reachable from node 2 with TTL = 4.
Case 44: 4 nodes not reachable from node 3 with TTL = 0.
Case 45: 3 nodes not reachable from node 3 with TTL = 1.
Case 46: 2 nodes not reachable from node 3 with TTL = 2.
Case 47: 2 nodes not reachable from node 3 with TTL = 3.
Case 48: 4 nodes not reachable from node 4 with TTL = 0.
Case 49: 4 nodes not reachable from node 4 with TTL = 1.
Case 50: 4 nodes not reachable from node 4 with TTL = 2.
Case 51: 29 nodes not reachable from node 1 with TTL = 0.
Case 52: 25 nodes not reachable from node 1 with TTL = 1.
Case 53: 21 nodes not reachable from node 1 with TTL = 2.
Case 54: 17 nodes not reachable from node 1 with TTL = 3.
Case 55: 13 nodes not reachable from node 1 with TTL = 4.
Case 56: 10 nodes not reachable from node 1 with TTL = 5.
Case 57: 8 nodes not reachable from node 1 with TTL = 6.
Case 58: 6 nodes not reachable from node 1 with TTL = 7.
Case 59: 4 nodes not reachable from node 1 with TTL = 8.
Case 60: 2 nodes not reachable from node 1 with TTL = 9.
Case 61: 0 nodes not reachable from node 1 with TTL = 10.
Case 62: 0 nodes not reachable from node 1 with TTL = 11.
Case 63: 0 nodes not reachable from node 1 with TTL = 12.
Case 64: 0 nodes not reachable from node 1 with TTL = 13.
Case 65: 0 nodes not reachable from node 1 with TTL = 14.
Case 66: 0 nodes not reachable from node 1 with TTL = 15.
Case 67: 0 nodes not reachable from node 1 with TTL = 16.
Case 68: 0 nodes not reachable from node 1 with TTL = 17.
Case 69: 0 nodes not reachable from node 1 with TTL = 18.
Case 70: 0 nodes not reachable from node 1 with TTL = 19.
Case 71: 0 nodes not reachable from node 1 with TTL = 20.
Case 72: 0 nodes not reachable from node 1 with TTL = 21.
Case 73: 29 nodes not reachable from node 18 with TTL = 0.
Case 74: 27 nodes not reachable from node 18 with TTL = 1.
Case 75: 25 nodes not reachable from node 18 with TTL = 2.
Case 76: 23 nodes not reachable from node 18 with TTL = 3.
Case 77: 19 nodes not reachable from node 18 with TTL = 4.
Case 78: 15 nodes not reachable from node 18 with TTL = 5.
Case 79: 11 nodes not reachable from node 18 with TTL = 6.
Case 80: 7 nodes not reachable from node 18 with TTL = 7.
Case 81: 5 nodes not reachable from node 18 with TTL = 8.
Case 82: 4 nodes not reachable from node 18 with TTL = 9.
Case 83: 3 nodes not reachable from node 18 with TTL = 10.
Case 84: 2 nodes not reachable from node 18 with TTL = 11.
Case 85: 1 nodes not reachable from node 18 with TTL = 12.
Case 86: 0 nodes not reachable from node 18 with TTL = 13.
Case 87: 0 nodes not reachable from node 18 with TTL = 14.
Case 88: 0 nodes not reachable from node 18 with TTL = 15.
Case 89: 29 nodes not reachable from node 1 with TTL = 0.
Case 90: 25 nodes not reachable from node 1 with TTL = 1.
Case 91: 21 nodes not reachable from node 1 with TTL = 2.
Case 92: 17 nodes not reachable from node 1 with TTL = 3.
Case 93: 13 nodes not reachable from node 1 with TTL = 4.
Case 94: 9 nodes not reachable from node 1 with TTL = 5.
Case 95: 6 nodes not reachable from node 1 with TTL = 6.
Case 96: 4 nodes not reachable from node 1 with TTL = 7.
Case 97: 2 nodes not reachable from node 1 with TTL = 8.
Case 98: 1 nodes not reachable from node 1 with TTL = 9.
Case 99: 0 nodes not reachable from node 1 with TTL = 10.
Case 100: 0 nodes not reachable from node 1 with TTL = 11.
Case 101: 0 nodes not reachable from node 1 with TTL = 12.
Case 102: 0 nodes not reachable from node 1 with TTL = 13.
Case 103: 0 nodes not reachable from node 1 with TTL = 14.
Case 104: 0 nodes not reachable from node 1 with TTL = 15.
Case 105: 0 nodes not reachable from node 1 with TTL = 16.
Case 106: 0 nodes not reachable from node 1 with TTL = 17.
Case 107: 0 nodes not reachable from node 1 with TTL = 18.
Case 108: 0 nodes not reachable from node 1 with TTL = 19.
Case 109: 0 nodes not reachable from node 1 with TTL = 20.
Case 110: 0 nodes not reachable from node 1 with TTL = 21.
Case 111: 29 nodes not reachable from node 18 with TTL = 0.
Case 112: 27 nodes not reachable from node 18 with TTL = 1.
Case 113: 25 nodes not reachable from node 18 with TTL = 2.
Case 114: 23 nodes not reachable from node 18 with TTL = 3.
Case 115: 19 nodes not reachable from node 18 with TTL = 4.
Case 116: 14 nodes not reachable from node 18 with TTL = 5.
Case 117: 8 nodes not reachable from node 18 with TTL = 6.
Case 118: 3 nodes not reachable from node 18 with TTL = 7.
Case 119: 1 nodes not reachable from node 18 with TTL = 8.
Case 120: 0 nodes not reachable from node 18 with TTL = 9.
Case 121: 0 nodes not reachable from node 18 with TTL = 10.
Case 122: 0 nodes not reachable from node 18 with TTL = 11.
Case 123: 0 nodes not reachable from node 18 with TTL = 12.
Case 124: 0 nodes not reachable from node 18 with TTL = 13.
Case 125: 0 nodes not reachable from node 18 with TTL = 14.
Case 126: 0 nodes not reachable from node 18 with TTL = 15.
Case 127: 4 nodes not reachable from node 1 with TTL = 0.
Case 128: 3 nodes not reachable from node 1 with TTL = 1.
Case 129: 2 nodes not reachable from node 1 with TTL = 2.
Case 130: 2 nodes not reachable from node 1 with TTL = 3.
Case 131: 4 nodes not reachable from node 2 with TTL = 0.
Case 132: 2 nodes not reachable from node 2 with TTL = 1.
Case 133: 2 nodes not reachable from node 2 with TTL = 2.
Case 134: 2 nodes not reachable from node 2 with TTL = 3.
Case 135: 4 nodes not reachable from node 3 with TTL = 0.
Case 136: 3 nodes not reachable from node 3 with TTL = 1.
Case 137: 2 nodes not reachable from node 3 with TTL = 2.
Case 138: 2 nodes not reachable from node 3 with TTL = 3.
Case 139: 4 nodes not reachable from node 4 with TTL = 0.
Case 140: 3 nodes not reachable from node 4 with TTL = 1.
Case 141: 3 nodes not reachable from node 4 with TTL = 2.
Case 142: 3 nodes not reachable from node 4 with TTL = 3.
Case 143: 4 nodes not reachable from node 5 with TTL = 0.
Case 144: 3 nodes not reachable from node 5 with TTL = 1.
Case 145: 3 nodes not reachable from node 5 with TTL = 2.
Case 146: 3 nodes not reachable from node 5 with TTL = 3.
Case 147: 2 nodes not reachable from node 10 with TTL = 0.
Case 148: 1 nodes not reachable from node 10 with TTL = 1.
Case 149: 1 nodes not reachable from node 10 with TTL = 2.
Case 150: 2 nodes not reachable from node 12 with TTL = 1.
Case 151: 2 nodes not reachable from node 10 with TTL = 0.
Case 152: 1 nodes not reachable from node 10 with TTL = 1.
Case 153: 1 nodes not reachable from node 10 with TTL = 2.

Hope this helps...

Ciao!!!

Claudio

[mf]

Well, CDiMa's output does not matches my. Here's a diff:

Code: Select all

7,8c7,8
< Case 7: 6 nodes not reachable from node 35 with TTL = 2.
< Case 8: 2 nodes not reachable from node 35 with TTL = 3.
---
> Case 7: 5 nodes not reachable from node 35 with TTL = 2.
> Case 8: 1 nodes not reachable from node 35 with TTL = 3.
24,29c24,29
< Case 24: 5 nodes not reachable from node 1 with TTL = 1.
< Case 25: 7 nodes not reachable from node 1 with TTL = 0.
< Case 26: 6 nodes not reachable from node 4 with TTL = 1.
< Case 27: 6 nodes not reachable from node 4 with TTL = 2.
< Case 28: 6 nodes not reachable from node 5 with TTL = 1.
< Case 29: 6 nodes not reachable from node 6 with TTL = 2.
---
> Case 24: 4 nodes not reachable from node 1 with TTL = 1.
> Case 25: 6 nodes not reachable from node 1 with TTL = 0.
> Case 26: 5 nodes not reachable from node 4 with TTL = 1.
> Case 27: 5 nodes not reachable from node 4 with TTL = 2.
> Case 28: 5 nodes not reachable from node 5 with TTL = 1.
> Case 29: 5 nodes not reachable from node 6 with TTL = 2.
147,149c147,149
< Case 147: 2 nodes not reachable from node 10 with TTL = 0.
< Case 148: 1 nodes not reachable from node 10 with TTL = 1.
< Case 149: 1 nodes not reachable from node 10 with TTL = 2.
---
> Case 147: 1 nodes not reachable from node 10 with TTL = 0.
> Case 148: 0 nodes not reachable from node 10 with TTL = 1.
> Case 149: 0 nodes not reachable from node 10 with TTL = 2.
151,153c151,153
< Case 151: 2 nodes not reachable from node 10 with TTL = 0.
< Case 152: 1 nodes not reachable from node 10 with TTL = 1.
< Case 153: 1 nodes not reachable from node 10 with TTL = 2.
---
> Case 151: 1 nodes not reachable from node 10 with TTL = 0.
> Case 152: 0 nodes not reachable from node 10 with TTL = 1.
> Case 153: 0 nodes not reachable from node 10 with TTL = 2.

My code doesn't check for isolated vertices, so perhaps there are no such cases in the judge's input.

[Ali Arman Tamal]

YeeeHaaa
I got AC

The main problem was - there are some isolated vertices and judge creates them by assigning an edge to themselves - self cycles.

My program ignored all the i j inputs when i==j
But what I should have done is

*) if ( i ! = j ) update matrix and put i and j into the total vertex list ( if not previously done before)

*) else just put i into the total vertex list

Then doing the processing will give correct output.

My previous BFS code also gave AC when I updated it this way.

Thanks a lot, mf and CDiMa. You have been very helpful.

Good Luck

[Sedefcho]

Hello all,

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

2. Or ... Are the differences which mf mentions correct ?

3. If so - my program outputs same output ( as Claudio's )
but gets WA currently.

And one question ( in principle ) - do we have to define new nodes
according to the queries given. I mean the following : if in the edges
list which comes first in the input
v[1],v[2]) (v[3],v[4]) ... (v[2*N-1], v[2*N])
the node ( the vertex ) X is not mentioned ( X != v[k] for each k )
but if this node ( the node X ) is mentioned in a query ( X, some_ttl )
does that mean we have to define a new node ( vertex ) X.

If that is what they want then I am doing it right - I am firstly
reading all the queries in order to add new vertices ( which have
not yet been defined ).

Then on a second run I go through the queries, I calculate the
answers for these queries and I print them.

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.