Browse Category

Algorithms

Playing with Blocks (Hotseat: British Informatics Olympiad R1, 2015)

Second in a series. I apologise for the temporary hiatus, had a couple of weeks travelling and then intense sessions at work (part of this was my choice, but still).

Background

I was not in the UK for high school, and studying computing/informatics wasn’t common in my high school in Singapore either. I never actually participated in the British Informatics Olympiad. This is the UK’s national high-school competition in computing, and unlike normal programming contests there’s an explicit portion involving reasoning and discrete mathematics which I like. This can get intense; problems especially in the second round can feature fairly complex reasoning – such as 2009’s second round which required understanding models of computation in FRACTRAN (and eventually deciphering a “program” that computed the Fibonacci series). For quite a few contest problems, intuitively determining a solution, or even being uncertain but firing it off anyway in hopes of getting it accepted is much easier than trying to prove that the solution is correct.

The first round is somewhat less intense, but still has plenty of opportunities for interesting problems. There are typically three tasks; the first is gentle and meant to be a warm-up, the second tests implementation (perhaps more like what I might expect on a programming exam in university) and the third tests algorithms (in a sense, more like a standard contest problem). Each question has most of the points (about 75%) allocated to implementation and the remainder to several “reasoning” questions. Partial scores are awarded for solutions that aren’t optimal or fail on some cases (much like in the IOI, though the information is not known to the students).

This was one of the easier papers I’ve done; I worked my way through the tasks very quickly, and didn’t have too much of a problem (other than a careless error in problem 2). Most of the time I score above 90 points on these, though sometimes if I don’t “get” problem 3 in an optimal way or make subtle errors on problem 2 the score will be a fair bit lower.

The specific paper I did is here.

Problem 1: Block Palindromes

Given a string, find the number of ways of decomposing it into at least two blocks such that when the blocks are reversed (but not the letters within the blocks), the arrangement of blocks looks the same. For example, BARBAR is a block palindrome, since (BAR)(BAR) reads the same forwards and backwards. Of course, every ordinary palindrome is also a block palindrome, since taking one-letter blocks is allowed.

Not too much here; the problem is readily amenable to a simple recursive implementation (try taking each block length from 1 to half the string length and see if the string ends with that prefix – if so, recurse and add that result to our total). It would be possible to use memoisation to improve performance here, since there can be repeated subproblems e.g. with AABCBAA, you would be solving for the number of solutions to BCB twice. However, given the small constraints (strings of up to 10 characters) this wasn’t needed.

This problem probably had one of the trickier reasoning questions though – if all groupings of a block palindrome contain an even number of blocks, how many groupings can there be (and why)?

I attacked this one with a proof by contradiction – that it is not possible to have any groupings

S = B_1 B_2 \ldots B_{n-1} B_n B_{n-1} \ldots B_2 B_1

for n \geq 2. This can be shown by construction:

S' = (B_1) (B_2 \ldots B_{n-1} B_n B_{n-1} \ldots B_2) (B_1)

is a valid decomposition, which has three blocks. Of course, the empty string isn’t a valid block, so we require S = B_1 B_1 and the number of groupings has to be 1. We can probably formulate an even stronger condition (for instance, that apart from B_1 itself, no prefix of B_1 is also a suffix of B_1). While the reasoning seemed sound to me, I wasn’t too confident I had the right answer here.

(Note: The question text implied that a block palindrome could be decomposed into blocks in some way, so while 0 satisfies “all groupings” it wouldn’t be a block palindrome.)

Problem 2: Battleships

Given a funky (deterministic) algorithm for generating random numbers, implement it, and use it to fill a grid with ships of certain sizes via some kind of rejection sampling. The key constraints are that the grid has a finite size, and more interestingly ships are not allowed to touch (even diagonally).

Implementing the random-generator is pretty much following instructions from the spec. However, there are several ways to implement the latter constraint. Given that optimality is generally not important in problem 2, I went for a rather nasty solution that, say, for a k-ship placed horizontally would iterate through a 3 \times (k + 2) bounding rectangle around the ship and mark all those squares as unusable. Better asymptotic complexity can probably be obtained using an R-tree (though that is probably not reasonable for contests – especially without a reference!).

