610 - Street Directions

All about problems in Volume 6. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

610 - Street Directions

Post by CDiMa »

I'm trying to solve prob 610 but I'm getting RTE consistently ;)

The problem statement says that intersections are numbered from 1 to n and maximum number of intersections is 1000. It says also that at most 4 streets meet at each intersection.
So I allocate space for 1000 intersections and 4000 streets...

Is there something that I'm overlooking?

Thanks in advance for any help!

Claudio

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

Re: 610 street directions. RTE?

Post by CDiMa »

CDiMa wrote:I'm trying to solve prob 610 but I'm getting RTE consistently ;)

The problem statement says that intersections are numbered from 1 to n and maximum number of intersections is 1000. It says also that at most 4 streets meet at each intersection.
So I allocate space for 1000 intersections and 4000 streets...
Since noone replies, here is an update on my experiments on this prob.
I doubled the number of intersections and increased to 100 the streets that may insist on the same intersection. This way I avoid RTE and get WA.

Since the problem statement is clear on the sizes of input data, I think I fail to get input correctly.

Here is a snippet of my code:
[c]#define MAXV 1000

int E[2*MAXV+1][101];
/* ... */
while(scanf("%d %d",&maxV,&maxE)==2){
if(!maxV && !maxE) return(0);
for(i=maxV;i>0;i--) {
E[0]=0;
};
for(i=maxE;i>0;i--){
scanf("%d %d",&v,&w);
E[v][++E[v][0]]=w;
E[w][++E[w][0]]=v;
};
/* ... */
};
[/c]
E[0] contains the number of streets that insist on on itersection i and E[1] to E[E[0]]
are the intersections adiacent to i.
I expected to need only E[MAXV+1][5] to store the input data...
So what am I missing?

Ciao!!!

Claudio

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

Re: 610 street directions. RTE?

Post by CDiMa »

CDiMa wrote:Since the problem statement is clear on the sizes of input data, I think I fail to get input correctly.
[...]
So what am I missing?
Multiple inputs :oops:

Now I get a very fast WA ;)

Ciao!!!

Claudio

wanderley2k
New poster
Posts: 28
Joined: Mon Mar 01, 2004 11:29 pm

610 - Street Directions - Why WRONG?

Post by wanderley2k »

Hi,

I tried to solve 610, but i got WA.

I implemented the code for discovery brigded in graph and for my test cases my program be correct.

My code:

[cpp]
/*
* encontrar todos as pontes do grafo em TEMPO LINEAR!! :)
*
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define D(x)
#define MAX_VERTICES 1010

bool adj[MAX_VERTICES][MAX_VERTICES];
bool res[MAX_VERTICES][MAX_VERTICES];
int low[MAX_VERTICES];
int pre[MAX_VERTICES];
int count;
int numVertices;

void bridgeR(int i, int w) {
int j;

pre = count++;
low = pre;

for (j = 0; j < numVertices; j++) {
if (!adj[j]) continue;

if (!res[j] && !res[j]) {
res[j] = true;
}

if (pre[j] == -1) {

bridgeR(j, i);
if (low > low[j]) {
low = low[j];
}
if (low[j] == pre[j]) {
//printf("%d %d\n", j, i);
res[j] = true;
res[j][i] = true;
}
}
else if (j != w) {
if (low[i] > pre[j]) {
//printf(".\n");
low[i] = pre[j];
}
}
}
}


void imprimir(bool matriz[MAX_VERTICES][MAX_VERTICES]) {
int i, j;
for (i = 1; i < numVertices; i++) {
for (j = 1; j < numVertices; j++) {
printf("%d ", matriz[i][j]);
}
printf("\n");
}
}

int main() {
int i, j, k;
int n, m;
int inst = 1;
int cases;

scanf("%d", &cases);
for (; cases > 0; cases--) { // multiple input
//while (scanf("%d %d", &n, &m) == 2) {
scanf("%d %d", &n, &m);
if (n == 0 && m == 0) {
break;
}

if (inst > 1) {
printf("\n");
}
printf("%d\n\n", inst++);

numVertices = ++n;

for (i = 0; i < numVertices; i++) {
pre[i] = -1;
}

memset(adj, false, sizeof(adj));
memset(res, false, sizeof(res));

/* Lendo adjacencia */
for (i = 0; i < m; i++) {
scanf("%d %d", &j, &k);
adj[j][k] = true;
adj[k][j] = true;
}

count = 0;

for (i = 1; i < numVertices; i++) {
if (pre[i] == -1) {
bridgeR(i, i);
}
}

