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
I write a Recursive Function; however, I couldn't find a way to memorize
some path.
Any one give me some hint, please.
Lonely
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?
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?
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
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
[ ]
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];
![:(](./images/smilies/icon_frown.gif)
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];
????
@cpphamza,
could you post your code please
This was my code during the contest. I got TLE though, thanks very much in advance.
Vinay Emani
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;
}
Vinay Emani
I am signing an important document!
Here is my code,
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?
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;
}
Did you forget this line?
Code: Select all
#include <cstring>
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![:)](./images/smilies/icon_smile.gif)
anyway i'll try cstring the next time i got compilation error for memset
![:)](./images/smilies/icon_smile.gif)
hi , it is not good to post solution code directlycpphamza 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
![:)](./images/smilies/icon_smile.gif)
studying @ ntu csie
Gettting Wa, can someone provide some data
Got AC.
But someone explain why all 0 should give result 1
But someone explain why all 0 should give result 1
got WA
i can't find any bug in my code.
Can any body help me?
thanks.
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;
}