Project Euler #227: The Chase

Sort by

recency

|

13 Discussions

|

  • + 0 comments

    Looking back at this one, I believe it can be solved quickly for n < 10^18, m < 10^18, in O( log( n ) ).

  • + 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.

    • + 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/

      • + 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

        • + 0 comments

          What's the expected value of a fair dice?

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

  • + 2 comments

    how to read input from stdin.....i m using c language

    • + 0 comments

      maybe cin?

    • + 0 comments

      scanf() i guess

  • + 1 comment

    From where the 675 and 44 are came from?

    • + 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/

  • + 0 comments

    tym pass