for (i = 1; i < numVertices; i++) {
for (j = 1; j < numVertices; j++) {
if (res[i][j]) {
printf("%d %d\n", i, j);
}
}
}

printf("#");
}
return 0;
}

[/cpp]

Have the input??

Thanks,

Wanderley

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

Re: 610 - Street Directions - Why WRONG?

Post by CDiMa »

wanderley2k wrote:Hi,

I tried to solve 610, but i got WA.

I implemented the code for discovery brigded in graph and for my test cases my program be correct.
Your code fails on multiple inputs.
When it finds the couple of zero indicating the end of the first case it exits without processing the remaining cases.

Ciao!!!

Claudio

wanderley2k
New poster
Posts: 28
Joined: Mon Mar 01, 2004 11:29 pm

Re: 610 - Street Directions - Why WRONG?

Post by wanderley2k »

CDiMa wrote:Your code fails on multiple inputs.
When it finds the couple of zero indicating the end of the first case it exits without processing the remaining cases.
Claudio
Ok, I read the problem again and find the error..

Thanks

I learned the lession: READ READ READ THE INPUT! :D


Wanderley

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Location: TORONTO, CANADA

Post by daveon »

Multiple input no longer applies.

chileno
New poster
Posts: 3
Joined: Mon Aug 27, 2007 2:05 am

610 test cases please !!!

Post by chileno »

Hi, I tried a lot of tests and I think the output is correct. Could you give me some test cases ??? Thanks !! :D

chileno
New poster
Posts: 3
Joined: Mon Aug 27, 2007 2:05 am

Some tests

Post by chileno »

Here are some tests that I tried.

Input:
3 3
1 2
1 3
2 3
7 10
1 2
1 3
2 4
3 4
4 5
4 6
5 7
6 7
2 5
3 6
7 9
1 2
1 3
1 4
2 4
3 4
4 5
5 6
5 7
7 6
3 2
1 2
2 3
2 1
1 2
4 5
1 2
1 3
1 4
2 3
3 4
5 5
1 2
2 3
3 4
4 5
5 1
4 3
1 4
2 3
3 4
0 0

Output:
1

1 2
2 3
3 1
#
2

1 2
2 4
3 1
3 6
4 3
5 2
5 4
6 4
6 7
7 5
#
3

1 2
2 4
3 1
4 1
4 3
4 5
5 4
5 6
6 7
7 5
#
4

1 2
2 1
2 3
3 2
#
5

1 2
2 1
#
6

1 2
2 3
3 1
3 4
4 1
#
7

1 2
2 3
3 4
4 5
5 1
#
8

1 4
2 3
3 2
3 4
4 1
4 3
#

chileno
New poster
Posts: 3
Joined: Mon Aug 27, 2007 2:05 am

Post by chileno »

I've got AC !!! :P

tryit1
Experienced poster
Posts: 119
Joined: Sun Aug 24, 2008 9:09 pm

Re: 610 - Street Directions

Post by tryit1 »


My algorithm is
I find all the bridges ,store the orientation bridge with (x,y) as orient[x][y]=orient[y][x]=1
For every other edge in DFS if x is parent of y , then orient[x][y]=1.
All the other unmarked edges in arr[j] (adjacency matrix) is orient[y][x]=1;

Any inputs for which this fails.


Code: Select all


#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAX 1010
int N, E;
int arr[MAX][MAX], orient[MAX][MAX];
int visit[MAX], low[MAX], num[MAX], tme;

/* tme is time 
 * orient is whether the edge runs from x -> y or y->x
 * For a bridge it is both
 *
 * */

/*Find the bridges in the graph */
void
dfs (int x, int par, int isroot)
{

  num[x] = ++tme;
  visit[x] = 1;
  low[x] = num[x];
  int y;
  for (y = 1; y <= N; y++)
    {
      if (y != par)
	{
	  if (arr[x][y])
	    {
	      if (!visit[y])
		{
		  /* y is successor of x in dfs , go from x->y */
		  orient[x][y] = 1;
		  dfs (y, x, false);
		  if (low[y] == num[y])	//&& low[i]>=num[i])
		    {
		      //            printf ("x,y=%d,%d\n", x, y);
		      orient[x][y] = 1;
		      orient[y][x] = 1;
		    }
		  low[x] = min (low[x], low[y]);
		}
	      else
		{
		  low[x] = min (low[x], num[y]);
		}
	    }
	}
    }

}


