Codeforces Round 284 Div. 1 Problem B - Name That Tune

Problem Statement:
498B - Name That Tune

Solution:
A tough problem, not only because it is a conceptually difficult problem on probability, but also coupled by the fact that the problem constrain is very, very tight. In fact I have rewrote my implementation, which all are based by the idea described in the official editorial, just to reduce constant term in the running time complexity. But a good problem nevertheless :)

DP state that works here is as follows:
Let D[i][k] be the probability of the person guessing i-th song exactly at time k seconds. The base case for D is that of D[0][0] which means guessing none of the song exactly at time 0 second.



To fill up D, we can fill up each row i as follows:
1. First, notice that if we can guess (i-1) th song in k-j second, for all j \(\in [1,\ldots, t[i-1]]\), then we can guess D[i][k] in  \((1-p[i-1])^{j-1} p[i-1] D[i-1][k-j] \), for all j (the terms before D[i-1][k-j] simply represent the probability of guessing j-1 problems wrong and guessing the last one correctly).
2. Secondly, there is also the case where we have guessed (i-1) th song in k-t[i-1] second, which contributes additional probability to D[i][k] by \((1-p[i-1])^{j-1} D[i][k-t[i-1]] \). (Which means guessing all j-1 problems wrongly, and having a correct guess for the last one after listening to the chorus).

If we can fill those up efficiently, to find the expectation of the number of songs guessed, for each question i, we calculate the probability of having guessed up to i-th song when the game ends, which is where k = T. This means we sum up \(D[i][T-j] (1-p[i])^{j}\) for all \(1 \leq j < t[i]\). (This means after guessing i-th song exactly at T-j seconds, we simply guessed wrongly until the game ends at time k = T.)

Now, the implementing the DP calculation of D as described above will give us \(O(NT^2)\). But it is possible to reduce the running time to \(O(NT)\) by observing this fact:
When calculating D[i][k] of row i, we always use the values in row i-1 (that is, D[i-1][k-j] for some values of j), hence the row i-1 is actually fixed. And another important thing is that the calculation is done in a continuous interval.

That gives us a way to implement a trailing "sum" of elements in D[i-1] to use for calculating D[i]. Below is an implementation of the idea:

#include <cstdio>
#include <cmath>

double p[5005];
int t[5005];
double prob[5005][5005];
int N, T;

int main(){
 scanf("%d%d", &N, &T);
 for(int i=0;i<N;++i){
  scanf("%lf%d", &p[i], &t[i]);
  p[i] *= 0.01;
 }
 prob[0][0] = 1;
 double ans = 0;
 double cur = 0;
 double tmp = 0;
 double q;
 for(int i=1;i<=N;++i){
  cur = 0;
  tmp = 0;
  q = pow(1-p[i-1],t[i-1]-1);
  for(int k=0;k<=T;++k){
   cur = cur * (1-p[i-1]) + prob[i-1][k];
   if(k >= t[i-1]-1){
    cur -= prob[i-1][k-t[i-1]+1] * q;
    prob[i][k] += prob[i-1][k-t[i-1]] * q;
   }
   if(k >= T-t[i-1] && k < T){
    tmp = prob[i-1][k+1] + (1-p[i-1]) * tmp;
   }
   prob[i][k+1] = cur * p[i-1];
  }
  ans += tmp * (i-1);
 }
 for(int k=0;k<=T;++k){
  ans += N * prob[N][k];
 }
 printf("%.12lf\n", ans);
 return 0;
}