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.
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.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Project Euler #213: Flea Circus
You are viewing a single comment's thread. Return to all 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.