There was a rather nasty “reasoning” problem about the number of ways to place ships of size 4, 3, 2 and 1 on a 5 by 5 grid – this was also where I lost the five points. I hacked my implementation to, instead of using the random number generator, simply use backtracking to count the number of possible placements. However, I forgot that my bounding rectangle system was based on booleans (in other words, a square that was unusable because of two different ships would suddenly become usable after just one was removed), and thus came up with the impressive total of 427,840 possibilities (correct answer: 1,424)!

I subsequently fixed the aforementioned bug (using integers instead) and confirmed that the answer was indeed 1,424. During the test I did try smoke-tests that verified that a 1-ship could be placed in 25 ways and a 5-ship in 10; I attempted to do two 1-ships, but decided that I would have had too much pain working through the combinatorics for that.

Problem 3: Modern Art

This problem revolved around (reasonably) efficiently determining the ith permutation of a string in terms of lexicographic ordering, possibly involving duplicate characters. For example, in a string which consists of five As, Bs, Cs and Ds – what is the 11,223,344,556th permutation?

Of course, for smaller strings and smaller numbers it would suffice to implement some kind of next-permutation generator. This is a pretty standard algorithm. We can then step through the permutations until we get what we want – and there are some test cases that would be solvable with this; you would get (I think) 11 of the 25 points available.

The key idea is that we don’t want to explore all of the permutations. From combinatorics, we can quickly calculate the number of permutations of five As, Bs, Cs and Ds:

\displaystyle {20 \choose 5} \times {15 \choose 5} \times {10 \choose 5} \times {5 \choose 5} = 11,732,745,024

Intuitively, we are close to the “end”; we can thus be pretty sure that our 11-millionth permutation should start with a D. We can thus write a recursive (or iterative) algorithm that identifies the first character based on this search.

I began by implementing a function that computes the number of ways of permuting a given number of As, Bs, Cs and Ds. This was done in a bit of a hacky way and has some (probably unnecessary) memoisation.

private static long numPerms(long as, long bs, long cs, long ds) {
  List<Long> longs = Lists.newArrayList(as, bs, cs, ds);
  Collections.sort(longs);
  if (cache.contains(longs)) {
    return cache.get(longs);
  }
  long totalChars = as + bs + cs + ds;
  long perms = 1L;

  // Computes (total C l) then updates total
  for (Long l : longs) {
    long num = 1;
    long denom = 1;
    for (int i = 0; i < l; i++) {
      num *= totalChars - i;
      denom *= i + 1;
    }
    perms *= num / denom;
    totalChars -= l;
  }

  cache.put(longs, perms);
  return perms;
}

Interestingly, it turns out it would actually have been okay to build the entire numerator and denominator and then divide the two; perhaps 20 was chosen to avoid complications with overflow (since 21! will exceed the max value of a 64 bit integer). Anyway, the highest value the numerator could have taken on here was 1,860,480 (20 to 16 multiplied together) so I was sure I was safe this way.

We then go through the characters in lexicographic order, and for each one, consider the number of permutations that would be feasible. The general approach is something like this:

private static String getPermutation(long as, long bs, long cs, long ds, long offset) {
  if (as == 0 && bs == 0 && cs == 0 && ds == 0) {
    return ""; // we've built the entire thing
  }

  long permsCovered = as == 0 ? 0 : numPerms(as - 1, bs, cs, ds);
  if (offset < permsCovered) {
    return "A" + getPermutation(as - 1, bs, cs, ds, offset);
  }
  long permsPassed = permsCovered;
  permsCovered += bs == 0 ? 0 : numPerms(as, bs - 1, cs, ds);
  if (offset < permsCovered) {
    return "B" + getPermutation(as, bs - 1, cs, ds, offset - permsPassed);
  }
  permsPassed = permsCovered;
  permsCovered += cs == 0 ? 0 : numParams(as, bs, cs - 1, ds);
  if (offset < permsCovered) {
    return "C" + getPermutation(as, bs, cs - 1, ds, offset - permsPassed);
  }
  // and the same for D.
}

I actually finished the implementation fairly quickly, but decided to write a couple of tests; I stepped through the 12 permutations of “ABBC” as given in the spec, and also wrote a test for “AAABBBCCCDDD” that all the permutations were generated in the correct order (using numPerms to give me the range). I also of course tried a couple of edge-ish cases such as each of “A”, “B”, “C” and “D”, and a test to verify we could handle the expected scale (five of each character, retrieving the 1st as well as 11732745024th permutation).

The “reasoning” problems on this one were very easy compared to the other two questions.

