Dancing Links

Here is a demonstration of the Dancing Links idea (Wikipedia definition).

The idea is this: if you remove an item from a doubly-linked list, you can put it right back in O(1) as long as you hold on to it. And, if you remove items A B C, you can put them right back as long as you reverse the order exactly, C B A.

This is done as follows:

// Remove: `curr` is forgotten by neighbors
curr->prev->next = curr->next;
curr->next->prev = curr->prev;

// Reinsert: 'curr' knows where to go, and steps right back in!
curr->next->prev = curr;
curr->prev->next = curr;

// Works over and over, as long as it's done in stack order:
// remove=push, reinsert=pop.
dancing_link_remove(A);
  dancing_link_remove(B);
  dancing_link_reinsert(B)
  dancing_link_remove(C);
  dancing_link_reinsert(C)
dancing_link_reinsert(A)

This works well where you’re drilling in to search but need to backtrack too — you can do so without the need to work with multiple copies.

And finally, this is demonstrated in git and as follows:
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

Palindrome

This post is in reference to CodeForces Palindrome.

The question is: given a string, can you find the longest palindrome sub-sequence?

N.B. A sub-sequence of a string is what remains after removing any characters you’d like, keeping the order unchanged. Sub-sequences of abcd are acd, bd, abcd, d, etc. The following are not: acb, da, abcde, dcba.

The solution uses dynamic programming on a 2D vector, with input string along both the top and side. The number of cells is input.size * input.size.

Grid[row][col] means “longest sub-sequence within input sub-string [col…row]”. The grid is calculated from top to bottom, each row from right to left.

Example input = abbca
subseqpal

Explanations:

N.B. LCPal is Longest Common Sub-Sequence Palindrome

1. LCPal of “a” is “a
2. LCPal of “b” is “b
3. LCPal of “ab” is “a” (taken from row above)
4. LCPal of “bb” is “bb” (take the match plus row/column above/beside, which is empty)
5. LCPal of “abb” is “bb” (taken from column beside)
6. LCPal of “bbc” is “bb” (taken from row above)
7. LCPal of “abbca” is “abba” (take the match plus row/column above/beside), and that’s the final answer

And an implementation note: because each row only requires the previous, I don’t keep all rows in memory — just two.

My solution is in git and below:
Continue reading

Stadium and Games

This post is in reference to CodeForces Stadium and Games.

Let’s look at a subset of inputs, and see what shakes out.

N.B. From problem description

– Phase 1: total of halves removed
– Phase 2 input: number of teams minus phase one
– Phase 2 output: phase-2-input * ( phase-2-input — 1 )/2

x (binary)  phase-1 phase-2-input
1 (1b)      =  0       1
3 (11b)     =  0       3
5 (101b)    =  0       5
7 (111b)    =  0       7
9 (1001b)   =  0       9
11 (1111b)  =  0       11

x (binary)  phase-1 phase-2-input
2 (10b)     =  1       1
6 (110b)    =  3       3
10 (1010b)  =  5       5
14 (1110b)  =  7       7
18 (10010b) =  9       9
22 (11110b) =  11      11

...

x (binary)  phase-1 phase-2-input
8 (1000b)     =  7       1
24 (11000b)   =  21      3
40 (101000b)  =  35      5
56 (111000b)  =  49      7
72 (1001000b) =  63      9
88 (1111000b) =  77      11

First, notice the phase-2-input in each case: it’s strictly increasing. And phase-2-output (on this strictly increasing input) is strictly increasing. And phase 1 is strictly increasing too. Therefore, it’s safe to say that the total result on any series of inputs having the same number of ending-zeroes is strictly increasing.

This means we can perform a binary search on each group of partitioned inputs, for the given result. So, explicitly:

– Series 0: 1, 3, 5, 7… with no zeroes attached to the back
– Series 1: 1, 3, 5, 7… with 1 zero attached (yielding 2, 6, 10…)
– Series 2: 1, 3, 5, 7… with 2 zeroes attached
– etc.

Also notice that any number is part of exactly one series: if it ends in 1 zero it’s in series 1, ends in 14 zeroes it’s in series 14, etc. Therefore, all possible answers are searched.

(Also, notice the phase-1 to phase-2-input ratio in each series is the same. This is useful during implementation.)

With that, here it 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