Project Euler Forum

Problem 232 (View Problem)

I have a question about the format of the answer to the problem.

Give your answer rounded to eight decimal places in the form 0.abcdefgh .

is what it reads as of the time of this post. Is that telling me to enter the value of the percentage * 100000000 rounded down towards zero to a whole integer, or is it telling me to enter 0.whatever.

Example, Let's say it was 50% or 0.50000000: Would I then enter 0.50000000 or 50000000 to get the correct answer?

Thus far I have been entering it in the later style and still suspect my approach is incorrect. Given the somewhat low number of those who've solved it thus far it also looks like it is justifiably difficult.

Additionally is this the right place to ask for suggested additional reading for the kinds of theory that would be useful in solving this problem?

You would enter 0.50000000 in that case.

mjevans wrote:Additionally is this the right place to ask for suggested additional reading for the kinds of theory that would be useful in solving this problem?

In this case, there's no problem because any introduction to probability theory would be useful in solving the problem and nothing more specialised is necessary or likely to exist (possibly a book on game theory might discuss related topics, but once you know enough probability theory to read on game theory, this problem should be easy anyway).

You also need a technique that is useful in a LOT of problems (and I'm not talking about sieving )

stijn263 wrote:You also need a technique that is useful in a LOT of problems (and I'm not talking about sieving )

Well then, clearly you must be referring to solving a Diophantine equation...

(I haven't actually attempted the problem yet, I'm just amusing myself by the thought)

quilan wrote: Well then, clearly you must be referring to solving a Diophantine equation...

LMAO

I believe there is a minor inconsistency in the wording for this problem. First it says

On Player 2's turn, she chooses a positive integer T and tosses the coin T times

meaning tossing a coin T times. It then says

On each turn Player 2 selects the number, T, of coins that maximises the probability of her winning.

meaning tossing T coins once.
The result from tossing a single coin T times or tossing T coins each once is mathematically the same, just the inconsistent wording could be confusing.

Thanks for having such an awesome site btw

Good spot. Fixed now.

quilan wrote:Well then, clearly you must be referring to solving a Diophantine equation...

I think this is the ranking of techniques you need the most when solving PE problems:
1) Sieving
2) Dynamic Programming
3) Solving Diophantine equations
4) Generating (special) pythagorean triplets

DP/memoisation is tops in my book. You're dead without it in so many cases.

Let me ask for some clarification. Say, it's n-th round, and both
payers got score 99. If the first player gets 1, he wins, second player
is not allowed to play anymore, i.e. draw is not possible in this game?

Yes.

Just wondering, I'm not sure if this is a valid question to ask:

The problem says "On each turn Player 2 selects the number, T, of coin tosses that maximises the probability of her winning."
Does this mean winning on that turn or just plain winning overall (i.e. after several more flips)

Thanks!

Winning overall.

stijn263 wrote: I think this is the ranking of techniques you need the most when solving PE problems:
1) Sieving
2) Dynamic Programming
3) Solving Diophantine equations
4) Generating (special) pythagorean triplets

Thank you, now I know the names of the topics to look up... I'm guessing it's probably 3, since I already saw sieving on the prime relation problems and I think I'm already doing dynamic programming, though there's an additional degree of complexity I might need to explore.

(I fixed an error relating to a confusing example that was on wikipedia which skewed my numbers a bit. However none of the numbers I generate using an easy method is the valid answer, though they are roughly matching my expectations.)

mjevans wrote:Thank you, now I know the names of the topics to look up... I'm guessing it's probably 3,

Not for this one.

mjevans wrote:(..) though they are roughly matching my expectations

Perhaps your expectation is wrong ?

In exchange for hints on this problem which made me lose my will to live I am willing to give you a wonderful Yaris 1300 (2007) almost as good as new, ABS, cd-player, airbags and a small picture of Euler within the rear mirror frame.
Call me on +39-112-3581321

...

Oh, my! Your phone number contains the answer!

(just kidding)

Despite the fact that incorrect answers are user error almost 100% of the time, I still can't help but feel like something is wrong with the answer for this problem. I have a method that, to me, seems like it is provably correct yet it is giving me the wrong answer.

Very frustrating. Would it be acceptable for me to post a small number n, like maybe 10, and ask someone to verify if my output is correct, close, or way off the mark if the point limit is n instead of 100?

Edit: Well I finally solved it. Maybe it was easy for some people, but it's for sure the most frustrating one I've encountered to date. Sometimes you're just going about it all wrong... Even worse that the answer I kept thinking was correct was less than .2% away from the correct answer