## 11125 - Arrange Some Marbles

Moderator: Board moderators

DP
Learning poster
Posts: 62
Joined: Sun Aug 13, 2006 9:15 am
Contact:

### Re: got WA

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?

Anindya
New poster
Posts: 28
Joined: Sun Feb 04, 2007 4:34 am
Location: EEE,BUET,DHAKA

### Re: 11125 - Arrange Some Marbles

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
Experienced poster
Posts: 146
Joined: Thu Dec 22, 2005 5:50 pm
Contact:

### Re: 11125 - Arrange Some Marbles

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
Experienced poster
Posts: 103
Joined: Tue Mar 25, 2008 11:00 pm
Contact:

### Re: 11125 - Arrange Some Marbles

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;
}
It is tough to become a good programmer.
It is more tough to become a good person.
I am trying both...............................

atef
New poster
Posts: 1
Joined: Wed Dec 24, 2008 9:29 pm

### Re: 11125 - Arrange Some Marbles

@kbr_iut

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