## 11125 - Arrange Some Marbles

Moderator: Board moderators

lonelyone
Learning poster
Posts: 65
Joined: Sat Feb 19, 2005 6:53 pm

### 11125 - Arrange Some Marbles

I would like to know how to DP it.
I write a Recursive Function; however, I couldn't find a way to memorize
some path.

Any one give me some hint, please.

Lonely

ziliang
New poster
Posts: 19
Joined: Sat Sep 30, 2006 2:50 pm

### 11125 give me some data please

i wrote it in a DP method.
and my result is the same as what i wrote it in recursive searching.
but i keep getting WA.

is there any special data?

can anyone give me some?

ziliang
New poster
Posts: 19
Joined: Sat Sep 30, 2006 2:50 pm

### [ ] I got Accepted.

the spacial case appears when all numbers are zero thanks all the same

vinay
Experienced poster
Posts: 104
Joined: Thu Apr 13, 2006 2:26 pm
Location: India
Contact:
that's the most critical one If I will myself do hashing, then who will do coding !!!

cpphamza
New poster
Posts: 18
Joined: Sat Sep 09, 2006 12:55 pm
During the contest i got AC using the following recursion

get(firstGroupColor, firstGroupSize,firstColorAvaiable,secondColorAvaiable,
thirdColorAvaiable,fourthColorAvaiable, prevGroupColor, prevGroupSize) =
{
num = 0;
for(each color i from 1 to 4)
for(each size j from 1 to avaialable of color i)
if(we can form a group with color i and size j){
num += get(update params appropriately);
}

return num;
}

and I've memorized in an ugly an 8 dimensions array. Hope this helps

ziliang
New poster
Posts: 19
Joined: Sat Sep 30, 2006 2:50 pm

### [ ]

my DP is 9-dimension. that's so terrible.

anyone can help me with a less dimension?

mine is

int dp[current lenth][start color][start lenth][current 1st color usage][current 2ed color usage][current 3rd color usage][current 4th color usage][current end color][current end lenth]

that is :
int dp;

ziliang
New poster
Posts: 19
Joined: Sat Sep 30, 2006 2:50 pm

### [ ]

mine is 9-dimensions even more ugly ziliang
New poster
Posts: 19
Joined: Sat Sep 30, 2006 2:50 pm

### [ ]

Naani
New poster
Posts: 12
Joined: Mon Sep 25, 2006 11:10 am
Location: India
Contact:

### ????

@cpphamza,

Code: Select all

``````#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <string>
#include <cstring>

using namespace std;
#define LL long long

LL res;

int maxs,FC,FG,N,tmp;

LL ways(int l1,int l2,int l3,int l4,int prevc,int prevg)
{
if(l1+l2+l3+l4==0)return prevc!=FC&&prevg!=FG;
if(res[l1][l2][l3][l4][prevc][prevg]>=0)return res[l1][l2][l3][l4][prevc][prevg];
LL tot = 0;
for(int i=0;i<4;i++)
{
if(i==prevc)continue;int max = i==0?l1:(i==1?l2:(i==2?l3:l4));
for(int j=1;j<=3&&j<=max;j++)
{
if(j-1==prevg)continue;tmp=l1;tmp=l2;tmp=l3;tmp=l4;tmp[i]-=j;
tot += ways(tmp,tmp,tmp,tmp,i,j-1);tmp[i]+=j;
}
}
return res[l1][l2][l3][l4][prevc][prevg]=tot;
};

int main()
{
int T,i,j,k;
cin >> T;
while(T--)
{
cin >> N;
memset(maxs,0,sizeof(maxs));
for(i=0;i<N;i++)cin >> maxs[i];LL result = 0;
for(i=0;i<4;i++)
{
for(j=1;j<=3&&j<=maxs[i];j++)
{
memset(res,-1,sizeof(res));FG = j-1;FC = i;
if(i==0)result+=ways(maxs-j,maxs,maxs,maxs,i,j-1);
if(i==1)result+=ways(maxs,maxs-j,maxs,maxs,i,j-1);
if(i==2)result+=ways(maxs,maxs,maxs-j,maxs,i,j-1);
if(i==3)result+=ways(maxs,maxs,maxs,maxs-j,i,j-1);
}
}
cout << result << "\n";
}
return 0;
}
``````
This was my code during the contest. I got TLE though, thanks very much in advance.
Vinay Emani
I am signing an important document!

cpphamza
New poster
Posts: 18
Joined: Sat Sep 09, 2006 12:55 pm
Here is my code,

Code: Select all

``````#include<algorithm>
#include<iostream>
using namespace std;

#define big int
int cNum;

big table;

