11125 - Arrange Some Marbles

[DP]

i can't find any bug in my code.
Can any body help me?

if( dp[a1][a2][a3][a4][siz][fir][last][firsize] != -1 )
return dp[a1][a2][a3][a4][siz][fir][last][firsize];
................
....
for( int i = 0;i < 4; i++ )
for( int j = 0;j < 4; j++ )
for( int k = 0;k < 4; k++ )
for( int z = 0; z < 4; z++ )
if( i == j || k == z )
dp[0][0][0][0][k][j][z] = 0;
else dp[0][0][0][0][k][j][z] = 1;
thanks.

What is going here?:-? Did you get correct output for Sample Test Case?

[Anindya]

Those who got WA check the data set given below:
Input:

Code: Select all

12
1 7
1 6
1 5
1 3
1 1
1 0
2 0 0
3 0 0 0
4 7 7 7 7
2 7 6
2 7 7
4 0 3 4 5

Output:

Code: Select all

0
0
0
0
0
1
1
1
688022064
6
0
174

wish u get AC.

[Leonid]

I spent about half of a year to solve this problem!
I wrote 3 different approaches and finally AC with a very elegant solution!!

[kbr_iut]

I coded with 8 dimensional ugly memoized solution and got TLE.....how 8 dimension gets AC? or am I missing something
here is my code.

Code: Select all

#include<iostream>
#include<string.h>
#include<algorithm>
#include<numeric>
#include<vector>
using namespace std;
int sum,r,n,N,R,C,t,txt;
typedef vector<int> vi;
typedef long long LL;

LL dp[5][8][8][8][8][8][5][8];
LL doit(int c,int c1,int c2,int c3,int c4,int len,int fc,int flen){
	LL &ret=dp[c][c1][c2][c3][c4][len][fc][flen];
	if(ret!=-1)return ret;
	if(c1==0&&c2==0&&c3==0&&c4==0){
		if(c==fc||len==flen)return ret=0;
		else return ret=1;
	}
	ret=0;
	vi v(5);v[1]=c1;v[2]=c2;v[3]=c3;v[4]=c4;
	for(int i=1;i<=n;i++){
		if(!v[i]||i==c)continue;
		for(int j=1;j<=v[i]&&j<=3;j++){
			if(j==len)continue;
			vi vv=v;vv[i]-=j;
			if(fc==0)ret+=doit(i,vv[1],vv[2],vv[3],vv[4],j,i,j);
			else ret+=doit(i,vv[1],vv[2],vv[3],vv[4],j,fc,flen);
		}
	}
	return ret;
}
int main(){
#ifndef ONLINE_JUDGE
	freopen("1.txt","r",stdin);
	//freopen("out.txt","r",stdout);
#endif
	int i,j,k;
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		memset(dp,-1,sizeof(dp));
		vi v(5,0);
		for(i=1;i<=n;i++)cin>>v[i];
		int sum=accumulate(v.begin(),v.end(),0);
		if(!sum){printf("1\n");sum=0;continue;}
		LL rr=doit(0,v[1],v[2],v[3],v[4],0,0,0);
		printf("%lld\n",rr);
	}
	return 0;
}

thanx in advance.

[atef]

@kbr_iut

Do you need to clear the 'dp' array every case?

[Jehad Uddin]

@kbr_iut
do another dp on input [8][8][8][8] ,