11420 – Chest of Drawers

A Dynamic Programming combinatorics problem.
You start placing the drawers one by one and each time you decide between locked and unlocked. During this process, keep track of the number of drawers placed so far and the number of secure ones. If both reach your target, count that as one solution. The DP solution:

• State S(n, s, l) – n is number of drawers waiting to be placed, s number of secured drawers required and l whether the previous drawer is locked.
• Transition S(n, s, l) = S(n - 1, s - l, true) + S(n - 1, s, false) – You can place a locked drawer which decreases the number of required secured drawers, if and only if the previous drawer is locked. Placing an unlocked drawer only decreases the number of remaining drawers.

Caution!

• long long isn’t enough!

C++ top-down implementation:

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

#define N 128

unsigned long long nWays[N][N][2];

unsigned long long getNWays(int n, int s, bool l) {
	if (n == 0 && s == 0)
		return nWays[n][s][l] = 1;
	if (s > n || n < 0 || s < 0)
		return 0;
	if (nWays[n][s][l] != -1)
		return nWays[n][s][l];
	return nWays[n][s][l] = getNWays(n - 1, s - l, true) + getNWays(n - 1, s, false);
}

int main() {
	memset(nWays, -1, sizeof nWays);
	int n, s;
	while (cin >> n >> s && n >= 0 && s >= 0)
		cout << getNWays(n, s, true) << endl;
	return 0;
}

118D – Caesar’s Legions

A Dynamic Programming problem.
You’re trying to find the number of permutations of footmen/horsemen that match the given criterion. While you’re permuting, some problems are revisited. That’s when DP comes in handy:

• State S(n1, n2, k1, k2) – You’ve placed n1 footmen and n2 horsemen. The previous soldier is either a part of k1 consecutive footmen or k2 consecutive horsemen.
• Transition S(n1, n2, k1, k2) = S(n1 + 1, n2, k1 + 1, 0) + S(n1, n2 + 1, 0, k2 + 1) – You can either place a footman — which increases the number of consecutive footmen by one and resets the number of consecutive horsemen k2 — or a horseman.

Caution!

• Don’t forget the modulo 10⁸.

C++ implementation but with values decreasing instead of increasing:

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

#define N 128
#define K 16
#define M 100000000

int nWays[N][N][K][K];
int N1, N2, K1, K2;

long long getNWays(int n1, int n2, int k1, int k2) {
	if (n1 < 0 || n2 < 0 || k1 < 0 || k2 < 0)
		return 0;
	if(n1 == 0 && n2 == 0)
		return 1;
	if (nWays[n1][n2][k1][k2] != -1)
		return nWays[n1][n2][k1][k2];
	return nWays[n1][n2][k1][k2] =
			(getNWays(n1 - 1, n2, k1 - 1, K2) + getNWays(n1, n2 - 1, K1, k2 - 1)) % M;
}

int main() {
	memset(nWays, -1, sizeof nWays);
	cin >> N1 >> N2 >> K1 >> K2;
	cout << getNWays(N1, N2, K1, K2) << endl;
	return 0;
}

10684 – The jackpot

A 1D array maximum sub-array problem.
The solution is Dynamic Programming. This maximum sub-array technique is also known as Kadane’s Algorithm.
C++ implementation:

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
	long n, e, sum, maxSum;
	while (cin >> n && n) {
		sum = maxSum = 0;
		while (n--) {
			cin >> e;
			sum += e;
			if (sum < 0)
				sum = 0;
			maxSum = max(maxSum, sum);
		}
		if (maxSum > 0)
			cout << "The maximum winning streak is " << maxSum << ".";
		else
			cout << "Losing streak.";
		cout << endl;
	}
	return 0;
}

1213 – Sum of Different Primes

A Dynamic Programming problem.
Simply, you combine primes — which you generated one way or another — that add up to the input. This combination should be executed via Dynamic Programming. Your state consists of:

• n – the number that needs decomposition.
• k – the number of primes n should be divided into.
• i – the lowest prime number that can be used in the next decomposition. This is to avoid repeated primes in the sum.

Your transitions from S(n, k, i) are:

• S(n – prime[i], k – 1, i + 1) – subtract the current prime.
• S(n, k, i + 1) – bypass it.

C++ implementation:

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

#define N 2048
#define P 309
#define K 16

long long nWays[N][K][P], prime[P];

void sieve() {
	int nPrime = 0, isPrime[N];
	memset(isPrime, true, sizeof isPrime);
	isPrime[0] = isPrime[1] = true;
	for (int i = 2; i < N; ++i)
		if (isPrime[i] && (prime[nPrime++] = i))
			for (int j = i * i; j < N; j += i)
				isPrime[j] = false;
}

long long getNWays(int n, int k, int i) {
	if (n == 0 && k == 0)
		return 1;
	if (n < 0 || k < 0 || prime[i] > n || i == P)
		return 0;
	if (nWays[n][k][i] != -1)
		return nWays[n][k][i];
	return nWays[n][k][i] = getNWays(n - prime[i], k - 1, i + 1) + getNWays(n, k, i + 1);
}

int main() {
	// init
	sieve();
	memset(nWays, -1, sizeof nWays);
	// solve
	int n, k;
	while (cin >> n >> k && (n || k))
		cout << getNWays(n, k, 0) << endl;
	return 0;
}

10130 – SuperSale

A 0/1-Knapsack problem.
Apply the 0/1-Knapsack for each family member given the weight they can carry and sum the maximum up.
I added a little detail but it doesn’t make much of a difference. I sort the items according to their weights and start from light items until I reach an item I can’t add. Items heavier than that last item are, of course, no use so we return from there and stop the recursion.
C++ implementation:

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

#define N 1004
#define G 104
#define W 34
#define weight first
#define price second

int dp[N][W];
pair<int, int> item[N];

bool cmp(pair<int, int> p1, pair<int, int> p2) {
	return p1.weight > p2.weight;
}

int getMax(int n, int w) {
	if (n < 0)
		return 0;
	if (dp[n][w] != -1)
		return dp[n][w];
	if (w < item[n].weight)
		return dp[n][w] = 0;
	else
		return dp[n][w] = max(getMax(n - 1, w - item[n].weight) + item[n].price, getMax(n - 1, w));
}

int main() {
	int totT, totN, totG;
	cin >> totT;
	for (int i = 0; i < totT; ++i) {
		// input
		cin >> totN;
		for (int j = 0; j < totN; ++j)
			cin >> item[j].price >> item[j].weight;
		memset(dp, -1, sizeof dp);
		sort(item, item + totN, cmp);
		cin >> totG;
		// solve
		int sum = 0;
		for (int j = 0, w; j < totG; ++j) {
			cin >> w;
			sum += getMax(totN - 1, w);
		}
		cout << sum << endl;
	}
	return 0;
}