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

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

Post by sohel » Mon Dec 29, 2003 5:05 pm

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.

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

hi

Post by abishek » Mon Dec 29, 2003 7:27 pm

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
Experienced poster
Posts: 131
Joined: Thu Apr 17, 2003 8:39 am
Location: Baku, Azerbaijan

Post by Farid Ahmadov » Mon Dec 29, 2003 7:36 pm

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

Farid Ahmadov
Experienced poster
Posts: 131
Joined: Thu Apr 17, 2003 8:39 am
Location: Baku, Azerbaijan

Post by Farid Ahmadov » Mon Dec 29, 2003 7:40 pm

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

Farid Ahmadov
Experienced poster
Posts: 131
Joined: Thu Apr 17, 2003 8:39 am
Location: Baku, Azerbaijan

Post by Farid Ahmadov » Mon Dec 29, 2003 8:08 pm

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.
_____________
NO sigNature

User avatar
Dreamer#1
Learning poster
Posts: 77
Joined: Tue Oct 07, 2003 10:07 pm

Post by Dreamer#1 » Wed Dec 31, 2003 10:03 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. :lol:

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.

Tahseen Mohammad
Learning poster
Posts: 54
Joined: Sun Oct 28, 2001 2:00 am
Location: Bangladesh

Post by Tahseen Mohammad » Thu Jan 01, 2004 6:32 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

Post by Observer » Thu Jan 01, 2004 7:00 am

Yeah, all "possible" cases in the judge data have ALL intersections visited, though I don't know why...... :wink:
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 ?

Post by cypressx » Sun Aug 08, 2004 5:21 pm

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

Post by sidky » Mon Sep 20, 2004 8:35 am

The graph given as input is undirected.

QulinXao
New poster
Posts: 29
Joined: Mon Apr 05, 2004 11:12 am

Post by QulinXao » Sat Jan 15, 2005 6:59 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)

Post by TheKiler » Fri Jul 29, 2005 11:57 pm

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

Post by misof » Sat Jul 30, 2005 11:57 am

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 :D

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

Post by TheKiler » Sat Jul 30, 2005 2:23 pm

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 :wink: ), I was kinda surprised by this. I thought I made some error when writing and (unconsciously? :P ) 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 8)

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

Post by helloneo » Fri Jan 20, 2006 5:39 pm

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.

Post Reply

Return to “Volume 105 (10500-10599)”