10596 - Morning Walk

[sohel]

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]

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

[Farid Ahmadov]

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.

[Farid Ahmadov]

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.

[Farid Ahmadov]

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).
I made a change:
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.
Thank you for your helps.

[Dreamer#1]

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.

[Tahseen Mohammad]

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]

Yeah, all "possible" cases in the judge data have ALL intersections visited, though I don't know why......

[cypressx]

#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]

The graph given as input is undirected.

[QulinXao]

U must remember The Graf must be connected, Not Forrest,
from any point must be path to any other

[TheKiler]

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]

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]

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]

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

Code: Select all

CUT AFTER AC