## 11125 - Arrange Some Marbles

Moderator: Board moderators

### 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
lonelyone
Learning poster

Posts: 65
Joined: Sat Feb 19, 2005 6:53 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
ziliang
New poster

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

that's the most critical one
If I will myself do hashing, then who will do coding !!!

vinay
Experienced poster

Posts: 104
Joined: Thu Apr 13, 2006 2:26 pm
Location: India

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
cpphamza
New poster

Posts: 18
Joined: Sat Sep 09, 2006 12:55 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[28][4][3][8][8][8][8][4][3];
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

### [ ]

ziliang
New poster

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

### ????

@cpphamza,
Code: Select all
`#include <iostream>#include <cmath>#include <vector>#include <algorithm>#include <string>#include <cstring>using namespace std;#define LL long longLL res[8][8][8][8][4][3];int maxs[4],FC,FG,N,tmp[4];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[0]=l1;tmp[1]=l2;tmp[2]=l3;tmp[3]=l4;tmp[i]-=j;   tot += ways(tmp[0],tmp[1],tmp[2],tmp[3],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[0]-j,maxs[1],maxs[2],maxs[3],i,j-1);     if(i==1)result+=ways(maxs[0],maxs[1]-j,maxs[2],maxs[3],i,j-1);    if(i==2)result+=ways(maxs[0],maxs[1],maxs[2]-j,maxs[3],i,j-1);    if(i==3)result+=ways(maxs[0],maxs[1],maxs[2],maxs[3]-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!
Naani
New poster

Posts: 12
Joined: Mon Sep 25, 2006 11:10 am
Location: India

Here is my code,
Code: Select all
`#include<algorithm>#include<iostream>using namespace std;#define big intint cNum[4];big table[5][8][8][8][8][8][5][8];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[4] = {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[0], num[1], num[2], num[3], 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[0], cNum[1],cNum[2],cNum[3],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?
cpphamza
New poster

Posts: 18
Joined: Sat Sep 09, 2006 12:55 pm

Did you forget this line?
Code: Select all
`#include <cstring>`
FAQ
Learning poster

Posts: 84
Joined: Wed Jan 28, 2004 6:23 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
cpphamza
New poster

Posts: 18
Joined: Sat Sep 09, 2006 12:55 pm

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
SRX
Learning poster

Posts: 63
Joined: Sat May 14, 2005 8:13 am
Location: Taiwan

### Gettting Wa, can someone provide some data

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

Posts: 26
Joined: Mon Mar 12, 2007 6:58 pm
Location: BUET

### 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[8][8][8][8][4][4][4][4];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[4] = {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[4];            for( int k = 0;k < 4; k++ )               temp[k] = a[k];            temp[j] = a[j] - i;            res += solve( temp[0], temp[1], temp[2], temp[3], i, fir, j, firsize );         }   return res;}int main(){   int test, ted[4], 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[0][0][0][0][k][i][j][z] = 0;                  else dp[0][0][0][0][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[4];         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[0], temp[1], temp[2], temp[3], j, i, i, j );         }      }      cout << res << endl;   }   return 0;}`

thanks.
rezaeeEE
New poster

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

Next

### Who is online

Users browsing this forum: No registered users and 1 guest