## 11420 - Chest of Drawers

All about problems in Volume 114. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

f74956227
New poster
Posts: 37
Joined: Sun Jan 27, 2008 1:50 am
Location: Taiwan
Contact:

### 11420 - Chest of Drawers

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
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:
Could you include the name of the problem in the topic?
Yes, I believe this problem is DP.
Last edited by sclo on Wed Mar 19, 2008 11:56 am, edited 1 time in total.

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Contact:

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]
Last edited by emotional blind on Wed Mar 19, 2008 2:20 pm, edited 1 time in total.

Robert Gerbicz
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:
Don't forget that if s>n, then the answer is 0. (There are such tests in the input.)

f74956227
New poster
Posts: 37
Joined: Sun Jan 27, 2008 1:50 am
Location: Taiwan
Contact: 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
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Contact:
f74956227 wrote: 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
New poster
Posts: 37
Joined: Sun Jan 27, 2008 1:50 am
Location: Taiwan
Contact:
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
New poster
Posts: 7
Joined: Wed Oct 19, 2011 5:07 pm

### Re: 11420 - Chest of Drawers

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;
unsigned long long int soln_lck_fst;

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11420 - Chest of Drawers

You are assigning -1 to unsigned variables.
Check input and AC output for thousands of problems on uDebug!

eric7237cire
New poster
Posts: 4
Joined: Sat Mar 30, 2013 4:06 pm

### Re: 11420 - Chest of Drawers

While probably obvious to most, just in case.

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

New poster
Posts: 17
Joined: Thu Jul 03, 2014 11:13 am

### 11420 - Chest of Drawers

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;
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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11420 - Chest of Drawers

You should be able to solve it without resetting your memo array on every test case.
Check input and AC output for thousands of problems on uDebug!