big get(int firstColor, int firstSize, int c1, int c2, int c3, int c4, int prevColor, int prevSize){

if(c1 == 0 && c2 == 0 && c3 == 0 && c4 == 0)
return (prevColor == firstColor || prevSize == firstSize) ? 0 : 1;

if(table[firstColor][firstSize][c1][c2][c3][c4][prevColor][prevSize] != -1)
return table[firstColor][firstSize][c1][c2][c3][c4][prevColor][prevSize];

int num = {c1,c2,c3,c4};
big r = 0;
for(int i = 0 ; i < 4 ; i++){

if(num[i] == 0 || i == prevColor)
continue;

for(int j = 1 ; j <= num[i] ; j++){

if(j == 4)
break;

if(j == prevSize)
continue;

int fc = firstColor == 4 ? i : firstColor;
int fs = firstColor == 4 ? j : firstSize;

num[i] -= j;

r += get(fc, fs, num, num, num, num, i, j);

num[i] += j;
}
}

table[firstColor][firstSize][c1][c2][c3][c4][prevColor][prevSize] = r;
return r;
}

int main(){

//	freopen("1.in", "r", stdin);
//	freopen("1.out", "w", stdout);

int tt; cin >> tt;

for(int c1 = 0 ; c1 < 5 ; c1++)
for(int c2 = 0 ; c2 < 8 ; c2++)
for(int c3 = 0 ; c3 < 8 ; c3++)
for(int c4 = 0 ; c4 < 8 ; c4++)
for(int c5 = 0 ; c5 < 8 ; c5++)
for(int c6 = 0 ; c6 < 8 ; c6++)
for(int c7 = 0 ; c7 < 5 ; c7++)
for(int c8 = 0 ; c8 < 8 ; c8++)
table[c1][c2][c3][c4][c5][c6][c7][c8] = -1;

//memset(table, -1, sizeof(table));
for(int t = 0 ; t < tt ; t++){

fill(cNum, cNum+4, 0);
//
int colors; cin >> colors;
int i, ones = 0;
for( i = 0 ; i < colors ; i++){
cin >> cNum[i];
if(cNum[i] > 0)
ones++;
}

if(ones == 0)
cout << "1" << endl;
else if(ones == 1)
cout << "0"<< endl;
else{
big r = get(4, 0, cNum, cNum,cNum,cNum,4,0);
cout << r << endl;
//	r = r;
}
}
return 0;
}``````
by the way, I always get compile error when using memset at UVA (which made me initialize the array using 8 nested loops), does anyone know why is this? am i missing some header file or so?

FAQ
Learning poster
Posts: 84
Joined: Wed Jan 28, 2004 6:23 pm
Did you forget this line?

Code: Select all

``````#include <cstring>
``````

cpphamza
New poster
Posts: 18
Joined: Sat Sep 09, 2006 12:55 pm
Usually i don't include <cstring>, memset doesn't need it on VC++ and GCC if i remember correctly, but the wierd thing is that i tried to submit the problem now with memset and without including any additional headers and got AC!

anyway i'll try cstring the next time i got compilation error for memset SRX
Learning poster
Posts: 63
Joined: Sat May 14, 2005 8:13 am
Location: Taiwan
cpphamza wrote:Usually i don't include <cstring>, memset doesn't need it on VC++ and GCC if i remember correctly, but the wierd thing is that i tried to submit the problem now with memset and without including any additional headers and got AC!

anyway i'll try cstring the next time i got compilation error for memset hi , it is not good to post solution code directly studying @ ntu csie

tanaeem
New poster
Posts: 26
Joined: Mon Mar 12, 2007 6:58 pm
Location: BUET
Contact:

### Gettting Wa, can someone provide some data

Got AC.
But someone explain why all 0 should give result 1

rezaeeEE
New poster
Posts: 25
Joined: Fri May 11, 2007 3:45 pm

### got WA

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

Code: Select all

``````#include <iostream>

using namespace std;

int dp;

int solve( int a1, int a2, int a3, int a4, int siz, int fir, int last, int firsize ){
if( dp[a1][a2][a3][a4][siz][fir][last][firsize] != -1 )
return dp[a1][a2][a3][a4][siz][fir][last][firsize];
int & res = dp[a1][a2][a3][a4][siz][fir][last][firsize];
res = 0;
int a = {a1, a2, a3, a4};
for( int i = 1; i <= 3; i++ )
for( int j = 0; j < 4; j++ )
if( last != j && siz != i && a[j] >= i ){
int temp;
for( int k = 0;k < 4; k++ )
temp[k] = a[k];
temp[j] = a[j] - i;
res += solve( temp, temp, temp, temp, i, fir, j, firsize );
}
return res;
}

int main()
{
int test, ted, n;
memset( dp, -1, sizeof dp );
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[k][i][j][z] = 0;
else dp[k][i][j][z] = 1;
for( cin >> test; test--; ){
cin >> n;
memset( ted, 0, sizeof ted );
for( int i = 0;i < n; i++ )
cin >> ted[i];
int res = 0;
for( int i = 0;i < n; i++ ){
int temp;
for( int j = 0;j < 4; j++ )
temp[j] = ted[j];
for( int j = 1; j <= min( 3, ted[i] ); j++ ){
temp[i] = ted[i] - j;
res += solve( temp, temp, temp, temp, j, i, i, j );
}
}
cout << res << endl;
}
return 0;
}
``````
thanks.