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.