11125 - Arrange Some Marbles

All about problems in Volume 111. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

Re: got WA

Post by DP » Fri Feb 15, 2008 9:12 pm

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

Post by Anindya » Thu May 29, 2008 8:33 am

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

Post by Leonid » Tue Jul 29, 2008 9:50 pm

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

User avatar
kbr_iut
Experienced poster
Posts: 103
Joined: Tue Mar 25, 2008 11:00 pm
Location: IUT-OIC, DHAKA, BANGLADESH
Contact:

Re: 11125 - Arrange Some Marbles

Post by kbr_iut » Sat Dec 19, 2009 9:14 pm

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.
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

Post by atef » Sun May 16, 2010 10:09 pm

@kbr_iut

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

Jehad Uddin
Learning poster
Posts: 74
Joined: Fri May 08, 2009 5:16 pm

Re: 11125 - Arrange Some Marbles

Post by Jehad Uddin » Mon Sep 06, 2010 9:28 am

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

Post Reply

Return to “Volume 111 (11100-11199)”