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

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

11420 - Chest of Drawers

Post by f74956227 » Wed Mar 19, 2008 7:31 am

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?

:o

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Wed Mar 19, 2008 9:19 am

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.

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

Post by emotional blind » Wed Mar 19, 2008 9:34 am

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:

Post by Robert Gerbicz » Wed Mar 19, 2008 11:36 am

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:

Post by f74956227 » Wed Mar 19, 2008 1:07 pm

:D
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^^

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

Post by emotional blind » Wed Mar 19, 2008 2:22 pm

f74956227 wrote::D
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:

Post by f74956227 » Wed Mar 19, 2008 6:00 pm

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

Post by shopnobaj_raju » Mon Jun 11, 2012 6:29 pm

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

Re: 11420 - Chest of Drawers

Post by brianfry713 » Tue Jun 12, 2012 12:29 am

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

Post by eric7237cire » Sat Mar 30, 2013 5:14 pm

While probably obvious to most, just in case.

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

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

11420 - Chest of Drawers

Post by bradd123 » Mon Feb 16, 2015 3:31 pm

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

Re: 11420 - Chest of Drawers

Post by brianfry713 » Tue Feb 17, 2015 3:49 am

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!

Post Reply

Return to “Volume 114 (11400-11499)”