CF335E Counting Skyscrapers

Provide a worst-case solution first and huge and difficult to write(

Bob

Obviously, the real building volume can reach \ (314! \), and there is no way to do it directly. With the example of the only scheme, you can guess that there is a simple conclusion.

Consider that when the building height is \ (K (k<h) \), the contribution of each height to the answer is \ (2^{k-1}\times 2^{-k}\), i.e. \ (\frac{1}{2}\), and when the building height is \ (K \ge h) \, the contribution of each height to the answer is \ (2^k\times 2^{-k}\), i.e. \ (1\). Obviously, the contributions have nothing to do with \ (h\), that is, the conclusion is only related to \ (n\). It is easy to guess that the answer is \ (n\) with a few groups of data and samples.

Code:

void Sub2(){
	scanf("%d%d",&n,&h);
	printf("%d\n",n);
}

Alice

It is observed that the buildings with a height of \ (\ge h\) are essentially the same. The height interval of the buildings can be determined as \ ([1,h]\) (the probability of a height of \ (h\) becomes \ (2^{1-h}\).

If the height of building \ (k\) is the highest, Bob must pass building \ (k\). It is easy to find that in front of building \ (k\), the height of the building Bob passes by is monotonous, and behind building \ (k\) is monotonous.

Note that in order to prevent double counting, if the height is the same, the highest one in front shall be determined by imperial court.

Then you can transfer.

Let \ (f_{i,j,k,0/1}\) indicate that building \ (i\) has been transferred, and the height of the last passing building \ (x\) is \ (j\). The maximum height of \ ([x+1,i]\) is \ (k\), which is the expectation of whether to pass the highest building.

Let \ (g_{i,j,k,0/1}\) indicate that building \ (i\) has been transferred, and the height of the last passing building \ (x\) is \ (j\). The maximum height of \ ([x+1,i]\) is \ (k\), which is the probability of whether to pass the highest building.

When DP, use the brush table method to enumerate the height transfer of building \ (i\). The time complexity \ (O(nh^3) \) should be stuck and the array should be scrolled.

Code:

const double eps=1e-15;
const int maxn=30010;
const int maxh=35;
int n,h;
double g[2][maxh][maxh][2];
double f[2][maxh][maxh][2];
double V[maxh],S[maxh];
void Sub1(){
	scanf("%d%d",&n,&h);
	for(int i=0;i<h;i++){
		V[i]=1.0/(1<<i+1),S[i]=(1-1.0/(1<<i));
		f[1][i][0][0]=V[i]+0.5,g[1][i][0][0]=V[i];
	} 
	if(h) V[h]=V[h-1],S[h]=(1-1.0/(1<<h));
    else V[h]=1;
	for(int i=0;i<=h;i++) f[1][i][0][1]=V[i],g[1][i][0][1]=V[i];
	//The above is initialization
    double tmp1,tmp2,tmp;
	for(int i=1,ii=1,iii=0;i<n;i++,ii^=1,iii^=1){
		memset(f[iii],0,sizeof(f[iii]));
		memset(g[iii],0,sizeof(g[iii]));
      	//Note that when j=i (Bob passes through the current building) k is also 0
      	//K and u enumerated here are all added with 1 (k is 0 only when j=0)
      
      	//For the sake of stability, the transfer formula is ugly, but the essence is the same
		for(int j=0;j<=h;j++)
			for(int k=0;k<=j;k++){
				tmp1=f[ii][j][k][0],tmp2=g[ii][j][k][0],tmp=tmp2/2;
				if(tmp1>eps){
					//u<=k
					f[iii][j][k][0]+=tmp1*S[k];
					g[iii][j][k][0]+=tmp2*S[k];
					tmp1*=V[k],tmp2*=V[k];
					//--------
				 	for(int u=k+1;u<=h+1;u++){
						if(u-1>=j) f[iii][u-1][0][0]+=tmp1+tmp,g[iii][u-1][0][0]+=tmp2;
						else f[iii][j][u][0]+=tmp1,g[iii][j][u][0]+=tmp2;
						if(u-1>j) f[iii][u-1][0][1]+=tmp1,g[iii][u-1][0][1]+=tmp2;
						if(u<h) tmp1/=2,tmp2/=2;
					}
					f[iii][h][0][0]+=tmp;
				}
				tmp1=f[ii][j][k][1],tmp2=g[ii][j][k][1],tmp=tmp2/2;
				if(tmp1>eps){
					//u<=k
					f[iii][j][k][1]+=tmp1*S[k];
					g[iii][j][k][1]+=tmp2*S[k];
					tmp1*=V[k],tmp2*=V[k];
					//--------
                  for(int u=k+1;u<=j+1;u++){
						f[iii][u-1][0][1]+=tmp1+tmp,g[iii][u-1][0][1]+=tmp2;
						if(u-1<j) f[iii][j][u][1]+=tmp1,g[iii][j][u][1]+=tmp2;
						if(u<h) tmp1/=2,tmp2/=2; 
					}
					if(j==h) f[iii][h][0][1]+=tmp;
				} 
			}
	}
	double ans=0;
	for(int i=0;i<=h;i++)
		ans+=f[n&1][i][0][1];
	printf("%.9lf",ans);
}

Can it be faster?

In essence, the above expected DP is divided into \ ([1,k],[k+1,j][j+1,h]\) three intervals to transfer rows and columns respectively. Considering that the decision point is placed on the segment tree, the problem is converted to interval modification / single point query of the segment tree, with time complexity \ (O(nh^2\log h) \).

However, since it is necessary to discuss whether \ (f,g\) and whether it passes through the tallest building, row or column, it is necessary to open \ (8nh\) segment trees and run \ (10s+\) local limit data, which has no real effect.

Can it be faster?

It is observed that the transfer equation has nothing to do with \ (n\). It is considered to construct a matrix of \ (h\times h\), just run the fast power of the matrix, and the time complexity \ (O(h^3logn) \) is better in time and space.

Posted by joe2 on Mon, 30 May 2022 11:51:08 +0530