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

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Problem H Morning Walk (IIUC Online Programming Contest)

Post by Adrian Kuegel » Sun Dec 21, 2003 1:04 pm

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 :-? )

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

Post by Tahseen Mohammad » Sun Dec 21, 2003 2:00 pm

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

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Sun Dec 21, 2003 3:33 pm

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

Post by Observer » Sun Dec 21, 2003 3:38 pm

Yeah the problem description is really uncleared...

They should at least make it clear that they want a "circuit", not just a path 8)
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

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

Post by Tahseen Mohammad » Sun Dec 21, 2003 3:51 pm

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:

Post by Larry » Mon Dec 22, 2003 1:36 am

If you solved enough problems, you'll know that roads are NOT always bidirectional.. =P it should be mentined anyhow..

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

Post by Tahseen Mohammad » Mon Dec 22, 2003 11:43 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

Post by Red Scorpion » Sat Dec 27, 2003 2:24 pm

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:

Post by Whinii F. » Sat Dec 27, 2003 3:00 pm

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" :wink:)
JongMan @ Yonsei

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

Confusing

Post by sohel » Sat Dec 27, 2003 3:35 pm

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.

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Sat Dec 27, 2003 4:27 pm

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

Post by .. » Sat Dec 27, 2003 9:25 pm

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.

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

10596 WA

Post by Farid Ahmadov » Mon Dec 29, 2003 12:58 pm

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

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

disputed question

Post by sohel » Mon Dec 29, 2003 1:53 pm

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

:-?

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 2:18 pm

My output for this case is "Possible".
_____________
NO sigNature

Post Reply

Return to “Volume 105 (10500-10599)”