## Tuesday, February 10, 2015

### 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;
}