Problem 80 - Duel Chances
Back to Problem Solutions forum
Hi admin :) I didn't know how to solve problem #80 so I set up a randomizer, ran it a million times for each line, to calculate the average for Alan winning the duel. My solution is very close to the expected answer, i.e. out of 20 or so answers mine differs only in one or two of them, by one or two percent.
For instance for this input data: 22 57 32 56 28 70 75 10 50 83 88 58 78 64 73 54 20 27 39 15 39 18 88 88 66 24 42 24 68 53 21 84 20 44 49 39 23 33 39 64 25 37 31 13 10
expected answer was: 81 82 76 18 85 64 71 85 49 31 20 92 43 32 84 96 62 74 56 88 65 60
my answer was: 80 82 76 19 85 64 71 85 49 32 20 92 43 32 84 96 62 73 56 87 65 59
Isn't it close enough for enlightenment points? ;)
Hello again!
I think your approach (let's call it "experiment modelling") is ok, but if precision is not enough you may need to increase amount of attempts (say, 10 mln times instead of 1 mln) or ensure that probabilities are as just as possible (straightforward use of randomizer may lead to some skews).
Though I believe (again not remember precisely and don't want to cheat looking at checker code, haha) that precise solution could be calculated with some simple math. I suspect one needs to write down formula for probabilities - it will be recurrent, so unknown values should be grouped to one side to get usable expression.
The key observation is that if on the first round neither of two killed an opponent, they came to situation with the same probabilities as in beginning.