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

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

10566 – Crossed Ladders

The problem is as shown in the figure. Given x, y, c, find d.

We can see that; given the distance between the two buildings d and the lengths of the ladders x & y, we can determisiticly find the hight of the intersection c.
However, we’re given x, y, c and required to find d. Thus, a binary search for d will do.

• We know that 0 <= d <= min(x,y)
• Given (x, y, d), we can find c'.
• If c' > c, we need more d. And vice versa.

#include <iostream>
#include <complex>
#include <limits>
using namespace std;

typedef double gtype;
#define equ(a, b, e) ( abs((a) - (b)) <= (e) )
const gtype epsLen = 10E-6;
typedef complex<gtype> point;
#define x real()
#define y imag()
#define crs(a, b) ( (conj(a) * (b)).y )
#define intrN(a, b, p, q) ( crs((p)-(a),(b)-(a)) * (q) - crs((q)-(a),(b)-(a)) * (p) )
#define intrD(a, b, p, q) ( crs((p)-(a),(b)-(a)) - crs((q)-(a),(b)-(a)) )
#define cosL(a, b, c) ( ((a) * (a) + (b) * (b) - (c) * (c)) / (2 * (a) * (b)) )

gtype getD(gtype x0, gtype y0, gtype d) {
	gtype y1, x1, intrDen;
	y1 = sqrt(y0 * y0 - d * d);
	x1 = sqrt(x0 * x0 - d * d);
	intrDen = intrD(point(0,0), point(d,x1), point(0,y1), point(d,0));
	if (equ(intrDen, 0, epsLen))
		return 0;
	return (intrN(point(0,0), point(d,x1), point(0,y1), point(d,0)) / intrDen).y;
}

int main() {
	cout.precision(3);
	gtype x0, y0, c0;
	while (cin >> x0 >> y0 >> c0) {
		gtype lD = 0, hD = min(x0, y0) + epsLen, mD;
		do {
			mD = (hD + lD) / 2.0;
			if (getD(x0, y0, mD) < c0)
				hD = mD;
			else
				lD = mD;
		} while (hD - lD > epsLen);
		cout << fixed << mD << endl;
	}
	return 0;
}

575 – Skew Binary

An ad-hoc weird number format problem.
The formula for the given format is:

Which we can divide into two steps:


The first term is twice the normal binary conversion to decimal. The second one is just a summation.
Implementation in C++

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

int main() {
	char line[1024];
	unsigned int i;
	unsigned long long out;
	while (scanf("%s", line) == 1) {
		if (strcmp(line, "0") == 0)
			break;
		out = 0;
		// 2 ^ (k + 1)
		for (i = 0; i < strlen(line); ++i, out <<= 1)
			out += (line[i] - '0');
		// -1
		for (i = 0; i < strlen(line); ++i)
			out -= (line[i] - '0');
		// out
		printf("%lld\n", out);
	}
	return 0;
}

Introduction to Binary Trees

Basic Definitions

• Binary Tree
  A binary tree is made of a set of nodes. This set can be empty or it can consist of a node called a root along with two disjoint subtrees.
• Disjoint subtrees
  Trees that have no nodes in common.
• Node
  A node contains a value and links to two (binary) other nodes called children (left and right). These links are called edges. A node also might link to its parent node.
• Descendant node
  Nodes of any subtree are descendants of its root.
• Ancestor node
  A root of a subtree is an ancestor of it’s nodes.
• Path from n₁ to n_k
  The path from n1 to nk is the sequence of nodes n1, n2 ... nk. Where each node ni in the sequence is a parent of node ni + 1 (each node is a parent of the next / going from the top downwards).
• Depth/Level of node M
  The length of the path between the root of the tree R and M. The root node R is at level 0.
• Height of a tree
  More than the depth of the deepest node in the tree by one. height = max(depth) + 1.
• Leaf/External node
  A node that has no children. Has neither right nor left subtree.
  !hasLeft AND !hasRight = !(hasLeft OR hasRight)
• Internal node
  A node that has at least one child. Has a right or a left subtree. Or both. An internal node is the opposite of an external node.
  hasLeft OR hasRight = !(!hasLeft AND !hasRight)
• Full tree
  A binary tree which consists of nodes that must satisfy one of the following conditions:
  • An internal node with two non-empty children.
  • A leaf.

  Each node must have either 0 or 2 children. Uni-child nodes aren’t allowed.

• Complete tree
  A binary tree which in which all the levels are full except the last level. You can think of it as a tree that is filled from left to right level by level.
  You might confuse a complete tree with a full tree. A little mind trick to memorize them is: the word complete is wider than the word full, so is the complete tree — always wider than the full tree–.

Full Binary Theorem

• The number of leaves in a non-empty full binary tree = number of internal nodes + 1
• The number of empty subtrees in a non-empty binary tree = number of nodes in the tree + 1

Proven by mathematical induction.

Traversal

A tree’s nodes are placed in such structure for a reason. We want to process the tree’s nodes — one by one — by visiting them in a certain order.
These ways/orders by which we visit the nodes are called traversals. A traversal on a tree generates a sequence of nodes in which each node appears once and only once. This is called an enumeration.
There are three types of traversal: pre-order, post-order and in-order. They’ll be explained using the following figure.

Imagine you’re starting from the root of the tree and draw a border around the tree parallel to the edges and surrounding each branch as shown.
Whenever you pass through the left of a node, you’re in pre-order. When you are below a node, you’re in in-order. If you are to the right of a node, you’re in post-order.

• Pre-Order

The algorithm goes as follows:

preoreder(node)
	if(node == null)
		return;
	do(node)
	preorder(node.left)
	preorder(node.right)

• In-Order

The algorithm goes as follows:

inoreder(node)
	if(node == null)
		return;
	inorder(node.left)
	do(node)
	inorder(node.right)

• Post-Order

The algorithm goes as follows:

postoreder(node)
	if(node == null)
		return;
	postorder(node.left)
	postorder(node.right)
	do(node)

You can do these traversals simultaneously in a more general manner instead of only one at a time by gluing them together. The procedure should looks like this:

traverse(node)
	if(node == null)
		return;
	doPreOrder(node)
	traverse(node.left)
	doInOrder(node)
	traverse(node.right)
	doPostOrder(node)