10596  Morning Walk
Moderator: Board moderators

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
Problem H Morning Walk (IIUC Online Programming Contest)
I think that either the solution or the input for this problem was wrong, because there were road intersections without connected roads in the input, and in each such case the solution printed "Not Possible", but I think if there are road intersections without connected roads, then they can be ignored, and it may still be possible to visit all the roads (Note that this was all the problem asked for, to visit all the roads; it doesn't say: find an euler tour, if it had said so then also all nodes have to be visited).
In my opinion the input shouldn't contain such cases where a road intersection has no connected road (why should it be called road intersection then )
In my opinion the input shouldn't contain such cases where a road intersection has no connected road (why should it be called road intersection then )

 Learning poster
 Posts: 54
 Joined: Sun Oct 28, 2001 2:00 am
 Location: Bangladesh
I think you are right. We were only asked to visit all roads. There is
no mention that all intersections must be visited.
Also it seems the input data is shallow even for the solution that was
taken correct. A check of node of degree zero seems to suffice the
check of disconnected graph.
And about road intersections without roads, I think the roads were
washed out in rain.
no mention that all intersections must be visited.
Also it seems the input data is shallow even for the solution that was
taken correct. A check of node of degree zero seems to suffice the
check of disconnected graph.
And about road intersections without roads, I think the roads were
washed out in rain.
Yeah the problem description is really uncleared...
They should at least make it clear that they want a "circuit", not just a path
They should at least make it clear that they want a "circuit", not just a path
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org

 Learning poster
 Posts: 54
 Joined: Sun Oct 28, 2001 2:00 am
 Location: Bangladesh
Roads normally means bidirectional.
I guess there are OneWay roads too.
These two problems mentioned are really considerable,
is it bidirectional
is it path/circuit.
There is no direct mention for any of these.
I guess I was lucky thinking this is the case.
I wan't to set problems for contest. But this is what worries me.
If I make mistake, it won't take time for me to get washed in the
Board.
I guess there are OneWay roads too.
These two problems mentioned are really considerable,
is it bidirectional
is it path/circuit.
There is no direct mention for any of these.
I guess I was lucky thinking this is the case.
I wan't to set problems for contest. But this is what worries me.
If I make mistake, it won't take time for me to get washed in the
Board.

 Learning poster
 Posts: 54
 Joined: Sun Oct 28, 2001 2:00 am
 Location: Bangladesh
Thats right. I believe problem specifications should be as
clear as possible (though I'm not sure if I can make one
such description).
I am normally not good with guessing what the statement
means if I not sure. But as I said I got lucky this time.
I do agree that my assumptions of bidirectional has nothing
to do with the statement. And about the circuit, the 2nd sample
input I think confirms it.
clear as possible (though I'm not sure if I can make one
such description).
I am normally not good with guessing what the statement
means if I not sure. But as I said I got lucky this time.
I do agree that my assumptions of bidirectional has nothing
to do with the statement. And about the circuit, the 2nd sample
input I think confirms it.

 Experienced poster
 Posts: 192
 Joined: Sat Nov 30, 2002 5:14 am
10596  Morning Walk
Hi, all.
I get many WA in this problem.
My algo is: (euler cycle)
1. Check if the graph is connected.
2. for all vertex indegree must be the same as outdegree.
3. if number of road = 0, then print "Not conneted".
Am I wrong?
Thanks, for help.
Best Regards,
RS
I get many WA in this problem.
My algo is: (euler cycle)
1. Check if the graph is connected.
2. for all vertex indegree must be the same as outdegree.
3. if number of road = 0, then print "Not conneted".
Am I wrong?
Thanks, for help.
Best Regards,
RS
Confusing
I also treated the graph as bidirectional and checked to see if all the vertices has even degrees. And the degree of every vertex has got to be more than zero for a possible path.
There could be cases where all the vertices has even degree but the graph is disconnected. My AC gives possible path for this cases, which seems to be wrong.
There could be cases where all the vertices has even degree but the graph is disconnected. My AC gives possible path for this cases, which seems to be wrong.
I think that there is some test case,
a road will appear more than once in the input.
If you are unlucky, you may get overflow or other mistake and then WA.
a road will appear more than once in the input.
If you are unlucky, you may get overflow or other mistake and then WA.
My signature:
 Please make discussion about the algorithm BRFORE posting source code.
We can learn much more in discussion than reading source code.  I HATE testing account.
 Don't send me source code for debug.

 Experienced poster
 Posts: 131
 Joined: Thu Apr 17, 2003 8:39 am
 Location: Baku, Azerbaijan
10596 WA
I'm getting crazy of this WA.
What is wrong? Isn't it Euler cycle?
What does mean:
Then there will be R lines each containing two numbers c1 and c2 indicating the intersections connecting a road.
Is it an oriented graph or not?
Please give any tricky inputs if there are any?
Thanks in advance.
What is wrong? Isn't it Euler cycle?
What does mean:
Then there will be R lines each containing two numbers c1 and c2 indicating the intersections connecting a road.
Is it an oriented graph or not?
Please give any tricky inputs if there are any?
Thanks in advance.
_____________
NO sigNature
NO sigNature
disputed question
Hi Farid,
This question is a little controversial. My wrong code got AC but unfortunately the right one got WA.
What is your output for the following case:
3 2
0 1
1 0
This question is a little controversial. My wrong code got AC but unfortunately the right one got WA.
What is your output for the following case:
3 2
0 1
1 0

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