This was used in my solving of SPOJ 11110. Easy Longest Increasing Subsequence ELIS and is in git and below:

Continue reading

# Tag Archives: spoj

# Kruskal’s Algorithm & Quick Union

**The gist:**

- For each edge by weight ascending
- If nodes are in same component, forget/skip
- 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

# Prim’s Algorithm & Pairing Heap

My implementation is used to solve SPOJ 3188. Minimum Spanning Tree MST, and is in git and below:

Continue reading

# Kosaraju’s Algorithm

The algorithm runs in two phases:

**Phase 1:**

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

**Phase 2:**

- pop node off stack.
- graph traversed against directed edges.
- all within traversal belong to one strongly-connected component.
- 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

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:

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

Continue reading

# Power the Power Up

How do you solve where is prime?

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

First, the highest part must be chopped down. Fortunately our answer is taken modulo a prime number. So if we can solve for where , we can safely take .

E.g. if , then ; these exponents disappear.

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

So, calculate using modular exponentiation. Then do it again on with . 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 ? This case too must be handled but I’ll leave that to you.

# Curd Producers

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?**

The first calculation required is: how many items were produced by time X? This is a simple 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 . 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

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:

N.B. 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

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 . So a solution is as follows:

across = 10

back = 3

across = 5

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 below for clarity.

**3a.** chauffeurs across, comes back and does the same for :

**3b.** chauffeurs and returns, and cross and (aha!) returns:

My solution is in git and below:

Continue reading

# Closest Triplet

Given a set of N points, find the triplet with minimum sum of (3) distances. (Another way: find points forming a triangle with minimum perimeter.)

My solution uses this closest-pair algorithm (PDF), modified to suit. So, if you want to understand, that PDF is where you should really dig in.

My solution is in git and below:

Continue reading