10305 – Ordering Tasks

Given a set of dependent tasks, find the order in which these tasks have to be executed.

The solution is found via a topological sort.

#include <algorithm>
#include <iostream>
#include <limits>
#include <vector>
#include <queue>
#include <map>
using namespace std;

vector<map<int, int> > graph;
vector<int> sortedNodes;

void topSort() {
	sortedNodes.clear();
	vector<int> inDegree = vector<int>(graph.size(), 0);
	for (size_t i = 0; i < graph.size(); ++i)
		for (map<int, int>::iterator itr = graph[i].begin(); itr != graph[i].end(); ++itr)
			++inDegree[itr->first];
	queue<int> q;
	for (size_t i = 0; i < graph.size(); ++i)
		if (inDegree[i] == 0)
			q.push(i);
	while (q.size()) {
		int p = q.front();
		sortedNodes.push_back(p), q.pop();
		for (map<int, int>::iterator itr = graph[p].begin(); itr != graph[p].end(); ++itr)
			if (!(--inDegree[itr->first]))
				q.push(itr->first);
	}
}

int main() {
	int n, m;
	while (cin >> n >> m && (n || m)) {
		// input
		graph.clear();
		for (int i = 0; i < n; ++i)
			graph.push_back(map<int, int>());
		for (int i = 0, x, y; i < m; ++i)
			cin >> x >> y, --x, --y, graph[x][y] = 1;
		// solve
		topSort();
		cout << (sortedNodes[0] + 1);
		for (int i = 1; i < n; ++i)
			cout << " " << (sortedNodes[i] + 1);
		cout << endl;
	}
	return 0;
}

10986 – Sending email

Given a network of servers and the connections between them with their latency, find the fastest path for sending a message.

A straight-forward path finding problem. Dijkstra will do and Bellman Ford will get TLE.

#include <algorithm>
#include <iostream>
#include <limits>
#include <vector>
#include <queue>
#include <map>
using namespace std;

vector<map<int, int> > graph;

vector<int> dijkstraD, dijkstraP;
void dijkstra(int s) {
	dijkstraD = vector<int>(graph.size(), numeric_limits<int>::max());
	dijkstraP = vector<int>(graph.size(), -1);
	priority_queue<pair<int, int> > q;
	dijkstraP[s] = -s - 1;
	dijkstraD[s] = 0;
	q.push(make_pair(dijkstraD[s], s));
	while (!q.empty()) {
		pair<int, int> p = q.top();
		q.pop();
		if (dijkstraP[p.second] < 0) {
			dijkstraP[p.second] = -dijkstraP[p.second] - 1;
			for (map<int, int>::iterator itr = graph[p.second].begin();
				itr != graph[p.second].end(); ++itr)
				if (dijkstraP[itr->first] < 0
				&& dijkstraD[p.second] + graph[p.second][itr->first] < dijkstraD[itr->first]) {
					dijkstraP[itr->first] = -p.second - 1;
					dijkstraD[itr->first] = dijkstraD[p.second] + graph[p.second][itr->first];
					q.push(pair<int, int>(-dijkstraD[itr->first], itr->first));
				}
		}
	}
}

int main() {
	int N, n, m, s, t;
	cin >> N;
	for (int caseI = 0; caseI < N; ++caseI) {
		// input
		cin >> n >> m >> s >> t;
		graph.clear();
		for (int i = 0; i < n; ++i)
			graph.push_back(map<int, int>());
		for (int i = 0, a, b, w; i < m; ++i)
			cin >> a >> b >> w, graph[a][b] = graph[b][a] = w;
		// solve
		dijkstra(s);
		cout << "Case #" << (caseI + 1) << ": ";
		if (dijkstraD[t] == numeric_limits<int>::max())
			cout << "unreachable";
		else
			cout << dijkstraD[t];
		cout << endl;
	}
	return 0;
}

10088 – Trees on My Island

Given a polygon whose vertices are of integer coordinates (lattice points), count the number of lattice points within that polygon.
Pick’s theoreom states that
Where

• is the number of lattice points in the interior (this is our program’s output).
• is the area of the polygon.
• is the number of lattice points on the exterior.

All the reqired quantities are easily computable, however, needs some extra work. To find the number of lattice points on line segment , we simply calculate .
C++ implementation with rank 329:

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

typedef long long gtype;
typedef complex<gtype> point;
#define x real()
#define y imag()
#define crs(a, b) ( (conj(a) * (b)).y )

long double polArea(vector<point> & p) {
	long double area = 0;
	for (size_t i = 0; i < p.size() - 1; ++i)
		area += crs(p[i], p[i + 1]);
	return abs(area) * 0.5;
}

long long gcd(long long a, long long b) {
	long long t;
	while (b)
		t = b, b = a % b, a = t;
	return a;
}

long long polLatticeB(vector<point> & p) {
	long long b = 0;
	for (size_t i = 1; i < p.size(); ++i)
		b += gcd(abs(p[i].y - p[i - 1].y), abs(p[i].x - p[i - 1].x));
	return b;
}

int main() {
	int n;
	while (cin >> n && n) {
		// polygons
		vector<point> p(n + 1);
		for (int i = 0; i < n; ++i)
			cin >> p[i].x >> p[i].y;
		p[n] = p[0];
		// is convex
		cout << (long long) (polArea(p) - polLatticeB(p) * 0.5l + 1) << endl;
	}
	return 0;
}

259 – Software Allocation

You’re given 10 computers and a set of programs that need to be executed. A computer cannot multitask. Each problem needs to run on a computer of a specific set. Find an assignment of the programs to the computers.