int
main ()
{
  int tc = 0;
  while (scanf (" %d %d", &N, &E) != EOF)
    {
      //if(f) printf("\n");
      if (!N && !E)
	break;
      ++tc;
      memset (arr, 0, sizeof (arr));
      memset (orient, 0, sizeof (orient));
      memset (visit, 0, sizeof (visit));
      memset (low, 0, sizeof (low));
      memset (num, 0, sizeof (num));
      tme = 0;
      int x, i, y, j;
      for (j = 0; j < E; j++)
	{
	  scanf (" %d %d", &x, &y);
	  arr[x][y] = 1;
	  arr[y][x] = 1;
	}

      for (i = 1; i <= N; i++)
	if (!visit[i])
	  {
	    dfs (i, i, true);
	  }

      printf ("%d\n\n", tc);


      for (i = 1; i <= N; i++)
	{
	  for (j = 1; j <= N; j++)
	    {
	      if (arr[i][j])
		{
		  if (!orient[i][j])
		    orient[j][i] = 1;
		}
	    }
	}

      for (i = 1; i <= N; i++)
	{
	  for (j = 1; j <= N; j++)
	    {
	      if (orient[i][j])
		{
		  printf ("%d %d\n", i, j);
		  if ((i != j) && orient[j][i])
		    {
		      printf ("%d %d\n", j, i);
		      orient[j][i] = 0;
		    }
		}
	    }
	}

      printf ("#\n");
    }

  return 0;
}



mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: 610 - Street Directions

Post by mf »

tryit1 wrote:All the other unmarked edges in arr[j] (adjacency matrix) is orient[y][x]=1;

tryit1 wrote:

Code: Select all

      for (i = 1; i <= N; i++)
	{
	  for (j = 1; j <= N; j++)
	    {
	      if (arr[i][j])
		{
		  if (!orient[i][j])
		    orient[j][i] = 1;
		}
	    }
	}
Well, your mistake is in this step. You don't need it (there's no way to fix it), instead you need to change your DFS code a little.

When you do a DFS search on an undirected graph, the edges of the graph can be classified as either tree edges and back edges (google for definitions). Some of the tree edges can be bridges (but a back edge can never be a bridge).

Your code orients the bridge edges two-way, non-bridge tree edges away from the root - so far this is all correct. But then a step in your algorithm mentioned above does something strange with the back edges - it orients each back edge to be from a higher-numbered vertex to a lower-numbered vertex. This is, of course, just completely arbitrary, and can't be always right (especially with larger graphs). Try to think of a better way to deal with back edges.

tryit1
Experienced poster
Posts: 119
Joined: Sun Aug 24, 2008 9:09 pm

Re: 610 - Street Directions

Post by tryit1 »

mf wrote:
tryit1 wrote:All the other unmarked edges in arr[j] (adjacency matrix) is orient[y][x]=1;

tryit1 wrote:

Code: Select all

      for (i = 1; i <= N; i++)
	{
	  for (j = 1; j <= N; j++)
	    {
	      if (arr[i][j])
		{
		  if (!orient[i][j])
		    orient[j][i] = 1;
		}
	    }
	}
Well, your mistake is in this step. You don't need it (there's no way to fix it), instead you need to change your DFS code a little.

When you do a DFS search on an undirected graph, the edges of the graph can be classified as either tree edges and back edges (google for definitions). Some of the tree edges can be bridges (but a back edge can never be a bridge).

Your code orients the bridge edges two-way, non-bridge tree edges away from the root - so far this is all correct. But then a step in your algorithm mentioned above does something strange with the back edges - it orients each back edge to be from a higher-numbered vertex to a lower-numbered vertex. This is, of course, just completely arbitrary, and can't be always right (especially with larger graphs). Try to think of a better way to deal with back edges.
With the change

Code: Select all

             else // x -> y is a back edge
               {

               if(num[y] < num[x]) orient[x][y]=1;

                 low[x] = min (low[x], num[y]);
               }
thanks mf, i got it accepted with in the backedge with the above step. I had this code accepted on around 4 other problems, so thought it would be correct.
and removing the other 2 loops altogether


My question is we mark all the forward edges and bridges . Now the left over edges are backedges ? Aren't they ?

Can't we have the direction of back edges based on the time when they were seen ?
I found a way to orient them ie

Code: Select all

      if (arr[i][j]) // all the forward edges and bridges are oriented
      {
        if (!orient[i][j] && !orient[j][i]) // this mean this edge is a backedge and it is not oriented yet , now check the times of i and j in the dfs and orient them
              if(num[i] < num[j]) orient[j][i]=1 else orient[i][j]=1;
      }
       }
got AC :) thanks again mf

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 610 - Street Directions

Post by brianfry713 »

Shadek, for input:

Code: Select all

