# 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/

vali_dragan6 + 1 comment How is 675/44 = 113636380 (mod 10^9 + 9), I've been looking at this for over 30 minutes..

kmcshane + 0 comments This may help you. https://www.geeksforgeeks.org/modular-division/

Note: the C++ code will overflow 32 bit ints when using modulo 10^9+9, so I suggest you replace ints with longs.

emad_aghili + 1 comment Imagine a circle and person1 and person2 who have the dice and are sitting exactly opposite to each other on the left and write side of the circle. The probability of person1 rolling 1 and person2 rolling m, is equal to the probability of person1 rolling m and person2 rolling 1. That means the probability of each moving one step in the upper half of the circle (and therefore reducing the distance by two units) is equal to the probability of them doing the same thing in the lower half. And the same is true for other types of move (no passing and one to the right or left). Imho, the average is infinite.

jpking10 + 1 comment When dice are at their furthest distance there are three options for the change in distance: stay the same, reduce by one or reduce by two.

In this problem there are a finite number of states and there is an exact solution.

Iâ€™ve written a few ideas down which should point you in the right direction for solving this one: https://www.jamespking.com/posts/hackerrank-projecteuler-227-writeup/

emad_aghili + 1 comment But when they are not at their furthest distance there is more options including increasing the distance by 1 and increasing by two

jpking10 + 0 comments What's the expected value of a fair dice?

You can still model this situation and find an exact answer.

animeshs650 + 2 comments how to read input from stdin.....i m using c language

jpking10 + 0 comments maybe cin?

chandramouli_ga1 + 0 comments scanf() i guess

jamalrachidi250 + 0 comments **

PRIZES: 1st $100, 2nd $50, 3rd $5, 4th $3, 5th $1 PRIZES: 1st $100, 2nd $50, 3rd $5, 4th $3, 5th $1

**

Sort 12 Discussions, By:

Please Login in order to post a comment