# Project Euler #227: The Chase

# Project Euler #227: The Chase

datsko_d + 1 comment Can someone explain me the task? What do p and q mean? And why does the answer exist(what if on every step they both roll neither 1 nor m?)

jpking10 + 1 comment The answer exists because we are calculating the

**expected**number of turns.Think of a fair 6 sided dice. The expected outcome is the sum of each potential outcome multiplied by the probability of that outcome:

1*(1/6) + 2*(1/6) + 3*(1/6) + 4*(1/6) + 5*(1/6) + 6*(1/6) = 3.5

In other words, if we rolled the dice an infinite number of times we'd expect the average to be 3.5.

I wrote an article with some hints. https://www.jamespking.com/posts/hackerrank-projecteuler-227-writeup/

oleg_b + 1 comment Just a small nitpick about the article:

A particular language is not an issue; a good algorithm is much more important. For example, it is possible to implement a Python2 solution with 2.6 sec worst run-time.

The idea is to avoid an impression of impossibility to get 100% AC if you are limited to a scripted language like Python. At least for this particular problem :)

jpking10 + 0 comments Thanks for the advice oleg :)

I grappled with the Python3 solution for a while before porting it over. My approach probably isn't the most efficient (I'm new to this). I'd love to take a look at your approach.

moonpine1016 + 1 comment The only problem is that I don't know how the hell is 675/44 = 113636380 (mod 10^9 + 9).

Could anyone give me an example about how to magically turn 675 and 44 into 113636380?

jpking10 + 1 comment See https://www.jamespking.com/posts/hackerrank-projecteuler-227-writeup/

Also note that 44 * 113636380 % (10**9 + 9) = 675

Since the modulo operation is not distributive over division we can't directly calculate 675/44 (mod 10^9 + 9). Instead, we find the multiplicative inverse of 44 (ie. 1/44) and use that (as discussed in the article).

moonpine1016 + 0 comments Wow, thx a lot :)

asdfyhsauiui + 1 comment From where the 675 and 44 are came from?

jpking10 + 0 comments See https://www.geeksforgeeks.org/multiplicative-inverse-under-modulo-m/ Also note that 44 * 113636380 % (10**9 + 9) = 675 Since the modulo operation is not distributive over division we can't directly calculate 675/44 (mod 10^9 + 9). Instead, we find the multiplicative inverse of 44 (ie. 1/44) and use that (as discussed in the article). For more info on why we use the modulo operation read https://www.hackerearth.com/practice/notes/abhinav92003/why-output-the-answer-modulo-109-7/

wiprosurya1999 + 0 comments tym pass

maxxi9 + 1 comment I figured out the answers, but I can't convert to 10e9+9

jpking10 + 0 comments Your solution probably lacks the efficiency needed for the bigger inputs.

See https://www.geeksforgeeks.org/multiplicative-inverse-under-modulo-m/ Also note that 44 * 113636380 % (10**9 + 9) = 675 Since the modulo operation is not distributive over division we can't directly calculate 675/44 (mod 10^9 + 9). Instead, we find the multiplicative inverse of 44 (ie. 1/44) and use that (as discussed in the article). For more info on why we use the modulo operation read https://www.hackerearth.com/practice/notes/abhinav92003/why-output-the-answer-modulo-109-7/

Sort 12 Discussions, By:

Please Login in order to post a comment