UVa 11420

From Algorithmist
Jump to navigation Jump to search

11420 - Chest of Drawers[edit]

Summary[edit]

A chest of drawers means a wardrobe which has many drawers aligned vertically. A drawer is secure only if it is locked and either it is the topmost drawer of the chest or the drawer just above it is also locked. There are n drawers and exactly s drawers are secure. How many such arrangements of drawers is possible?

Explanation[edit]

This is a Dynamic Programming Problem. Let dp(n,s,x) be the number of ways s drawers can me made secure out of the n drawers where the drawer just above these n drawers is locked if x = 1 and unlocked if x = 0. We consider our two options for the current topmost drawer (lock it or unlock it) and reduce this n sized problem to n-1 sized problem.

General Cases: If the drawer just above these n drawers is unlocked (x = 0), the current topmost drawer cannot be made secure whether we lock it or not. If we lock it dp(n,s,0) reduces to dp(n-1,s,1). If we keep it unlocked dp(n,s,0) reduces to dp(n-1,s,0). If the drawer is the topmost drawer or the drawer just above these n drawers is locked (x = 1), the current topmost drawer can be made secure only if it is locked. If we lock it, the current topmost drawer is secured and dp(n,s,0) reduces to dp(n-1,s-1,1). If we keep it unlocked dp(n,s,0) reduces to dp(n-1,s,0).

dp(n,s,0) = dp(n-1, s, 1) + dp(n-1,s,0)

dp(n,s,1) = dp(n-1,s-1,1) + dp(n-1,s,0)

Base Cases: When n = 1 (only one drawer),

  • s = 1 and x = 0 ---- 1 of 1 drawer needs to be secured and the drawer above it is unlocked, so no possible way to secure the drawer (return 0)
  • s = 1 and x = 1 ---- 1 of 1 drawer needs to be secured and the drawer above it is locked, only possible way to secure the drawer is to lock it (return 1)
  • s = 0 and x = 1 ---- 0 of 1 drawer needs to be secured and the drawer above it is locked, only possible way to make the drawer insecure is to keep the drawer unlocked (return 1)
  • s = 0 and x = 0 ---- 0 of 1 drawer needs to be secured and the drawer above it is unlocked, we can either lock the drawer or keep it unlocked, the drawer will not be secured (return 2)
  • Any time s > n, that is, number of drawer that needs to be secured exceeds the number of drawers, there is no possible way (return 0)
  • Any time s = n and x = 0, that is, number of drawer that needs to be secured equals the number of drawers and the drawer above these n drawer is unlocked, there is no possible way (return 0)

Gotchas[edit]

  • Use long long int

C++ Implementation[edit]

#include<cstdio>
#include<cstring>
using namespace std;

typedef long long int L;
L arr[66][66][2];

L dp(int n, int s, int x)
{
	if(n == 1)
	{
		if(s == 0 && x == 1)
			return 1;
		if(s == 0 && x == 0)
			return 2;
		if(s == 1 && x == 1)
			return 1;
		return 0;
	}		
	if(n < s)
		return 0;
	if(n == s && x == 0)
		return 0;
	if(arr[n][s][x] != -1)
		return arr[n][s][x];
	if(x)
		arr[n][s][x] =  dp(n-1,s-1,1) + dp(n-1,s,0);
	else
		arr[n][s][x] =  dp(n-1,s,1) + dp(n-1,s,0);
	return arr[n][s][x];	
}
main()
{
	memset(arr, -1, sizeof(arr));
	int n,s;
	while(1)
	{
		scanf("%d %d", &n, &s);
		if(n<0 && s<0)
			break;
		printf("%lld\n", dp(n,s, 1));  
	}
}

Input[edit]

6 2
6 3
6 4
65 65
5 6
65 30
-1 -1

Output[edit]

16
9
6
1
0
64310620249541505