Conclusion

Unfortunately meta-analysis is somewhat limited here as unlike the AIME results, the ones for the BIO aren’t public. I’m pretty sure 95 is a solid score as the contest isn’t that easy, but I won’t be surprised if there are multiple 100s (with a bit of caution I could have gotten one)!

Style during programming contests is an interesting issue. I find that many contestants especially with C++ like to use rather bespoke preprocessor routines (e.g. cin as f, cout as g). I’m actually used to some of them as well e.g. ll for long long, vpll for vector<pair<long, long>>. If one understands these it’s probably better for speed, though when debugging I find having not-unreasonable names is preferable (even if my code is written more for speed than style).

Odd Sums Sudoku

The puzzle above is from the WPF Sudoku GP, Round 4 2016 #13. To solve it, each row, column and marked 3×3 box must contain the digits 1 to 9 once each, and the solution must have, in the marked rows, maximal odd substrings summing to the given totals in the correct order.

I’ve always enjoyed a good puzzle, though I’ve never considered myself especially good at them. That said, I’ve done my fair share of sudoku, including several books where puzzles were labelled as very difficult; yet, fairly often identifying triples, or the odd X-wing, XY-wing or unique rectangle would be sufficient to blow through the puzzles. At least, I thought that clearing some “very difficult” puzzles in 8 or 10 minutes was blowing through them; I found the World Puzzle Federation’s Sudoku GP, where some of these had benchmark times along the lines of 3-4 minutes!

Furthermore, in addition to your standard “classic” puzzles which feature the standard rules (i.e. each row, column and marked 3×3 box must contain the digits from 1 to 9 once each), there are a couple of interesting variants that require understanding new rulesets and figuring out how to deal with them. After a while, as mentioned the classic puzzles largely tend to be solved with standard techniques, and the challenge there is dispatching them with extreme speed; the variants, on the other hand, tend to maintain some degree of freshness (at least as far as I’m concerned).

The above puzzle was an example of this; several of the rows are marked with additional clues, and for these rows, the largest odd substrings in the row must sum to the values indicated by the clues. For example, if a row was 178356924, the clue associated with it would be 8, 8, 9. Note that this is also generated by several other valid sequences, such as 532174689 or 174283569.

For the above puzzle, the 9, 5, 3, 8 clue is a good starting point, and indicates that we have 9, 5, 3 and (17 or 71) as substrings of the solution to that row in some order; given the position of 6, we can conclude that the 9 and the 3 must occur before the 6 (though we don’t know). We thus have 9 in the bottom left hand corner, an even number (either 2 or 4), and then a 3. Now, reading the first column clue 1, 12, 3, 9; we have 1, (57 or 75), 3 and 9 as substrings. The 9 is at the end, and 3 cannot occur before the 4 as there’s no space to fit it. Thus 3 occurs after the 4, but it has to be separated from the 9 by an even number. More simply, the second column clue 10, 9, 6 indicates that our 5 has to be preceded by an even number and then a 1. There’s only one spot left for a 7 in this lower box, so we can insert it.

We thus reach this position:

Moving on, we can consider the middle column. 3 can only be satisfied by a singular 3, so we know that the 3 in the bottom row cannot be in the middle column. It thus must be in the sixth column, with 1 and 7 taking up the eighth and ninth columns (in some order).

Now consider the rightmost column. It is 3, 10, 12; 3 can only be satisfied by a singular 3, so the odd substrings must be 3, (19 or 91) and (57 or 75). Given the position of the 2 (fourth row), it must be the case that the column has 1 and 9 in the fifth and sixth rows, an even number in the seventh, and 5 and 7 in the eighth and ninth. We thus clearly have 7 in the corner, and 5 above it.

Finally, we can actually decide on the ordering of 1 and 9 as well; consider the hint for the middle row, which ends with 8; a 9 would automatically exceed this. Thus the middle row must contain the 1 and the sixth row the 9. The hint gives us for free that we have a 7 to the left of the 1.

There are more interesting deductions we can make as well. Consider the seventh column. The clue is 16, 9 and this can be satisfied in two ways: {1357} in some order and then a singleton 9, or {79} and {135} in some order. However, we can prove that the latter construction is impossible; the middle row is an even number, and also we have already used the 1 and the 5 in the bottom right hand box so we can’t place those numbers there. Thus, the first four numbers must be {1357} in some order and there is a 9 somewhere in the bottom right box.