We map the problem to a graph and solve via maximum flow.
We have two layers of nodes; those of the computers and those of the programs. Each computer node is connected to a program node if and only if it can run the program. The source node is connected to all 10 computer nodes and all program nodes are connected to the sink node.
We run Edmond-Karp algorithm and if the maximum flow is less that the number of programs, we can’t find a satisfactory allocation. Otherwise, an allocation is found and can be retrieved by examining the graph.
C++ implementaion with rank 217:

#include <algorithm>
#include <cstring>
#include <cstdio>
#include <limits>
#include <queue>
using namespace std;

#define N 39
int cap[N][N], parent[N], s = 37, t = 38;

bool bfs() {
	queue<int> q;
	q.push(s);
	memset(parent, -1, sizeof parent);
	parent[s] = s;
	while (q.size()) {
		int u = q.front();
		q.pop();
		if (u == t)
			return true;
		for (int v = 0; v < N; ++v)
			if (parent[v] == -1 && cap[u][v] > 0)
				parent[v] = u, q.push(v);
	}
	return false;
}

int maxFlow() {
	int mf = 0, f, v;
	while (bfs()) {
		// min
		v = t;
		f = numeric_limits<int>::max();
		while (parent[v] != v)
			f = min(f, cap[parent[v]][v]), v = parent[v];
		// update
		v = t;
		mf += f;
		while (parent[v] != v)
			cap[parent[v]][v] -= f, cap[v][parent[v]] += f, v = parent[v];
	}
	return mf;
}

int main() {
	char line[1024], *c, nProg = 1, mf;
	while (true) {
		// init
		memset(cap, 0, sizeof cap);
		for (int i = 0; i < 10; ++i)
			cap[i][t] = 1;
		// input
		nProg = 0;
		while (gets(line) && line[0]) {
			nProg += (cap[s][line[0] - 'A' + 10] = line[1] - '0');
			c = &line[3];
			while (*c != ';')
				cap[line[0] - 'A' + 10][*c - '0'] = 1, ++c;
		}
		// output
		if (!nProg)
			break;
		mf = maxFlow();
		if (mf == nProg)
			for (int i = 0; i < 10; ++i) {
				int j;
				for (j = 0; j < 26; ++j)
					if (cap[i][j + 10])
						break;
				printf("%c", j == 26 ? '_' : j + 'A');
			}
		else
			printf("!");
		printf("\n");
	}
	return 0;
}

10801 – Lift Hopping

Given a 100-floor building with a number of elevators that are only allowed to stop at certain floors, find the fastest way to reach a given floor.

We can map the building to a graph. A floor is a node and any two floors that are connected by an elevator are two ends of an edge.Find the shortest path and you’re done. Beware that the graph is bidirectional.

#include <algorithm>
#include <limits>
#include <cstdio>
#include <cstring>
#include <queue>
#include <map>
using namespace std;

vector<map<int, int> > graph;
vector<int> dijkstraD, dijkstraP;

void dijkstra(int s) {
	dijkstraD = vector<int>(graph.size(), numeric_limits<int>::max());
	dijkstraP = vector<int>(graph.size(), -1);
	priority_queue<pair<int, int> > q;
	dijkstraP[s] = -s - 1;
	dijkstraD[s] = 0;
	q.push(make_pair(dijkstraD[s], s));
	while (!q.empty()) {
		pair<int, int> p = q.top();
		q.pop();
		if (dijkstraP[p.second] < 0) {
			dijkstraP[p.second] = -dijkstraP[p.second] - 1;
			for (map<int, int>::iterator itr = graph[p.second].begin();
			itr != graph[p.second].end(); ++itr)
				if (dijkstraP[itr->first] < 0
				&& dijkstraD[p.second] + graph[p.second][itr->first] < dijkstraD[itr->first]) {
					dijkstraP[itr->first] = -p.second - 1;
					dijkstraD[itr->first] = dijkstraD[p.second] + graph[p.second][itr->first];
					q.push(pair<int, int>(-dijkstraD[itr->first], itr->first));
				}
		}
	}
}

int main() {
	int n, k, t[8], K = 100;
	char line[1024], *p;
	while (scanf("%d %d", &n, &k) == 2) {
		// build graph
		graph.clear();
		// nodes
		for (int i = n * K; i > -1; --i)
			graph.push_back(map<int, int>());
		// elevator speed
		for (int i = 0; i < n; ++i)
			scanf("%d", &t[i]);
		// changing elevators cost
		for (int i = 1; i < n; ++i)
			graph[K * (i - 1)][K * i] = graph[K * i][K * (i - 1)] = 0;
		for (int j = 1; j < K; ++j)
			for (int i = 0; i < n; ++i)
				for (int i2 = 0; i2 < n; ++i2)
					if (i != i2)
						graph[K * i + j][K * i2 + j] = 60;
		// elevator stop
		gets(line);
		for (int i = 0; i < n; ++i) {
			int prev, cur;
			gets(line);
			p = strtok(line, " ");
			sscanf(p, "%d", &prev);
			while ((p = strtok(NULL, " "))) {
				sscanf(p, "%d", &cur);
				graph[K * i + prev][K * i + cur] =
				graph[K * i + cur][K * i + prev] =
				t[i] * abs(cur - prev);
				prev = cur;
			}
		}
		//
		int d = numeric_limits<int>::max();
		dijkstra(0);
		for (int i = 0; i < n; ++i)
			d = min(d, dijkstraD[K * i + k]);
		if (d == numeric_limits<int>::max())
			printf("IMPOSSIBLE\n");
		else
			printf("%d\n", d);
	}
	return 0;
}