11420 - Chest of Drawers
Moderator: Board moderators
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?
Could you include the name of the problem in the topic?
Yes, I believe this problem is DP.
Yes, I believe this problem is DP.
Last edited by sclo on Wed Mar 19, 2008 11:56 am, edited 1 time in total.
-
- A great helper
- Posts: 383
- Joined: Mon Oct 18, 2004 8:25 am
- Location: Bangladesh
- 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
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.
-
- Experienced poster
- Posts: 196
- Joined: Wed May 02, 2007 10:12 pm
- Location: Hungary, Pest county, Halasztelek
- Contact:
-
- A great helper
- Posts: 383
- Joined: Mon Oct 18, 2004 8:25 am
- Location: Bangladesh
- Contact:
n(a,b,0)=n(a-1,b+1,1)+n(a-1,b,0)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^^
how does this work? here u are increasing b..
-
- 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[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];
}
-
- 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!
-
- 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)
You need to use 64 bit integers (signed is ok)
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?
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));
}
}
-
- 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!