Page 2 of 2
Re: got WA
Posted: Fri Feb 15, 2008 9:12 pm
by DP
rezaeeEE wrote: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?
Re: 11125 - Arrange Some Marbles
Posted: Thu May 29, 2008 8:33 am
by 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
wish u get AC.
Re: 11125 - Arrange Some Marbles
Posted: Tue Jul 29, 2008 9:50 pm
by 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!!
Re: 11125 - Arrange Some Marbles
Posted: Sat Dec 19, 2009 9:14 pm
by 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.
Re: 11125 - Arrange Some Marbles
Posted: Sun May 16, 2010 10:09 pm
by atef
@kbr_iut
Do you need to clear the 'dp' array every case?
Re: 11125 - Arrange Some Marbles
Posted: Mon Sep 06, 2010 9:28 am
by Jehad Uddin
@kbr_iut
do another dp on input [8][8][8][8] ,