I read tutorial for December Cook-Off 2014 Player(RRPLAYER) problem and i tried to implement it using dynamic programming as explained in the editorial. my code is working fine for small inputs(i have checked many small inputs with accepted answer), but it wont work for larger inputs because there is a limitation to the size of 2d array which i can take(dp[1000][1000]). If i take size larger than that i get run-time error.
In the editorial it is written
“This approach should be used for n <=
400 (or something like this)”
But i find that this approach could only be used for much small values(not even 50),because for big values a larger 2d array is required .
So please help me to solve this for larger values of n( and could someone explain me how the editorialist managed to solve this problem for such larger values of n).
MY SOLUTION(please read the editorial you will surely understand my code, i have done exactly that(maybe :P)
This problem can be easily solved through the methods of probability: link
The above pattern can be observed from the dp table you created.
Apart from this, you can also try the following approach:
We will try to calculate the probability that it took ‘x’ songs in order to listen to the entire playlist.
So, for x=n, the number of favorable cases will be:
Say we fix one song at the end of the list. This song can be chosen in n ways. Now, at remaining of the places in the list, we can place any of the (n-1) songs. this can be done in (n-1)^(n-1) ways. However, these cases also contain those cases where not all songs are present in the list. Let A=n*((n-1)^(n-1)). Then, number of favorable cases will be: A-(number of cases where at least on song is missing from the list) + (number of cases where at least 2 songs are missing from the list)-(number of cases where at least 3 songs are missing from the list) and so on (using inclusion-exclusion principle)… Now divide the number of cases by n^n.
Find the probabilities for n+1,n+2, n+3… tries in the same way, and when finding the expectant value you will see an AGP forming…
Of course this is a much more complicated procedure than that in the wiki link…
1 Like