The clue in the first row requires a 5 at the end. Given the 10, 10, 5 clue and the 4 already placed in the sixth column, the only odd substring in the last box must be the 5. We thus must have the 5 in the first row, and now only the 3 can fit in the fourth row. We also gather that the last two columns of the first row must be even, and we have enough clues to place these (using standard Sudoku rules).

Finally, we can place the 4 in the middle right box (now that the 3 is there, there’s only one space left where it can fit). Similarly, we can place the 5 (knowing that it can’t be in the seventh column any longer).

From this point on, solving the rest of the puzzle should be reasonably straightforward. The next step would probably involve placing 1, 9, 6, 7 and 3 in the first row (in that order – using the column hints and the knowledge that we have two tens)!

For these contests, I’d say the challenge lies largely in figuring out how the ruleset can be used to help solve the puzzle (and, well, speed; you’re thrown 13-15 puzzles to solve in the space of 90 minutes and I can only usually manage about seven or eight, and for that matter the ones I do finish are the ones on the easier end of the scale!).

On Hints in Puzzles

I played a game of Paperback with a couple of friends from Imperial yesterday. The game involves players making words from letter cards in their hands, and using them to buy additional, more powerful letter cards and/or cards worth victory points. It’s pretty much a deckbuilder crossed with a word game; while anagramming skills are indeed important, they aren’t always necessary (for instance, I managed to form the word WORK to buy the second highest tier victory point card) and certainly aren’t sufficient (keeping one’s deck efficient is certainly important).

In any case, the game reached a point where one of my classmates seemed to be agonising over what was presumably a tricky hand. The game does have a number of cards that use digraphs such as ES, TH or ED, which can make searching for words a little trickier. The common vowel (a vowel that players are all allowed to use in their words in addition to the cards in their hand) was an O, and the hand in question was [IT], [R], [B], [U] and two wilds. I immediately saw a solution when he sought help (BURrITO or BURrITOs; none of the cards had abilities dependent on word length) and let him know that a ‘perfect’ solution for his hand existed, though we decided to let him figure it out for himself. This started to drag on, though, and giving him the answer directly seemed excessive; I thus decided to drop hints that would hopefully lead him to the solution.

Technically, the search space that he would have had at this point would have been 5! + 6! \times 26 + {7 \choose 2} \times 5! \times 26^2 which is about 1.7 million possibilities, though of course one does not simply iterate through them; combinations like OqRzBITU would probably not even be considered directly, especially since the distribution of letters in English certainly isn’t memoryless (the Q being a good example; it is rarely followed by any character other than U). I gave a few hints, in this order:

  1. The word is a common word that a person in middle school would likely know.
  2. The word can be made with just one of the blanks.
  3. The blank you use matches one of the letters already on the table.
  4. You can eat it.

We could argue that the point of a hint could be to reduce the search space being considered by disqualifying some solutions, and/or serve as a way to encourage the algorithm to explore cases more likely to be correct first. Interestingly, it seems that clue 1 was neither of the above, though. It didn’t really cut down the search space much, and as far as I know it’s not easy to use this information to organise one’s search. Its point was mainly to reassure my classmate that the solution wasn’t too esoteric and he would know it was a valid solution upon considering it. I didn’t think I had played any particularly uncommon words earlier in the game (the rarest might have just been TENSOR or something), though I think I might have played Anagrams with him before, where I know I’ve called out some more… interesting words.

The next two clues do actually substantially reduce the search space in a sense though; the second clue slashes it to just 6! \times 26 = 18720 and the third further cuts it down to 6! \times 6 = 4320. I would think that after the third hint, the search should be pretty fast; I would probably try doubling up on the R and T first as they’re common.

Nonetheless, hint number 4 seemed to be the hint he responded best to, and it falls into the second category (encouraging the search to explore cases more likely to be correct). I’m not sure how humans solve anagrams, especially when blanks are involved; I personally seem to look at letters, intuitively construct a word that looks like it incorporates the key letters present, and then verify that the word is constructible (in a sense, it is a generate-and-test approach). Given the point values of the tiles, I saw including the B, U and IT cards as being the most important; thinking of words that use these patterns resulted in BITUMEN and BURRITO fairly quickly, the latter of which was feasible.

