10596 - Morning Walk

[Emilio]

Here http://online-judge.uva.es/board/viewto ... 2A10596%2A you can find all you need.

[helloneo]

thanks.. i should've thought every edge is undirected..

[mohsincsedu]

what's the problem in my code?
I got WA...

Code: Select all

while(scanf("%d %d",&n,&m)==2)
	{
		for(i = 0;i<n;i++)
			for(j = 0;j<n;j++)
				G[i][j] = 0;
		for(i = 0;i<m;i++)
		{
			scanf("%d %d",&x,&y);
			G[x][y]++;
		}
		for(i = 0,flag = 1;i<n;i++)
		{
			if(flag)
			{	
				x = inDegree(i);
				y = outDegree(i);
				if((x+y)==0||(x+y)%2==1)
					flag = 0;
			}
		}
		if(flag)
			printf("Possible\n");
		else
			printf("Not Possible\n");
}

Thanks in advanced...

[sohel]

Have you checked whether the graph is connected?

[mohsincsedu]

Thanks to Sohel Vhai....


I got ACC...

[riisiingsun]

After getting a lot of WA finally i solved...
Some instructions to new solver:
1. consider graph as bidirectional
2. need not to visit those vertices's which have no edge. u can ignore those. Exception if r != 0 !!
3. must have to visit all edges (Eulerian cycle)

consider these test cases:
Input:
3 2
0 1
1 0

2 2
1 0
1 0

4 4
0 1
1 0
2 3
3 2

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

4 6
1 2
2 1
2 3
2 3
3 1
1 3

2 0

Output:
Possible
Possible
Not Possible
Possible
Possible
Not Possible

[Taman]

I could never imagine that such a foolish problem or judge data could be made by anyone if I didn't face this problem with a lot of rubbish judge data. We are here to solve problems not to think what the problemsetter thinks.

Some instructions to new solver:

change this line. . . as, "Some instructions if you want to get ac", coz the instructions you gave is not accurate at all. . . at least the problem statement doesn't support your instruction, hence the data does. . .

[suneast]

I think the only tricky to solve this problem is the case when r==0

there is no doubt that if there isn't any road exist,how can a Uleur tour being possible?

[albertvictordu]

#include<iostream>

using namespace std;

int vis[210][210]={0};
int num,N,R;

void dfs(int v)
{
for(int i=0;i<N;i++)
if((vis[v]/10)&&!(vis[v]%10))
{
vis[v]=vis[v]+1;
num++;
dfs(i);
}
}

int main()
{
int i=0,a,b;
int nod[210];
while(cin>>N>>R)
{
memset(nod,0,sizeof(nod));
memset(vis,0,sizeof(vis));
i=num=0;
while(i<R)
{
cin>>a>>b;
vis[a]=10;
vis[a]=10;
nod[a]++;
nod++;
i++;
}
dfs(a);
for(i=0;i<N;i++)
{
if(nod%2==1)
break;
}
if(i!=N||R==0||num!=R)
cout<<"Not Possible"<<endl;
else
cout<<"Possible"<<endl;
}
return 0;

}

Why it gives me runtime error????who can help me.

[Shafaet_du]

Rubbish judge data,rubbish description. I am telling you an easy way to get ac:

just check if all the vertexes have non-zero even degree,thats all.
My output differs with risingsuns:

Code: Select all

3 2
0 1
1 0

2 2
1 0
1 0

4 4
0 1
1 0
2 3
3 2

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

4 6
1 2
2 1
2 3
2 3
3 1
1 3

2 0

Code: Select all

Not Possible
Possible
Possible
Not Possible
Not Possible
Not Possible

[academus]

I think the problem description and sample input/output are rather misleading, and what on earth does an intersection without any roads connecting to it mean? Can this be called as an "intersection"?? Also, the sample input:

2 2
0 1
1 0

2 1
0 1

seems to tell us the graph is directed. But you guys find that it must be treated as undirected/bidirectional. Too confusing!

[Darko]

This one was re-judged recently and my "solution" was not accepted anymore.

I am assuming that someone "fixed" the I/O but I am not quite sure how it is fixed when the statement itself is still ambiguous.

In the description section, it is mentioned that roads are visited only once, even on the way back home. But in the output section, nothing stipulates that you have to come home (other than the second example being "Not Possible").
If we do have a "home" intersection that we have to come back to, it is never stated which one it is. From the second example, it can be either 0 or 1.

I thought that the question asked if all edges form an Eulerian cycle. Then I added that 0 should be on the cycle. Neither worked.
Should I also visit all intersections? Or guess something else? I had no idea until I tried what was suggested - print "Not Possible" for r=0.

If a graph contains no edges, of course it is possible to visit all roads in a single walk - because there are no roads. For the people that think it is impossible - show me the road which is not reachable from "home".

And again - "home" is not defined in the problem. But, through trials and errors, I discovered that "home" is one of the intersections with a non-zero degree.

I got it AC eventually, but this is an ugly problem.

So for the input (I added a couple of cases):

Code: Select all

3 2
0 1
1 0

2 2
1 0
1 0

4 4
0 1
1 0
2 3
3 2

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

4 6
1 2
2 1
2 3
2 3
3 1
1 3

2 0

3 2
1 2
1 2

2 2
0 0
1 1

My currently accepted "solution" outputs:

Code: Select all

Possible
Possible
Not Possible
Possible
Possible
Not Possible
Possible
Not Possible