datsko_d 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 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 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 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 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 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 Wow, thx a lot :)
asdfyhsauiui From where the 675 and 44 are came from?
jpking10 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 tym pass
maxxi9 I figured out the answers, but I can't convert to 10e9+9
jpking10 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 How is 675/44 = 113636380 (mod 10^9 + 9), I've been looking at this for over 30 minutes..
kmcshane 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 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 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 But when they are not at their furthest distance there is more options including increasing the distance by 1 and increasing by two
jpking10 What's the expected value of a fair dice?
You can still model this situation and find an exact answer.
animeshs650 how to read input from stdin.....i m using c language
jpking10 maybe cin?
chandramouli_ga1 scanf() i guess
jamalrachidi250 **
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