I noticed that I tend to bias towards using the constraint letters near the beginning of the word though; this might be a cognitive issue with trying to satisfy the constraints quickly, in an unusual form of the human brain often being weak at long-term planning. This wasn’t really the case with the burrito example, but another friend had a hand of ten cards (I think) at some point with an [M], [IS], [T], [R], [D] and a couple of blanks. With the common O and knowing that the M, IS and D were higher-value, I saw MISDOeR and struggled to incorporate the T, finding it difficult to back out of starting the word with a MIS- prefix. It turns out it might have been okay in that I could have found MISsORTeD, there were easier solutions such as aMORTISeD or MODeRnIST.

On hindsight, though, my hinting might not have been ideal. This is because BURrITO and its plural form weren’t the only solutions; there was OBITUaRy, which some people might find easier to see (though I didn’t actually see this during the game). I think clue 1 would probably already be invalid; I knew the word ‘obituary’ in primary school, since it was a section in the newspapers that I would browse through in the mornings, but I’m not sure it would be fair to expect middle school students in general to be familiar with the term. Clue 2 would certainly be incorrect.

On the Theoretical Complexity of Efficient Testing

Complexity was one of the courses I took at Imperial that I found to be especially intellectually stimulating. I would say it was probably the most challenging course of the degree for me at least (excluding the individual project; the second half of Intelligent Data and Probabilistic Inference probably comes close, also bearing in mind the bar being set at 90). I would say the course has certainly helped me reason about algorithms and problems in more interesting and divergent ways, and has also been useful in figuring out when to stop trying to devise excessively clever algorithms (by understanding when that is impossible).

The course starts by looking at decision problems (that is, problems with a yes/no) answer, and whether they fit into the class called P (decidable in polynomial time). Examples of problems in P include finding the maximum element in an array or list, and finding the shortest path between a pair of nodes in a graph (this is breadth-first search for unweighted, and Dijkstra’s algorithm for weighted, both of which run in polynomial time).

We then move on to NP (nondeterministically decidable in polynomial time) – effectively, this means that it is possible to verify a “proof” of the problem being decided as a yes in polynomial time. Well-known problems in NP include the Hamiltonian path problem (given a graph, is there a path passing through each node once?) – this one is in NP because a “proof” that the answer is yes can be given in the form of a path. We can check that the edges match simply by walking down that path, and the path is a permutation of the nodes. Note that we don’t need to be able to prove negative answers in polynomial time – there is a separate class called co-NP for cases where we can prove these. (NP \cap co-NP is a strict subset of both NP and co-NP, and includes P as well as a couple of other problems like integer factorisation.)

(The course also covered the underlying theory behind P and NP, concerning Turing machines – I won’t go into detail here.)

One of the biggest parts of the course involved the concept of many-one reduction; a problem V reduces to a problem W if we can translate an instance of V to an instance of W, within certain constraints. For example, the problem of determining whether all integers in a set are positive reduces to that of determining whether all integers are negative under a polynomial time constraint; the first problem (positive) holds for some set S if and only if the second holds for T, which is S with all elements multiplied by -1. In a sense, we’re showing that if we can solve W, then we can solve V as well.

We then defined the hardest problems in a given class to be the problems that are complete for that class; that is, every problem in that class reduces to a complete problem (and yes, the complete problems reduce to themselves). For NP, the constraint on the reduction is that it can be carried out in polynomial time. This makes sense as NP would not be closed under reductions allowing more generous bounds (for example, if V reduced to W under some exponential time procedure and W was in NP, that doesn’t mean V is in NP; however, if V reduces to W under a polynomial time procedure and W is in NP, then so is V). This holds because if we had a guess for V, we could “translate” it using our reduction to a guess for W which can be verified in polynomial time.

The Hamiltonian path problem (hereafter HP) I introduced earlier is NP-complete, and can be used to show that other problems are NP-complete (by reducing HP to the other problem). This works because from our definition of NP-completeness, any problem in NP can be reduced to HP, and then reduced to our problem. This involves potentially composing two polynomial time mappings – but, the composition of polynomials is polynomial too. Note that it’s not just a sum, because the “output” of the first mapping, which is the input to the second mapping, could be bigger than the initial input (though only polynomially so!).

(For showing HP itself is NP-complete, there is a reduction of SAT – the problem of determining whether a logical formula in conjunctive normal form – to HP, and SAT itself can be proven NP-complete from the definition of NP over Turing machines.)

