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

SRM453.5 – MazeMaker

A graph breadth-first-search problem.
Since Jim is smart, he’ll always find the shortest bfs path to every cell. So, what we’ll do is find the cell with the maximum distance and place the exit there.
Caution!

• Input maze isn’t always a square.

C++ implementation:

#include <string>
#include <vector>
#include <queue>
using namespace std;

#define PUSH(x, y, d) if (x > -1 && y > -1  && y < (*maze).size() && x < (*maze)[y].size()&& \
		(*maze)[y][x] == '.') { q.push((x) | ((y) << 8) | ((d) << 16)); (*maze)[y][x] = 'X'; }
#define N 64

class MazeMaker {
	int maxD;
	vector<string> *maze;
	vector<int> *dX, *dY;
	void bfs(int sX, int sY) {
		queue<int> q;
		PUSH(sX, sY, 0);
		while (q.size()) {
			int x = q.front() & 0xFF, y = (q.front() >> 8) & 0xFF, d = q.front() >> 16;
			maxD = max(d, maxD);
			q.pop();
			for (int i = 0; i < (*dX).size(); ++i)
				PUSH(x + (*dX)[i], y + (*dY)[i], d + 1);
		}
	}
public:
	int longestPath(vector<string> maze, int sX, int sY, vector<int> dX, vector<int> dY) {
		this->maze = &maze;
		this->dX = &dY;
		this->dY = &dX;
		this->maxD = -1;
		bfs(sY, sX);
		for (int i = 0; i < maze.size(); ++i)
			for (int j = 0; j < maze[i].size(); ++j)
				if (maze[i][j] == '.' && (maxD = -1))
					break;
		return maxD;
	}
};