Project Euler #213: Flea Circus

Sort by

recency

|

6 Discussions

|

  • + 0 comments

    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.

  • + 1 comment

    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.

    • + 0 comments

      Look up modular multiplicative inverse.

  • + 1 comment

    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.

    • + 0 comments

      a*(modular inverse of b with respect to 10**9 + 7)

  • + 2 comments

    Dynamic Programming times out. Must be a better way.
    Markov Chains ?

    • + 0 comments

      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.

  • + 0 comments

    Adjacent squares are squares that share an edge.