10596 - Morning Walk

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

Moderator: Board moderators

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

Post by Emilio » Mon Jan 23, 2006 12:54 pm


helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Post by helloneo » Mon Jan 23, 2006 1:25 pm

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

Post by mohsincsedu » Fri Dec 21, 2007 1:31 pm

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...
Amra korbo joy akhdin............................

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » Fri Dec 21, 2007 3:20 pm

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

Post by mohsincsedu » Fri Dec 21, 2007 5:22 pm

Thanks to Sohel Vhai....


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

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

Re: 10596 - Morning Walk

Post by riisiingsun » Tue Oct 20, 2009 9:15 pm

After getting a lot of WA finally i solved... :D
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

Post by Taman » Sun Nov 22, 2009 1:20 am

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

Post by suneast » Wed Jul 14, 2010 4:40 pm

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

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

albertvictordu
New poster
Posts: 1
Joined: Sun Aug 15, 2010 4:40 am

Re: 10596 - Morning Walk

Post by albertvictordu » Sun Aug 15, 2010 11:27 am

#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
Location: University Of Dhaka,Bangladesh
Contact:

Re: 10596 - Morning Walk

Post by Shafaet_du » Fri Sep 10, 2010 12:16 pm

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
New poster
Posts: 3
Joined: Sat Jun 22, 2013 3:58 pm

Re: 10596 - Morning Walk

Post by academus » Fri Jul 05, 2013 10:02 am

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
Location: Calgary, Canada

Re: 10596 - Morning Walk

Post by Darko » Tue Jun 10, 2014 1:02 am

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

Post Reply

Return to “Volume 105 (10500-10599)”