11125 - Arrange Some Marbles

[lonelyone]

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]

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]

I got Accepted.


the spacial case appears when all numbers are zero

thanks all the same

[vinay]

that's the most critical one

[cpphamza]

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]

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]

mine is 9-dimensions
even more ugly

[ziliang]

灌个水!

[Naani]

@cpphamza,
could you post your code please

Code: Select all

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

using namespace std;
#define LL long long

LL 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

[cpphamza]

Here is my code,

Code: Select all

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

#define big int
int 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?

[FAQ]

Did you forget this line?

Code: Select all

#include <cstring>

[cpphamza]

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]

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

[tanaeem]

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

[rezaeeEE]

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.