11420 - Chest of Drawers

[f74956227]

Is this a DP problem? or a combination math problem.. i have tried a lot but still have no idea with this problem...can someone give me a little hints?

[sclo]

Could you include the name of the problem in the topic?
Yes, I believe this problem is DP.

[emotional blind]

Code: Select all

nway(n, s, pdl)  = nway(n-1, s, 0) + nway(n-1, s-1, 1)    if pdl=1
                        = nway(n-1, s, 0) + nway(n-1, s, 1) if pdl =0

here,
n = number of drawer
s = number of drawer to be secured
pdl = last drawer locked or not [1 means locked]

[Robert Gerbicz]

Don't forget that if s>n, then the answer is 0. (There are such tests in the input.)

[f74956227]

i finally got ac but i think the recursive function of the DP is

n(a,b,1)=n(a-1,b-1,1)+n(a-1,b-1,0)
n(a,b,0)=n(a-1,b+1,1)+n(a-1,b,0)

a is the number of drawer and b is the secured-num and the 0 or 1 means that the situation of the top drawer.

Finally thank all of you^^

[emotional blind]

i finally got ac but i think the recursive function of the DP is

n(a,b,1)=n(a-1,b-1,1)+n(a-1,b-1,0)
n(a,b,0)=n(a-1,b+1,1)+n(a-1,b,0)

a is the number of drawer and b is the secured-num and the 0 or 1 means that the situation of the top drawer.

Finally thank all of you^^

n(a,b,0)=n(a-1,b+1,1)+n(a-1,b,0)
how does this work? here u are increasing b..

[f74956227]

Just by initialize the array qq"

n[j][k]=0;
if(i<j)n[j][k]=0;
f((k==1 && i==j)||(k==1 && j==1))n[j][k]=1;
if(k==1 && j==0)n[j][k]=0;
if(k==0)
{
if(i-j<=1)n[j][k]=0;
else if(i-j==2)n[j][k]=1;
}
}

XDDD..

[shopnobaj_raju]

getting runtime error . please help

Code: Select all

#include<stdio.h>
#include<math.h>


unsigned long long int secureit(int n,int s);
unsigned long long int soln_lck_fst_it(int n,int s);
unsigned long long int secure[100][100];
unsigned long long int soln_lck_fst[100][100];


int main()
{
	int n,s;
	unsigned long long int ans;
	while(1)
	{
		int i,j;
		scanf("%d %d",&n,&s);
		if(n<0 && s<0) break;
		for(i=0;i<100;i++)
			for(j=0;j<100;j++) secure[i][j]=-1;
		for(i=0;i<100;i++)
			for(j=0;j<100;j++) soln_lck_fst[i][j]=-1;
        ans=secureit(n,s);
		printf("%llu\n",ans);
	}
	return 0;
}


unsigned long long int soln_lck_fst_it(int n,int s)
{
	if(s==n || s==n-1) return 1;
	if(n==2 && s==1) return 1;
	if(n==2 && (s==1 || s==2)) return 1;
	if(s>n) return 0;
	if(soln_lck_fst[n][s]!=-1) return soln_lck_fst[n][s];
	if(s==1)
	{
		soln_lck_fst[n][s]=(unsigned long long int) pow(2,n-2) - ((n-2)*(n-3))/2;
		return soln_lck_fst[n][s];
	}
	soln_lck_fst[n][s]=secureit(n-1,s-1);
	return soln_lck_fst[n][s];
}

unsigned long long int secureit(int n,int s)
{

    if(s==n || s==n-1) return 1;
	if(n==2 && s==1) return 1;
	if(n==2 && (s==1 || s==2)) return 1;
	if(s>n) return 0;
	if(secure[n][s]!=-1) return secure[n][s];
	secure[n][s]=soln_lck_fst_it(n,s)+secureit(n-1,s)-soln_lck_fst_it(n-1,s)+soln_lck_fst_it(n-1,s+1);
	return secure[n][s];


}

[brianfry713]

You are assigning -1 to unsigned variables.

[eric7237cire]

While probably obvious to most, just in case.

You need to use 64 bit integers (signed is ok)

[bradd123]

Hi, Can anyone tell me how to improve my solution for this problem.
I used DP top-down But It gives me TLE. Any suggestions please?

Code: Select all

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long int ll;
ll memo[75][75][75];
ll n,s;
ll LockDrawer(ll lst,ll id,ll nlck){
    if(id==n){
        if(nlck==s) return 1;
        else return 0;
    }
    if(memo[lst][id][nlck]!=-1) return memo[lst][id][nlck];
    ll tmp=0;
    if(lst==0){
        tmp=LockDrawer(lst,id+1,nlck)+LockDrawer(1,id+1,nlck);
    }
    else{
        tmp=LockDrawer(lst,id+1,nlck+1)+LockDrawer(0,id+1,nlck);
    }
    return memo[lst][id][nlck]=tmp;
}
int main()
{
    //freopen("in.txt","r",stdin);
    while(scanf("%lld %lld",&n,&s)){
        if(n<0&&s<0) break;
        for(ll i=0;i<66;i++)
            for(ll j=0;j<66;j++)
                for(ll k=0;k<66;k++)
                    memo[i][j][k]=-1;
        if(s>n) printf("0\n");
        else printf("%lld\n",LockDrawer(1,0,0));
    }
}

[brianfry713]

You should be able to solve it without resetting your memo array on every test case.