10596 - Morning Walk

Adrian Kuegel · 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 · 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.

Larry · 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 · 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

Tahseen Mohammad · 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 · 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 · 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 · 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. · 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"

)

sohel · 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.

shamim · 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.

.. · 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.

Farid Ahmadov · 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.

sohel · 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 · Post by **Farid Ahmadov** » Mon Dec 29, 2003 2:18 pm

My output for this case is "Possible".

OJ Board

10596 - Morning Walk

Problem H Morning Walk (IIUC Online Programming Contest)

10596 - Morning Walk

Confusing

10596 WA

disputed question