11872 - Where to Run

[Angeh]

What does the Problem Expect !!!
i cant understand the Problem ...
could somebody explain it ?
thanks ...

[Leonid]

What does the Problem Expect !!!

That is a very good question. I've spent like half of an hour re-reading the problem and more time investigating input and output data.

The plan is, from your current junction, you first find the number of junctions which are safe (no police are there) and if you go to one of them; you are still able to visit all the safe junctions (in any order) maintaining the above restrictions.

The most confusing part of this problem to me was this particular sentense. It attempts to say that you must be able to visit all yet unvisited junctions from the safe junction, otherwise it's not safe. Consider graph (1,2), (1,3), (2,3). Being in initial junction 1 it is not possible to move to junction 3, because it is not safe. Junction 3 is not safe because it is not possible to visit all unvisited junctions, in this case - 2 junction. Junction 2 is safe however. Hope it should be clear.

The probability of choosing to stay in the current junction or to go to each of the EJ is equal.

Here there are two ways to interpret the sentence. Either the probability to stay is 50% always (but why is it not written as 50% then?), or the probability to stay is 1/(n + 1) where n is number of adjacent non-visited junctions. According to sample input/output the second interpretation is right.

Usually these kinds of problems should be approached with a common sense complimented by test case analysis and enumeration of possible interpretations, even guessing, and checking assumptions against sample data. Setting up your own problems can help you with interpretation as the skills gained help you understand the way problem-setters think and where they can make mistakes in problem descriptions.

[Angeh]

Thanks Leonid , now problem is better but i still don't understand it completely

The probability of choosing to stay in the current junction or to go to each of the EJ is equal.

it means that when reaching a junction we can either keep running or stay there for 5 minuts and then Run ... !!!!
int the First & Third Test Case ...we have only one path ... and the out put means that we always stop at each junction for 5 minutes ..
0 ..(3m).. 1(5m) ...(3m)...2(5m) =16 ...
if so then whats the Probablity 1/(n+1)...

Thanks ...

[Leonid]

We do have one path in the first case. But it is possible to stay more than once in the same junction.

[Angeh]

is there other possibilities other than :
0 ..(3m).. 1(5m) ...(3m)...2(5m)
and then how is the Result 16 !!

But it is possible to stay more than once in the same junction.

what do you mean by this ??

[Leonid]

what do you mean by this ??

Consider a simple graph with 2 nodes: (0 => 1).
The probability to stay in 0 for 5 minutes is 50%,
The probability to stay in 0 for 10 minutes is 25%,
The probability to stay in 0 for 15 minutes is 12.5%,
....

[Angeh]

Leonid , would you please send me your code ?
i dont really understand what the problem is

angeh.a2@gmail.com

(if you send your solution for 11828 - Palindrome Again i'll be Really Grateful , i'm still stock on that problem ( )

Thanks ...