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.
  1. All Contests
  2. ProjectEuler+
  3. Project Euler #227: The Chase
  4. Discussions

Project Euler #227: The Chase

Sort 12 Discussions, By:

votes

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

Load more conversations