OJ Board

I'm completely in the dark on this problem.

Assuming 'taking random turns' also includes U-turns, I get the following probabilities for the first sample input: 3/10, 2/10, 2/10 and 3/10, that is: probability that Mr. H. ends on intersections 0, 1, 2 and 3 resp. Now Mrs. H. will have to drive resp. 0, 18, 8 and 4 units when she visits them in the order 0 3 2 1, so the expected distance is 0*3/10 + 18*2/10 + 8*2/10 + 4*3/10 = 64/10 units. At a speed of 12 this gives 64/120 = 8/15 units of time, a bit different than the correct answer 5/6.

Am I anywhere near the correct reasoning? Please give me a hint.

PS. Is the problemsetter of this problem the same Frank Chu that ended 4th in the contest?

I made the same mistake... and now let's read the problem again...

... smallest expected amount of time that Mrs. Hamilton needs in order to find her husband and bring him home ...

OMG, been staring at it for hours...
Thanks a lot, Cho!

I can't make sense out of the output given for the sample input.
How come you can visit vertex 1 inmediately after vertex 2, if there is no edge connecting both?

Via vertex 3.

Then why isn't vertex 3 part of the output?

It's a bit vague, but

giving the order of the intersections that Mrs. Hamilton should visit

should be interpreted such that she doesn't actualy visit an intersection to look for her husband if she's been at that intersection before, she only passes thru. Anyway, just list every intersection only once when it's first encountered.

Yes, the output statement is a little vague. What little joey said is correct. Basically the problem asks for a list of intersections that Mrs. H visits, without repetition, that minimize the expected time (of finiding Mr.H and bringing him home). Thank you for the correction.

And yes I am the guy who finished 4th on the contest. It's a little shameless on my part to make a submission on my own problem, but I couldn't resist :)

Frank Chu

It's a little shameless on my part to make a submission on my own problem, but I couldn't resist

"The ability to resist temptation is one of the best measures of honesty."
Muad'Dib

I know the temptation...
Great problem BTW.

From the sample input/output, I inferred that the author assumed the probability of Mr. Smith's waiting at certain intersection was totally (thus only) decided by the degree of the intersection, given that Mr. Smith had walked long enough before he stopped. However, I've got a different opinion that the probability just mentioned will be affected also by the length of the streets. To be more specific, the probability will be linear with the total length of all the streets connected at the intersection. And when all the streets are of the same length, it will simplify to the assumption about degrees.

As we have no written rules that problemsetters cannot participate so it is ok I guess. When someone participates in a contest he wants to do well and that is impossible without solving his own ones. Although it seems illogical to submit ones own problem Frank Chu did not submit it in first one minute of the contest but submitted it in a reasonable time.

I just don't want people to stay away from problemsetting just because they want to participate in contests. So such harsh rules need not be practiced as long as we don't have any prize money for an online contest.

Dear Mr. Manzoor!
With your kind permission I would dare to point out that in the vast majority of cases the
so-called human values (as courage, honesty, generosity etc.) are not based on written
rules. And arguments like "...Frank Chu did not submit it in first one minute of the contest
but submitted it in a reasonable time" seem to me quite difficult to understand.
I am not ashamed to state that I am still having serious problems to guess
what "smallest expected amount of time" does mean. And I am deeply convinced that I am
not the only person to face such a problem.
It would be very nice if somebody could explain to us what is the exact meaning of
"expected amount of time" since we are asked to perform a kind of a mathematical
calculation, which is hard to do without proper specification of the nature of the
involved numerical values.
Thank you for you involvement in this discussion.

Dear Mr. Ivan,
Please note I am not saying that you are wrong. It is ok that you feel bad and state your opinion here.

At the same time suppose you start setting problems when you r still a contestant so you must attend the contestx as well. After some time you find that people are going above you solving your own problem,then it is natural to have the temptation to submit your own problem assuming that you would have solved it any how in that specified time.

My point of view is:
There are very few people who set problems after their contestant life so we need the contestants to set good problems as well to ensure occurance of contest. At the same time we maintain the rule, not to allow an ICPC contestant in our problem setting panel (EPP). There was one exception but it will not happen again. So my request is "Don't stay away from problemsetting just because then you can't compete. Set problems and compete if you like, we won't have many problems from one person any how" When one is not a conteatant it is easy to avoid the temptation but otherwise it is not so easy and quite natural.

But ofcourse unless necessary (No need to practice) problems setters will naturally stay away from participating in contests .

What I find funny about all this is the fact that he made a wrong submission to his own problem!