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

## No comments:

## Post a Comment