53 73
2 1
2 11
3 1
4 2
5 3
6 5
7 1
8 3
9 8
10 2
11 7
12 5
13 1
13 15
14 4
15 10
15 30
16 5
17 8
18 3
19 4
20 4
21 20
21 52
22 18
22 28
23 14
23 52
24 23
25 18
25 30
26 11
26 52
27 7
28 8
29 23
29 28
30 14
31 12
31 27
32 20
32 46
33 22
33 50
34 33
35 25
35 33
36 21
36 38
37 18
38 21
38 34
39 28
39 48
40 22
41 16
41 25
42 20
42 30
43 24
43 50
44 26
45 26
46 9
46 13
47 13
48 14
49 47
50 47
51 50
52 32
53 11
53 39
0 0
My AC output is:

Code: Select all

1

7 1
3 1
4 2
21 20
38 21
18 3
13 1
13 46
47 49
49 47
50 33
24 23
43 24
50 43
50 51
51 50
47 50
13 47
15 13
10 2
15 10
30 15
30 14
42 20
30 42
25 30
35 33
25 35
16 5
41 16
25 41
18 25
18 37
37 18
22 18
28 8
29 23
28 29
48 14
39 48
53 11
39 53
28 39
22 28
22 40
40 22
33 22
34 33
38 34
36 38
21 36
52 21
26 11
26 44
44 26
26 45
45 26
52 26
52 32
23 52
14 23
4 14
4 19
19 4
20 4
32 20
46 32
9 46
8 9
8 17
17 8
3 8
5 3
5 6
6 5
12 5
31 12
27 31
7 27
11 7
2 11
1 2
#
Your output is:

Code: Select all

1

47 49
49 47
50 51
51 50
18 37
37 18
22 40
40 22
26 44
44 26
26 45
45 26
4 19
19 4
8 17
17 8
5 6
6 5
1 2
1 3
1 7
1 13
2 11
2 4
2 10
3 5
3 8
3 18
4 14
4 20
5 12
5 16
7 11
7 27
8 9
8 28
9 46
10 15
11 26
11 53
12 31
13 15
13 46
13 47
14 23
14 30
14 48
15 30
16 41
18 22
18 25
20 21
20 32
20 42
21 52
21 36
21 38
22 28
22 33
23 52
23 24
23 29
24 43
25 30
25 35
25 41
26 52
27 31
28 29
28 39
30 42
32 46
32 52
33 50
33 34
33 35
34 38
36 38
39 48
39 53
43 50
47 50
#
In your output there is no path from 2 to 1.
Check input and AC output for thousands of problems on uDebug!

Shadek
New poster
Posts: 2
Joined: Thu Sep 05, 2013 2:23 pm

Re: 610 - Street Directions

Post by Shadek »

hi Brianfry,

After sorting your output according to edge (a,b)
if( a<b) insert (a,b)
else insert(b,a)
then sorting the edges according to a, if a is same for some edges,then sort according to smaller b

Your sorted output:

Code: Select all

1 2
1 3
1 7
1 13
2 4
2 10
2 11
3 5
3 8
3 18
4 14
4 19
4 19
4 20
5 6
5 6
5 12
5 16
7 11
7 27
8 9
8 17
8 17
8 28
9 46
10 15
11 26
11 53
12 31
13 15
13 46
13 47
14 23
14 30
14 48
15 30
16 41
18 22
18 25
18 37
18 37
20 21
20 32
20 42
21 36
21 38
21 52
22 28
22 33
22 40
22 40
23 24
23 29
23 52
24 43
25 30
25 35
25 41
26 44
26 44
26 45
26 45
26 52
27 31
28 29
28 39
30 42
32 46
32 52
33 34
33 35
33 50
34 38
36 38
39 48
39 53
43 50
47 49
47 49
47 50
50 51
50 51
My sorted output according to above criterion:

Code: Select all

1 2
1 3
1 7
1 13
2 4
2 10
2 11
3 5
3 8
3 18
4 14
4 19
4 19
4 20
5 6
5 6
5 12
5 16
7 11
7 27
8 9
8 17
8 17
8 28
9 46
10 15
11 26
11 53
12 31
13 15
13 46
13 47
14 23
14 30
14 48
15 30
16 41
18 22
18 25
18 37
18 37
20 21
20 32
20 42
21 36
21 38
21 52
22 28
22 33
22 40
22 40
23 24
23 29
23 52
24 43
25 30
25 35
25 41
26 44
26 44
26 45
26 45
26 52
27 31
28 29
28 39
30 42
32 46
32 52
33 34
33 35
33 50
34 38
36 38
39 48
39 53
43 50
47 49
47 49
47 50
50 51
50 51
I found no difference. What's wrong?

Post Reply

Return to “Volume 6 (600-699)”