The inspiration for this post came from some preparatory work I was doing for a reading group with James, on algorithms for test-suite minimisation. The authors comment that the problem of finding a minimal representative subset for a test-suite is NP-complete. As a starting point, removing some of the details, their specific problem (involving mapping of tests to requirements shown by said tests) given is easily reformulated as the Minimum Set Cover problem; that is, given some possible subsets C of a bigger set S, find the smallest subset of C, such that the union of the sets we put in our subset itself is S.

Strictly speaking, this isn’t a decision problem, but we can put it into a decision form: given some possible subsets C of a bigger set S, is there a subset of C, such that the union of the sets we put in our subset itself is S with size not greater than k? Solving the original problem can then be performed by a binary search on k, at each step testing this decision problem for a different value of k. Let’s call this problem Set Cover (Decision) or SC(D).

We could proceed with trying to show HP reduces to SC(D), though I find it easier to do things a bit differently – we can pick any problem that’s NP-complete (so I’ll pick SAT), and we can also exploit transitivity of reductions as mentioned above. I’ll thus use two intermediate steps:

  1. Reduce SAT to 3SAT (the problem of determining whether a formula in conjunctive normal form where each clause has three literals is satisfiable)
  2. Reduce 3SAT to Vertex Cover (VC – given a graph and some positive integer k, is there a set of nodes, size up to k, such that every edge has at least one endpoint in the set?)
  3. Reduce VC to SC(D).

Step 3 is probably the easiest now – given an instance of VC, we map each edge to be an element in S, and each node to be a candidate subset containing all of the edges that are adjacent to it. That mapping requires us to iterate through the graph perhaps a few times, but that’s definitely polynomial in the input. Comparing the definitions it’s pretty clear that this should work (that said, if you were actually doing a complexity course you might need a more rigorous proof).

Step 1 relies on the use of logical equivalences – the idea being that we can always rewrite a clause that doesn’t use three literals into one or more clauses that do. The one and two cases simply involve repeating one of the literals that’s already there; if we have more than three, we can introduce auxiliary variables to chain them together:

// SAT
A or B or C or D or E

// 3-SAT equivalent version
(A or B or X) and
(!X or C or Y) and
(!Y or D or E)

Consider that the 3-SAT version is satisfiable if and only if the SAT version is satisfiable. If any one of the original variables can be set to true, then we can choose suitable values of X and Y (plus other auxiliary variables in larger cases) to satisfy all of the other clauses, “rippling out” from some variable that was set to true. However, if none of them are, we’ll run into a conflict somewhere.

Finally, step 2 is somewhat trickier. At a high level, the idea is that we want to enforce some way of selecting a truth value for each variable, that would satisfy at least one of the literals in a clause. We can then construct triangles for each clause, somehow wanting to have our cover only include two of the nodes in a triangle (corresponding to ‘false’ literals). The unselected literal must then be “true” in some sense, but we cannot have multiple conflicting literals in different clauses being true. To handle this, we introduce an additional constraint linking the literals we pick as true across clauses, yielding a construction like this:

The formula is satisfiable if and only if we can build a vertex cover picking two of the nodes in each clause, and one truth value for each variable. So k = 2C plus V, where C is the number of clauses and V the number of variables.

I think the course and especially exams on it were difficult because these constructions require nontrivial insight, which can be really difficult under pressure. Having a large set of known starting points would certainly have helped; this kind of three-stage derivation would probably not be needed in an exam, though constructions of a similar level of difficulty as step 2 were certainly present.

Another Look at Dynamic Programming

Whilst on the tube today, I overheard a mother teaching her child how to count, using a method likely to be extremely familiar to many – fingers. The child counted correctly from one to ten, and then the mother added her hands too and asked the child to count how many fingers there were now.

“One, two, three -“

And so on, till twenty. The mother then attempted to explain that it would have been faster if the child continued from ten, rather than starting again. Although it wasn’t really an example of the concept, the words dynamic programming immediately shot to the front of my mind. I initially found this to be a rather confusing concept to grasp (let’s say that up to high school programming contests, if a problem wasn’t solvable by exhaustive search or greedy algorithms I’d likely have struggled), so I figured a post on it might be worthwhile.

(This isn’t really an example of DP; I’d say it’s closer to divide and conquer plus the use of a cache. We’ve cached the answer that the child has ten fingers, and identified the problem as being taking the sum of the child’s and parent’s fingers. Note that because of the possibility of amputation or polydactyly, the subproblems are not the same – and, specifically, saying 2 * 10 = 20 isn’t generally correct.)

