Problem Link

My Solution

Spacial Thanks:

• Prajogo Tio his blog has some nice explanations of some problems and he helped me a lot. (anybody knows his CodeForces User Id??)

• Hasan0540 (I analyzed his code and he helped me understanding his logic, Also my code was motivated by his code)

MY THOUGHTS

Let dp[i][j] is the expected value for guessing i-th song at j-th second. Then, say we want to guess the i th song at 4th second like this,

(a) guess the i th song at 4 th second. and already have guessed the i-1 th song at 3 dh second dp[i][4] = ( dp[i-1][3] +1) X P[i]

+

(b) guess the i th song at 4 th second, and already have guessed the i-1 th song at 2 nd second dp[i][4] = ( dp[i-1][2] +1) X (1- P[i] )X P[i]

+

(c) guess the i th song at 4 th second, and already have guessed the i-1 th song at 1 st second dp[i][4] = ( dp[i-1][1] +1) X (1- P[i] )^2 X P[i]

Now,let's find the idea how The States are compressed by observing another scenario Let we now want to calculate the expected value of guessing the i th song at time 5th second. So what would be the states?

(w) guess the i th song at 5 th second. and already have guessed the i-1 th song at 4 th second dp[i][5] = ( dp[i-1][4] +1) X P[i].

+

(x) guess the i th song at 5 th second, and already have guessed the i-1 th song at 3 rd second dp[i][5] = ( dp[i-1][3] +1) X (1- P[i] )X P[i].

+

(y) guess the i th song at 5 th second, and already have guessed the i-1 th song at 2 nd second dp[i][5] = ( dp[i-1][2] +1) X (1- P[i] )^2 X P[i].

+

(z) guess the i th song at 5 th second, and already have guessed the i-1 th song at 1 st second dp[i][5] = ( dp[i-1][1] +1) X (1- P[i] )^3 X P[i].

Now Observe, if we take (1- P[i] ) out from x + y + z it becomes dp[i][4] So finally we can write, dp[i][5] = w + (1-p[i])*( dp[i][4] ) or dp[i][5] = ( dp[i-1][4] +1) X P[i] + (1-p[i]) X ( dp[i][4] )

So in general :: dp[i][j] = dp[i-1][j-1] X p[i] + dp[i][j-1] X (1-P[i])

Ok the basic part is Over, But there is yet another thing

It was said in the problem that, if we listen to a song for t[i] seconds we can be 100% sure of it's name. If I interpret this in my own way, "when we are at time tx all we calculate is previous t[i] steps from tx, Saying in general, if we are at dp[i][time_x] state , we may want to remove the states that started t[i] second previously than time_x and we may want to add the expected value of the state that represent the 100% guaranty case.