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

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 )

Learning poster
Posts: 54
Joined: Sun Oct 28, 2001 2:00 am
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.

washed out in rain.

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
My grief was that it also made no mention whether it's directed or undirected, making me submitting a few times.. =/

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
Yeah the problem description is really uncleared...

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

Learning poster
Posts: 54
Joined: Sun Oct 28, 2001 2:00 am
Roads normally means bidirectional.
I guess there are One-Way 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.

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
If you solved enough problems, you'll know that roads are NOT always bidirectional.. =P it should be mentined anyhow..

Learning poster
Posts: 54
Joined: Sun Oct 28, 2001 2:00 am
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 bi-directional has nothing
to do with the statement. And about the circuit, the 2nd sample
input I think confirms it.

Red Scorpion
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

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:
I treated the graph as bidirectional, and checked whether every edge has an even degree, and whether it is connected or not.

And I didn't check for 0 roads.

(And, you should print "Not Possible" instead of "Not connected" )
JongMan @ Yonsei

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

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.

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA
There is a mistake with the judge's data.
It also considers the answer to be not possible if it is not possible to reach a particular intersection, eventhough you may visit all roads.

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong
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.
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?

_____________
NO sigNature

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

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