Essentially, the key idea behind dynamic programming (DP) is that we save time by not re-doing work that we’ve already done, by remembering the results to intermediate steps. Of course, this tends to mean that there’s a space overhead. This is generally useful in cases where a problem is too large to solve, yet it can be decomposed into smaller pieces, and importantly we can combine optimal solutions to these smaller pieces, to get a solution that is optimal for the original problem. (More formally, this is known as optimal substructure.)

Furthermore, we want to get some significant benefit out of actually remembering the answers (in practice, we want to use our previous work multiple times; this manifests in the form of overlapping subproblems). This is what would distinguish an approach as being a DP-based one, as opposed to divide and conquer.

Of course, the fingers example is trivial. There are many other natural examples (the ones that come to mind first for me include knapsack problems and route-planning), though I’m not sure I directly apply DP that much in a natural context (although quite a few days have tasklists that could be done solving an ordered constrained TSP, the last time I used the Held-Karp algorithm was probably for my third year project). It certainly does see many applications that are relevant to daily life (error correction in search queries / autocorrect via Levenshtein distance; not sure how they are actually implemented but routing applications like Citymapper and Google Maps are likely to involve such algorithms as well).

In terms of implementation, the cache-based “top-down” solution was what I learned first, and to me at least was intuitively easier to understand. When you encounter a subproblem, you check a lookup table to see if you’ve done the problem before; if you have, you just take the answer from that. If you haven’t, solve the problem the hard way (this may involve more subproblems – when solving these, it’s important to look at the table again), and then (important!) store the answer you obtained back in the table.

The alternative “bottom-up” method involves generating solutions to smaller subproblems, and using these to build up the solution to a bigger problem. I’d probably first actually used a method along these lines when introduced to the Fibonacci sequence (probably in year 4 or so) – I remember being asked to compute F_{13} and did something like “1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, uh… 144, 233”. (This is linear time. It’s possible to do better via matrix exponentiation, or Binet’s formula – bonus points if you pair the exponentiation with a fancy multiplication algorithm like Karatsuba or even Schonhage-Strassen.)

From a computing point of view there can be both benefits and disadvantages to this versus the “top-down” method.

  • Ease of understanding and/or code readability are likely to depend on the problem; for Fibonacci I would prefer bottom-up, but I usually find the top-down case to be more approachable (it’s more intuitive to me at least to think “here’s how I decompose this problem” as opposed to “here’s how I build a solution from smaller solutions”).
  • The top-down approach might be able to solve some problems without necessarily computing all smaller subproblems that a bottom-up solution counting up from 0 or 1 might deal with. You can, of course, implement this in a bottom-up solution… provided you know how to compute the required subproblems in a way that isn’t itself too costly. With a top-down approach you get this “avoidance” for free.
  • As an extension of the previous point: for bottom-up you’ll need to figure out a safe ordering to go through the subproblems (you can’t have a solution depending on something that hasn’t been computed yet). This is easy in most cases (*cough* Fibonacci), but can be extremely difficult in others (chess transposition tables come to mind; problems with online input, many base cases and a massive domain).
  • Recursive implementations (which tend to be top-down, though could plausibly be in either direction; it’s possible to maintain your own call stack on the heap, or pass some kind of lookup table around) incur the overhead of function calls, and can cause stack overflows for large problems.
  • Handling limited memory (there are many 2D array problems for which only the last row of results needs to be kept; alternatively with Fibonacci we only need the last two results) tends to be more naturally expressed with the bottom up method (though of course, you can clean the top-down cache). This is probably because you’ll have defined an order for solving the subproblems, which may not be as immediately clear with the top-down method.

Note that although this is a powerful tool, there are quite a number of cases where you don’t actually need to consider all of the ways of decomposing a problem into subproblems. A well-known example would be the activity selection problem; given a set of mutually exclusive activities with start and end times, find the largest set of activities I can participate in. I can solve this optimally by sorting events by their ending time, and aggressively picking events to fill my schedule where feasible. The key differentiator here is what’s known as the greedy choice property; that making an optimal choice at each step gives us the overall optimal solution.

In practice anyway it’s highly unlikely that I’d weight my activities equally, so we then get to the weighted activity selection problem, and the greedy method no longer works (but we can still use dynamic programming – as before, sort the activities by their ending time E, and for each activity, pick the better of not attending it, or attending it and behaving optimally before the start time of said activity).

