понедельник, 29 апреля 2013 г., 15:25:55 UTC-5 пользователь Nate Bauernfeind написал: > Can you explain why multiplying the raw numbers (or summing their logs) is > more likely to give you the best answer than multiplying the probabilities? > > On Sunday, April 28, 2013 11:13:46 PM UTC-5, meir wrote: > > Summing the log of the count is equivalent to multiplying them, I was using > > Long and not BigInt, It is conceivable there was a simple numeric overflow. > > > > On Monday, April 29, 2013 4:37:09 AM UTC+3, Nate Bauernfeind wrote: > > > A correct answer I read through was very similar and I tried rewriting it > > > in a way that was more intuitive to me. > > > > > > I tried to build a probability of the choices by multiplying the > > > probability of the chance you saw k for each k and the probability it was > > > that combination of numbers (taking into account duplicate arrangements > > > basically n! / n2! / n3! / n4! ... etc > > > > > > That doesn't pass for some reason, but intuitively I would expect more > > > probable choices to have higher probability of happening. > > > > > > Then I tried simply summing them thinking maybe the value is too small to > > > compare. But still wrong answer. > > > > > > The solution I looked at summed the log of the count. It works but I > > > can't explain why. Because I would expect this just to be another way to > > > do the same thing we both tried.
In this problem you constantly need to multiply very small numbers. Multiplying numbers in the range of 1e-18 / 1e-10 / 1e-8 very quickly leads to HUGE loss of precision and eventually to "underflow". e-1023 is not that far away as you might think when you really start multiplying small numbers (for double) having passed that point you get 0. When you get zero in the middle of multiplication you get garbage. Logarithms are widely used to overcome this problem. For example log of 1e-300 is just -690. Almost impossible to get "underflow" in this situation. -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msg/google-code/-/xsplw3PWiH0J. For more options, visit https://groups.google.com/groups/opt_out.
