Kruskal’s Algorithm & Quick Union

In my previous post I implemented Prim’s algorithm with pairing heap. Now, here’s another way to find the minimum spanning tree, using Kruskal’s algorithm (Wikipedia) with quick union. If you compare the code between posts, this is a whole lot simpler.

The gist:

  1. For each edge by weight ascending
  2. If nodes are in same component, forget/skip
  3. Else take edge and merge the two components

Here’s my implementation used in the solving of SPOJ 368. Cobbled Streets CSTREET, in git and below:
Continue reading

Kosaraju’s Algorithm

Kosaraju’s algorithm (Wikipedia) finds a graph’s strongly connected components in linear time.

The algorithm runs in two phases:

Phase 1:

  1. grab an unseen node and perform depth-first search.
  2. add node to stack after children processed.
  3. while unseen nodes exist…

Phase 2:

  1. pop node off stack.
  2. graph traversed against directed edges.
  3. all within traversal belong to one strongly-connected component.
  4. while stack is not empty…

This algorithm is used in my solving of SPOJ 13990. Web islands WEBISL; implementation is in git and below:
Continue reading

Red John is Back

This post is in reference to SPOJ 21525. Red John is Back PPBRJB.

You need to build a solid wall that’s 4-high and N-wide using 4×1 bricks. The question: how many distinct walls can you build?

If you place a brick vertically, that takes up one entire column. Placing 4 bricks horizontally takes up four. The solution makes use of the simple dynamic programming recursion shown below:

dp-bricks

Without further ado, my DP implementation is in git and below:
Continue reading

Power the Power Up

This post is in reference to SPOJ 21690. Power the Power Up POWERUP.

How do you solve a^{b^c} (mod m) where m is prime?

Reality check: you can’t just crunch the numbers since this might be 1111111111^1111111111^1111111111.

First, the highest part b^c must be chopped down. Fortunately our answer is taken modulo a prime number. So if we can solve for n where a^n = 1 (mod m), we can safely take b^c (mod n).

E.g. if a^n=1 (mod m), then {a^n} * {a^n} * ... = 1 (mod m); these n exponents disappear.

This is Fermat’s Little Theorem (a.k.a. phi function, totient), giving us n = phi(m) = m - 1 when m is prime.

So, calculate b^c(mod m-1) using modular exponentiation. Then do it again on a with (mod m). This operation is as follows:

typedef unsigned long long uint64;
uint64 modular_pow(uint64 base, uint64 exp, uint64 mod) {
	uint64 result = 1;
	base = base % mod;
	while (exp > 0) {
		if (exp % 2 == 1) {
			result *= base;
			result %= mod;
		}
		exp >>= 1;
		base *= base;
		base %= mod;
	}
	return result;
}

But wait! There’s one loose end: what if we can’t solve a^n = 1 (mod m)? This case too must be handled but I’ll leave that to you.

Curd Producers

This post is in reference to SPOJ Curd Producers CURDPROD.

You have several machines, each producing one item at its own speed. One might produce every 5 seconds, another every 1000.

The question: what is the minimum time required to produce T items?

curdprod

The first calculation required is: how many items were produced by time X? This is a simple O(machines_num) integer division calculation, as follows:

uint64 production(vector<uint32>& machines, uint64 time) {
	uint64 total = 0;
	for (uint32 m_ix = 0; m_ix < machines.size(); m_ix++) {
		total += time / machines[m_ix];
	}
	return total;
}

Also, in the problem the maximum time is limited to 1000000000000000001. So, we have a bounded search space where the result at a given time is easy to calculate. What we've got here is a binary search.

My solution is in git and below:
Continue reading

Eat All the Brownies

This post is in reference to SPOJ 17626. Eat all the brownies CUTCAKE.

The question is: to divide a plane into X pieces, how many lines (cuts) are needed? Magically, the answer is found on page 499 of Knuth’s Concrete Mathematics 2nd Ed. (or p485 in this PDF), and is as follows:

regions = (tabular{000}{00}{cuts 0}) + (tabular{000}{00}{cuts 1}) + (tabular{000}{00}{cuts 2})
(tabular{000}{00}{cuts 0}) = 1
(tabular{000}{00}{cuts 1}) = cuts
(tabular{000}{00}{cuts 2}) = {cuts!}/{(cuts-2)! * {2!}} = {cuts * (cuts - 1)}/2

N.B. (tabular{000}{00}{n k}) is the binomial coefficient function.

So this solves for regions given the number of cuts. But in this problem we’re to solve it the other way around; this is done via binary search.

My solution is in git and here:
Continue reading

The Bridge to Home

This post is in reference to SPOJ 17660 The Bridge to Home WAYHOME.

You have a group of people on one side of a river, and it may only be crossed by a bridge; the bridge can take 1 or 2 at a time. All bridge-crossers must carry the lone flashlight, meaning each trip across must alternate — flashlight goes one way then back. Each person has a given “time to cross”, and two people crossing takes the longest time of the two. What is the minimum time (T) to cross?

e.g. You have times-to-cross of delim{lbrace}{3, 5, 10}{rbrace}. So a solution is as follows:

3 & 10 across = 10
3 back = 3
3 & 5 across = 5
T = 18

The algorithm has several cases as follows:

1. Remaining < = 2: simply cross

2. Remaining == 3: finish up, lo & mid, lo back, lo & hi

3. Remaining > 3: shuttle two highest
lo = lowest
lo2 = 2nd lowest
hi2 = 2nd highest
hi = highest

N.B. Take the best of the two below. Using max below for clarity.

3a. lo chauffeurs hi across, comes back and does the same for hi2: max(lo, hi) + lo + max(lo, hi2) + lo

3b. lo chauffeurs lo2 and lo returns, hi and hi2 cross and lo2 (aha!) returns: max(lo, lo2) + lo + max(hi, hi2) + lo2

My solution is in git and below:
Continue reading