## 10596 - Morning Walk

Moderator: Board moderators

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea
thanks.. i should've thought every edge is undirected..

mohsincsedu
Learning poster
Posts: 63
Joined: Tue Sep 20, 2005 12:31 am
Location: Dhaka
Contact:

### WA

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

Amra korbo joy akhdin............................

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York
Have you checked whether the graph is connected?

mohsincsedu
Learning poster
Posts: 63
Joined: Tue Sep 20, 2005 12:31 am
Location: Dhaka
Contact:

### ACC

Thanks to Sohel Vhai....

I got ACC...
Amra korbo joy akhdin............................

riisiingsun
New poster
Posts: 4
Joined: Fri May 18, 2007 12:03 pm

### Re: 10596 - Morning Walk

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
R!!\$!!NG\$UN

Taman
New poster
Posts: 32
Joined: Sun Oct 11, 2009 8:59 pm
Location: Southeast University

### Re: 10596 - Morning Walk

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.
riisiingsun wrote: 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
New poster
Posts: 49
Joined: Sun Jan 17, 2010 6:25 am
Location: FZU
Contact:

### Re: 10596 - Morning Walk

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
New poster
Posts: 1
Joined: Sun Aug 15, 2010 4:40 am

### Re: 10596 - Morning Walk

#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
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Contact:

### Re: 10596 - Morning Walk

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
``````

New poster
Posts: 3
Joined: Sat Jun 22, 2013 3:58 pm

### Re: 10596 - Morning Walk

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
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am

### Re: 10596 - Morning Walk

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
``````