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

11516 – WiFi

Given a street (a straigt line), a set of houses (points on that line) and a number of wireless access points (not placed yet), find the minimum range required for the access points to cover all the houses.

A binary search solution:

• Given the houses’ positions and the ranges, we can find the required number of access points n'. It’s correct to calculate this using some greedy algorithm.
• If n' < n (we have extra access points), decrease the range. Otherwise, increase the range.

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
using namespace std;

const double eps = 10E-4;
vector<int> house;

int nPointReq(double d) {
	int n = 1;
	double covered = house[0] + d;
	for (size_t i = 0; i < house.size(); ++i)
		if (house[i] > covered)
			covered = house[i] + d, ++n;
	return n;
}

int main() {
	int nCase, nPoint, nHouse;
	cin >> nCase;
	cout.precision(1);
	while (nCase--) {
		// input
		cin >> nPoint >> nHouse;
		house.clear();
		for (int i = 0, d; i < nHouse; ++i)
			cin >> d, house.push_back(d);
		sort(house.begin(), house.end());
		// solve
		double lD = 0, mD, hD = house[house.size() - 1];
		do {
			mD = (hD + lD) / 2.0;
			if (nPointReq(mD) > nPoint)
				lD = mD;
			else
				hD = mD;
		} while (hD - lD > eps);
		cout << fixed << (round(mD * 10) / 20.0) << 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;
}

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

11935 – Through the Desert

Given the discription of a road, find the minimum amount of fuel you need to finish the journey.

A binary search solution; given a fuel amount, simulate the journey and find whether you can reach the end. If you can, try to use less fuel. Otherwise, more fuel.

#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
using namespace std;

#define pos first
#define type second[0]
#define fuel second[1]

const double eps = 10E-6;
vector<pair<int, string> > road;

double journeySuccess(double v) {
	double g = v, c = 0, l = 0, prevPos = 0;
	for (size_t i = 0; i < road.size(); ++i) {
		g -= (road[i].pos - prevPos) * (l + c / 100.0);
		if (i < road.size() - 1)
			switch (road[i].type) {
				case 'F': c = road[i].fuel; break;
				case 'L': ++l; break;
				case 'G': g = (g >= 0 ? v : g); break;
				case 'M': l = 0; break;
				default: break;
			}
		prevPos = road[i].pos;
	}
	return g;
}

int main() {
	int p, t = 1, nLeak, maxT;
	string s;
	ostringstream e;
	cout.precision(3);
	while (true) {
		// input
		road.clear();
		maxT = nLeak = 0;
		do {
			cin >> p >> s, e.str(""), e << s[0];
			if (s[0] == 'L')
				++nLeak;
			if (s[0] == 'G' && s[1] == 'a')
				cin >> s;
			if (s[0] == 'F' && cin >> s >> t)
				e << (char) t, maxT = max(maxT, t);
			if (!t && !road.size())
				return 0;
			road.push_back(make_pair(p, string(e.str())));
		} while (s[0] != 'G' || s[1] != 'o');
		// solve
		double lV = 0, mV, hV = p * (maxT / 100.0 + nLeak), j;
		do {
			mV = (hV + lV) / 2;
			if ((j = journeySuccess(mV)) > 0)
				hV = mV;
			else
				lV = mV;
		} while (hV - lV > eps || j < 0);
		cout << fixed << ((hV + lV) / 2) << endl;
	}
	return 0;
}