1038 - Race to 1 Again
Idea:
let n = 2;
it has 2 divisors, 1 and 2.
so the probability to move from 2 to any other value is (1/2.0) = 0.5
from Expected Value, if the expected value to go 1 from 2 is E then
we can go to 1 with 1 move and if we go to 2 then we need (1+E) moves
E = 0.5*1 + 0.5*(1+E)
=> 2E = 1 + (1 + E)
=> 2E = 1 + 1 + E
=> E = 2
let n = 50
divisors of n are : 1, 2, 5, 10, 25 ,50. It has 6 divisors.
so the probability to move from 50 to any other value is = (1/6.0).
let the Expected value of any number to go 1 is P() except 50.
from Expected Value, if the expected value to go 1 from 50 is E then
E = (1/6.0)*(1+0) + (1/6.0)*(1 + P(2)) + (1/6.0)*(1 + P(5)) + (1/6.0)*(1 + P(10)) + (1/6.0)*(1 + P(25)) + (1/6.0)*(1 + P(50))
=> E = (1/6.0)*1 + (1/6.0)*(1 + P(2)) + (1/6.0)*(1 + P(5)) + (1/6.0)*(1 + P(10)) + (1/6.0)*(1 + P(25)) + (1/6.0)*(1 + E)
=>E - (1/6.0)*(1+E) = (1/6.0)*1 + (1/6.0)*(1 + P(2)) + (1/6.0)*(1 + P(5)) + (1/6.0)*(1 + P(10)) + (1/6.0)*(1 + P(25))
if the sum of (probability*expected value) of all proper divisors is D then
=>E - (1/6.0)*(1+E) = D
generally we can write
=>E - (probability to move from n)*(1+E) = D
If we have of the Expected value of 2,5,10,25 then we can easily get the value of E.
In one word if we have the expected value of all the proper divisirs of a number n we can easily calculate E for n.
for this we need to store all the divisirs of all N (1 ≤ N ≤ 10^5). then if we calculate the expected value from 1 to N, we can answer our each queries in O(1).
Code
Idea:
let n = 2;
it has 2 divisors, 1 and 2.
so the probability to move from 2 to any other value is (1/2.0) = 0.5
from Expected Value, if the expected value to go 1 from 2 is E then
we can go to 1 with 1 move and if we go to 2 then we need (1+E) moves
E = 0.5*1 + 0.5*(1+E)
=> 2E = 1 + (1 + E)
=> 2E = 1 + 1 + E
=> E = 2
let n = 50
divisors of n are : 1, 2, 5, 10, 25 ,50. It has 6 divisors.
so the probability to move from 50 to any other value is = (1/6.0).
let the Expected value of any number to go 1 is P() except 50.
from Expected Value, if the expected value to go 1 from 50 is E then
E = (1/6.0)*(1+0) + (1/6.0)*(1 + P(2)) + (1/6.0)*(1 + P(5)) + (1/6.0)*(1 + P(10)) + (1/6.0)*(1 + P(25)) + (1/6.0)*(1 + P(50))
=> E = (1/6.0)*1 + (1/6.0)*(1 + P(2)) + (1/6.0)*(1 + P(5)) + (1/6.0)*(1 + P(10)) + (1/6.0)*(1 + P(25)) + (1/6.0)*(1 + E)
=>E - (1/6.0)*(1+E) = (1/6.0)*1 + (1/6.0)*(1 + P(2)) + (1/6.0)*(1 + P(5)) + (1/6.0)*(1 + P(10)) + (1/6.0)*(1 + P(25))
if the sum of (probability*expected value) of all proper divisors is D then
=>E - (1/6.0)*(1+E) = D
generally we can write
=>E - (probability to move from n)*(1+E) = D
If we have of the Expected value of 2,5,10,25 then we can easily get the value of E.
In one word if we have the expected value of all the proper divisirs of a number n we can easily calculate E for n.
for this we need to store all the divisirs of all N (1 ≤ N ≤ 10^5). then if we calculate the expected value from 1 to N, we can answer our each queries in O(1).
Code
Comments
Post a Comment