11025 - Mr. And Mrs. Hamilton

[sclo]

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

How do you find that out?
I suprised that it says my solution used only 64k memory, but i declared arrays like int A[1<<13][13][13]. That's way more than 64k. I think the memory usage that uva shows is incorrect.

[fpmc]

Sorry for the controversy. Like I said, it was a bit shameless on my part, and if that angers others, I'll just stop doing it next time.

As for the problem, by smallest "expected amount of time" I mean the smallest average time that it would take Mrs. H to find Mr. H and take him home. The smallest is taken over all possible plans for Mrs. H to try to find Mr. H (ie. to visit all intersections at least once); the average is average over the amount of time that Mrs. H drives, given probabilities that Mr. H will be at each intersection.

The only unspecified part about the problem is with what probabilities Mr. H will be at each intersection. If you know these probabilities, then the mathematical calculations should be do-able. little_joey's explanation in the first post gives an idea (although he misses the "take him home" part in that post).

During the contest I received some clarifications and answered them (through my friend Abednego). One common one is "can I assume that Mr. H is at each intersection with equal probabilities?" The answer given was "No response; Read problem statement." If you are not satisfied with this answer, then you can at least deduce from little_joey's first post that the answer is "No". His probabilities for the first sample test case is correct.

The probabilities are not given for a reason, and I tried to make the problem somewhat non-standard to skew away those who attempt to guess a formula. The two important statements from the problem are "takes random turns (with uniform probability)" and "assumes that Mr. Hamilton has walked a very long time."

As for the wrong submission, it was a compile error.

Frank Chu

[fpmc]

Hi,

Thanks hewei. You're right, if the streets are of different lengths the probabilities will be different. When I created the problem I forgot to say that all streets have the same lengths.

Assuming this, the probabilities only depend on degree (and I can prove this).

Thanks,
Frank Chu

[fpmc]

By the way, your changing the name from Mr. Hamilton to Mr. Smith is either a very good joke, or a very funny Freudian slip. I like it.

Frank

[sclo]

Hi,

Thanks hewei. You're right, if the streets are of different lengths the probabilities will be different. When I created the problem I forgot to say that all streets have the same lengths.

Assuming this, the probabilities only depend on degree (and I can prove this).

Thanks,
Frank Chu

Then again, if you say that the streets all have the same lengths, then what is the reason to give the lengths in the input? It would only make sense if the set of roads that Mrs. Smith drives on are different then the set of streets that Mr. Smith can walk on.

[Quantris]

I'd just like to chime in about submitting on your own problem:

I see absolutely no reason to be upset over this. It's not like it's a secret that this was Frank's problem, and the contest is not for a prize (as Mr. Manzoor pointed out). Rather, the contest was for practice, and all that really matters to any person is their individual performance. Therefore, submitting on your own problem shouldn't be regarded as "cheating" or "unsportsmanlike" -- it shouldn't affect the other contestants anyway (unless you care deeply about your exact ranking, which is a separate issue).

This is an especially valid point when the problemsetter codes the problem again from scratch instead of just submitting the solution he's already written -- in this case it is basically the same as having seen a problem in a prior contest and knowing the algorithm to solve it.

Honestly, I would make more noise about teams participating in contests as a single account

By the way, nice problem Frank. Personally I thought the description was very well written in order not to make the problem too direct.

[helloneo]

Hello..
Can anybody explains the strategy..?
I really have no idea how to get the sequence..

Thanks..