## 10596 - Morning Walk

Moderator: Board moderators

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York
My AC program also gave 'not possible'. In this cases an Euler Cycle is possible without visiting road 2.

To solve this problem I have assumed a lot of false stuffs.
Such as :
1) I considered the graph to be undirected.
2) I applied the euler cycle algorithm and instead of counting the number of edges I counted the number of nodes i can visit.

In a nut-shell : I stored the degree of all the vertex and checked whether
every vertex has an even degree and no vertex has a degree of zero.

abishek
Experienced poster
Posts: 131
Joined: Mon Dec 15, 2003 5:41 am

### hi

my AC program checks if the degree of every vertex is even and that the graph is connected.
The only assumption is that the graph is undirected.
The rest all seem direct to me

Experienced poster
Posts: 131
Joined: Thu Apr 17, 2003 8:39 am
Location: Baku, Azerbaijan
Maybe I have some stupid mistake or I don't correctly get the input.
But I have tried nearly every variation of graph. But WA still.
_____________
NO sigNature

Experienced poster
Posts: 131
Joined: Thu Apr 17, 2003 8:39 am
Location: Baku, Azerbaijan
This is not correct and not fair. I've lost so much time on this problem at contest. There exist an Euler cycle. I visit every road and come back to the first city.
Thank you all.
_____________
NO sigNature

Experienced poster
Posts: 131
Joined: Thu Apr 17, 2003 8:39 am
Location: Baku, Azerbaijan
That's all. AC at last.
My last program was checking:
if there is any odd vertex or vertex 0 is not connected with any other vertex and this vertex is used to make a road then Not Possible.
This was WA (but correct I think).
if there is any odd vertex or vertex 0 is not connected with any other vertex then Not Possible.
This is AC (but not correct I think).

There is nothing said about that Kamal must walk through all intersections.
_____________
NO sigNature

Dreamer#1
Learning poster
Posts: 77
Joined: Tue Oct 07, 2003 10:07 pm
I tried so many times but kept getting WA until I read this page . Its really unfortunate but a few of problems from this contest made me feel as if we are here not to write programs but to try n make guesses on how the problemsetter actually thought about the problem. I don't think the problem descriptions were neat or perfect. Anyway, I know some of these guys are new to this so lets not make them too scared.

regards

Dreamer.
Not all of our dreams can be made to come true. But still we live with the hope to turn them into reality someday.

Learning poster
Posts: 54
Joined: Sun Oct 28, 2001 2:00 am
There are two guesses to make:

1) Graph is undirected
2) If a road intersection has no roads attach to it even then its not
possible.

If you check for a disconnected graph and give not possible then
you'have managed to get arround guess 2. But the problem is in
an Eulerian cycle you don't need to visit all intersections.

And about the check of degree 0, it seems in all disconnected graph
of the judge input there is always a node with degree 0. So people
like sohel & also me got away with it.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
Yeah, all "possible" cases in the judge data have ALL intersections visited, though I don't know why......
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

cypressx
New poster
Posts: 41
Joined: Sun Jul 04, 2004 12:16 pm

### 10596 .. why WA ?

#include <stdio.h>
#include <string.h>
int n,r;
int A[201][201];
char isEulerGraph() {
int i,j;
bool visit = false;
for(i=0;i<n;i++) {
visit = false;
int din = 0,dout = 0;
for(j=0;j<n;j++) {
if(A[j]){ din++; visit = true; }
if(A[j]){ dout++; visit = true; }
}
if(!visit) return 0;
if(din != dout) return 0;
}
return 1;
}
int main() {
while(scanf("%d",&n)==1) {
memset(A,0,sizeof A);
scanf("%d",&r);
int x,y;
for(int i=0;i<r;i++) {
scanf("%d%d",&x,&y);
A[x][y] = 1;
}
if(isEulerGraph()) printf("Possible\n");
else printf("Not Possible\n");
}
return 0;
}

I can`t understand why my code is wa ? I tried all the tests in the forum and it prints the right result .. please help me

sidky
New poster
Posts: 50
Joined: Wed Nov 06, 2002 1:37 pm
Location: Planet Earth, Universe
Contact:
The graph given as input is undirected.

QulinXao
New poster
Posts: 29
Joined: Mon Apr 05, 2004 11:12 am
U must remember The Graf must be connected, Not Forrest,
from any point must be path to any other

TheKiler
New poster
Posts: 6
Joined: Wed Jun 22, 2005 2:26 am
Location: Poland, Poznan

### Compil. error (odd interpret. of obviously correct code)

When I try to submit a code to solve problem 10596 (I just haven't tried the other) the memory usage is WAY too much. It should stay under the "Minimum" but it's about 300-400 kB. I wondered for some time what could be the problem, then I recalled reading about such a problem in Jon Bentley's "Programming Pearls" and submitted parts of the code, trying to find out which line(s) it is. To my surprise, the code that allocates that much memory is:

Code: Select all

``````#include <stdio.h>

int r,n, p[200], a,b, i, ileniep;

int main(void)
{
while (1) {
}
return 0;
}
``````
I have tried with for (;;) {}, too, with the same result. Also, code without the while loop allocates "Minimum", so as Bugs Bunny would say: "What's up, doc?"

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm
This may have something in common with the known problem of the UVa judge -- that it is unable to measure memory usage for programs that run too quickly.
Just for fun, try adding a counter inside the while-loop and break it after (say) 100 iterations. If I'm right, this should still give the "Minimum" memory usage.
By the way, the 300 kB is probably the correct result, this is approximately the space libc needs (if my memory doesn't fail me ).

In general, 300 kB isn't much, you have at least 32 MB available, so don't worry about that too much

TheKiler
New poster
Posts: 6
Joined: Wed Jun 22, 2005 2:26 am
Location: Poland, Poznan
Well, taking into consideration that I still haven't sent a single program that used more than "Minimum" with #include <stdio.h> - though I am not UVA's VESA (Very-Experienced-Solution-Author ), I was kinda surprised by this. I thought I made some error when writing and (unconsciously? ) used some malloc or other pointer-thing. Eventually, when I found out what it was I thought to point it out - maybe it's a yet unknown issue due to some new changes - that's what sometimes happens to me and my colleagues - new functions were working very well, although some old were crashing the program.

About the measurement of memory for programs that run too quickly - kind of funny, but hey, better to know than stay anaware. Now, thanks to you, I am the former

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

### 10596 Morning Walk.. how can i see if there exist euler cycl

i'm trying to find out if there exist euler cycle..
but i'm getting WA..
plz help.. ;

Code: Select all

``````CUT AFTER AC
``````
Last edited by helloneo on Mon Jan 23, 2006 1:23 pm, edited 1 time in total.