We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Project Euler #213: Flea Circus
Project Euler #213: Flea Circus
Sort by
recency
|
6 Discussions
|
Please Login in order to post a comment
This can be solved by calculating the probability of given square P(i, j) being occupied after m ring bells for given single flea starting at position (k, l). We can then compute the complement of the union of this events that is for all P(∑(i,j)') = ∏(1 - P(i.j)) - De Morgan Law Of Unions. The probability of square (i,j) being unocuppied afetr m ring bells is just equal to this value: P'(i,j) = ∏(1 - P(i.j)) when multiplication is calculated over flea starting from every square (k,l) in the grid. The expected value is the sum of all P'(i,j). To speed things up we can use symmetry and use just upper left quarter of the square as the starting positions of the fleas.
Can somebody clearify output format?
It says P X Q(-1) mod (10^9 + 7), which makes very little sense as sample output is just single number, e.g. if I try 1.0000 instead - it will be wrong. Plus as number of cells is restricted to 40 x 40, final result will never be over 1600; which makes mod statement somehow reflecting precision of result.
Please, help.
Look up modular multiplicative inverse.
For output a/b, does it want a*b mod (10^9 + 7)? It says Q^(-1) which is confusing because ab^(-1) = a/b.
a*(modular inverse of b with respect to 10**9 + 7)
Dynamic Programming times out. Must be a better way.
Markov Chains ?
Markov Chains definitely work, but it may be bottlenecked by the speed of matrix multiplications. The matrix representation will have n^2 x n^2 elements (although there's probably a better way to do it) and you'll have to multiple it by itself many times. For n=40 and m=100 you can expect it to be very slow.
Adjacent squares are squares that share an edge.