Codeforces Rockethon 2015 Problem C - Second price auction

Problem Statement:
513C - Second price auction

Solution:
This is a good problem :) The official editorial to this round is very well done and you are encouraged to check them out!

Apparently this problem can be solved using a pure mathematical approach, but I would like to describe the dynamic programming approach to solve this problem. In the editorial the author describes an \(O(N(R-L))\) solution to this problem, which requires some bounding on the states. But due to the small search space of N, I decided to write an \(O(N^3(R-L))\) solution because it is a bit more intuitive :)



Lets define \(b\), the value of the second bid. Before we attempt the problem, we should firstly know that the expectation of b can be computed as \(\sum bP(b) \). Hence the problem boils down to computing P(b).

Suppose we fix b to a value. Let's define the D(i,j,k) be the probability such that for companies [1..i], there j companies that placed bids exactly equals to b, and k companies that placed bids strictly more than b. This is the DP state that works for this problem :)

Let prob[i] be the probability of company i to place each bid. To compute D(i,j,k), we have three cases:
1. The i-th company has placed a bid less than b. Then D(i,j,k) += D(i-1,j,k) * prob[i-1] * (b - L[i]).
2. The i-th company has placed a bid exactly equal to b. Then D(i,j,k) += D(i-1,j-1,k) * prob[i-1].
3. The i-th company has placed a bid more than b. Then D(i,j,k) += D(i-1,j,k-1) * prob[i-1] * (R[i] - b).

After computing all D(i,j,k), we can compute P(b) by summing up the following:
1. D(n, j, 1) for all j > 0 (because we need at least 1 company bidding b, and 1 company bidding more than b).
2. D(n, j, 0) for all j > 1 (because in case no company bids more than b, we need at least two companies bid exactly b).

And finally we sum up all b * P(b) to get the expectation.

Good problem.

#include <cstdio>
#include <algorithm>
using namespace std;
double dp[10][10][10];
int a[10][2];
int n;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d%d",&a[i][0],&a[i][1]);
    }
    double expectation = 0;
    for(int b=1;b<=10000;++b){
        for(int i=0;i<10;++i)for(int j=0;j<10;++j)for(int k=0;k<10;++k)dp[i][j][k]=0;
        dp[0][0][0] = 1.0;
        for(int i=1;i<=n;++i){
            for(int j=0;j<=n;++j){
                for(int k=0;k<=n;++k){
                    double prob = 1.0/(a[i][1]-a[i][0]+1);
                    double temp = 0;
                    //lower
                    temp = dp[i-1][j][k] * (min(b-a[i][0], a[i][1]-a[i][0]+1)) * prob;
                    if(temp < 0) temp = 0;
                    dp[i][j][k] += temp;
                    temp = 0;
                    //equal
                    if(a[i][0] <= b && b <= a[i][1])
                        if(j>0)
                            dp[i][j][k] += dp[i-1][j-1][k] * prob;
                    //higher
                    if(k>0)temp = dp[i-1][j][k-1] * (min(a[i][1]-b, a[i][1]-a[i][0]+1)) * prob;
                    if(temp < 0) temp = 0;
                    dp[i][j][k] += temp;
                }
            }
        }
        for(int j=1;j<=n;++j){
            expectation += 1.0 * b * dp[n][j][1];
            if(j>1) expectation += 1.0 * b * dp[n][j][0];
        }
    }
    printf("%.12lf\n",expectation);
    return 0;
}