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

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