TopCoder – SRM570

Div2 – 250

You’re required to count the number of equal-valued pairs in an array. Get the frequency of each value, divide by two and sum that up.

#include<vector>
#include<map>
using namespace std;

class Chopsticks {
public:
	int getmax(vector <int> length);
};
int Chopsticks::getmax(vector <int> length) {
	map<int, int> freq;
	for (int i = 0; i < length.size(); ++i)
		freq[length[i]]++;
	int ans = 0;
	for (map<int, int>::iterator itr = freq.begin(); itr != freq.end(); ++itr)
		ans += itr->second / 2;
	return ans;
}

Div2 – 500

A simple simulation problem. You’re given a list of commands a that you’re required to follow T times. Output the manhattan distance you have travelled. Each command is an integer that determines the distance you have to travel and the rotation you have to do. After following command i, you have travelled a distance of a[i] and rotated an angle of 90 * a[i] to the right.
The naieve solution is acceptable.

#include <vector>
#include <cmath>
using namespace std;
typedef long long int64;

int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };

class RobotHerbDiv2 {
public:
	int getdist(int T, vector<int> a);
};
int RobotHerbDiv2::getdist(int T, vector<int> a) {
	int x = 0, y = 0, d = 0;
	for (int j = 0; j < T; ++j) {
		for (int i = 0; i < a.size(); ++i) {
			x += a[i] * dx[d];
			y += a[i] * dy[d];
			d += a[i], d %= 4;
		}
	}
	return abs(x) + abs(y);
}

Div2 – 1000

Given a tree , count the number of its subtrees (a subtree here is any tree ).
Think of this recursively; If we have a tree rooted at node with children and each child has possible subtrees, we need to find is .

We use this last formula recursively to get the number of possible trees rooted at as a function of its children. If we sum that up on all the nodes in the tree, we have counted all the possible subtrees rooted at any node.

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <map>
using namespace std;

typedef long long int64;

class CentaurCompanyDiv2 {
	vector<map<int, int> > graph;
	long long *dp;
	long long rec(int n);
public:
	long long count(vector<int> a, vector<int> b);
};
long long CentaurCompanyDiv2::rec(int n) {
	if (dp[n])
		return dp[n];
	long long ans = 1;
	for (map<int, int>::iterator itr = graph[n].begin();
				itr != graph[n].end(); ++itr)
		ans *= 1 + rec(itr->first);
	return dp[n] = ans;
}
long long CentaurCompanyDiv2::count(vector<int> a, vector<int> b) {
	graph = vector<map<int, int> >(a.size() + 1);
	for (int i = 0; i <= a.size(); ++i)
		graph[i].clear();
	for (int i = 0; i < a.size(); ++i)
		graph[a[i] - 1][b[i] - 1] = 1;
	dp = (long long *) malloc(graph.size() * sizeof(long long));
	memset(dp, 0, sizeof dp);
	long long ans = 0;
	for (int i = 0; i < graph.size(); ++i)
		ans += rec(i);
	return ans + 1;
}

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;
}

11137 – Ingenuous Cubrency

A Coin Change problem.
C++ top-down solution:

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

typedef long long int64;
#define N 10001
#define C 21

int64 nWay[N][C];
int cube[C];

int64 getNWay(int n, int c) {
	if (n == 0)
		return 1;
	if (c == C)
		return 0;
	if (nWay[n][c] != -1)
		return nWay[n][c];
	for (int i = 0; i * cube[c] <= n; ++i)
		nWay[n][c] += getNWay(n - cube[c] * i, c + 1);
	return ++nWay[n][c];
}

int main() {
	// init
	for (int i = 1; i <= C; ++i)
		cube[i - 1] = i * i * i;
	memset(nWay, -1, sizeof nWay);
	// solve
	int n;
	while (cin >> n)
		cout << getNWay(n, 0) << 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;
}