Perverse Incentives

gametheory

I do watch a couple of Let’s Plays on YouTube, and one game that a couple of channels have been playing is Trivia Murder Party from the Jackbox Party Pack. I’ve found the format to be interesting and relatively well-designed for building tension, though there are a few weird edge cases because of how the rules are laid out.

The final round has rules as follows:

  • One player is in the lead (the player with the fewest number of spaces left to the finish line).
  • Players are presented with a category, and need to decide if objects presented fit that category or not. The player in the lead has two objects; other players have three (this is a rubberbanding measure used to encourage them to catch up).
  • For example, a category could be “Asian Countries” with objects Russia, Shanghai and the USA. In this case players should only select Russia (Shanghai is a city, and the USA is in North America).
  • For each object correctly classified, players advance one space on the board. No penalties are issued for objects that were incorrectly classified.
  • The player with the lead moves first. If he is across the finish line, he wins (independent of what non-leading players do).
  • In the event of a tie, the highest ranked player (based on the previous rounds) who is not in the lead takes the lead. Furthermore, all tying players apart from the new leader (including the old leader, if relevant) move back 1 space.

One strategy of playing the final round, and an arguably sensible one is to always try and answer the questions to the best of one’s ability. Yet, the aforementioned rubberbanding mechanism means this isn’t always optimal – suppose you’re playing against an incredibly knowledgeable opponent who implements the maximising strategy. Furthermore, suppose you’re in the lead, with 5 spaces to go before finishing, while your opponent has 7. Then, consider:

  • If you advance 2 spaces, you’ll have 3 spaces left to go whilst your opponent has 4. Then, no matter what you do, your opponent will take the lead on your next turn, and you’ll lose.
  • If you advance 1 space and your opponent advances 3, you’ll both be at 4 spaces to go. Because of the tie rule, he leads and you get pushed back one space. This brings you to (5, 4). Now, as a non-leader advance 3 spaces; no matter what happens you retake the lead. Finally, advance 2 spaces and win.

We can generalise this to solve the two-player case, by considering what is a winning position – in the case where both players have very strong trivia knowledge, but the opponent always advances the maximum number of spaces.

  • (1, n), n \geq 2 is clearly a winning position. Simply advance and exit.
  • (2, n), n \neq 1 is also winning for the same reasons (and (2, 1) is losing).
  • (3, n) is a bit more interesting. n \leq 2 is clearly lost. But (3, 4) is actually lost too, because that becomes (2, 1) or (3, 1) after one turn, both of which are losing positions.  (3, n), n \geq 5 and greater are won; advance to (1, n-3) and win.

Having considered a few cases, we can use what’s called induction to determine the rest of the winning positions. What this means is that we are defining winning positions in terms of whether other positions are winning. This can be dangerous if we produce circular definitions, but the relationships we use here are well-founded in that we maintain that the total number of spaces left to go for both players always decreases, for each of the sub-problems we look at.

We thus say that a position (p, q) is winning, if and only if any of the following are true:

  • p = 1, or p = 2, q \neq 1.
  • p > q + 1 and at least one of (p-3, q-2), (p-2, q-2) and (p-1, q-2) is winning.
  • p = q + 1 and at least one of (p-3, q-1), (p-2, q-2) and (p-1, q-2) is winning.
  • p = q - 1 and at least one of (p-1, q-3) and (p, q-3) is winning.
  • p = q - 2 and at least one of (p-2, q-3) and (p, q - 3) is winning.
  • p = q - 3 and at least one of (p-2, q-3), (p-1, q-3) and (p + 1, q-3) is winning.

We can derive a similar inductive rule for cases where one always maximises the number of answers: for each of the “at least one of” choices, always pick the first option. We can then consider when the (probably) “intended” strategy of trying to answer to the best of one’s knowledge fails to be optimal. In terms of implementation, the inductive definition above swiftly lends itself to a dynamic-programming implementation, whether “top-down” or “bottom-up”.

I’ve only considered the 2 player case because it’s relatively simple to analyse… things get substantially more complex once we go beyond that, especially factoring in the tiebreaking rules based on first-round performance. In practice, given that the questions can be difficult and unpredictable, at least for me it would probably be too risky to try to take a dive like this – but I can see this becoming relevant if expert players played this.

  • 1
  • 2