Burst Balloons, Dynamic Programming, and Maybe More?

--- tags: programming, CS, notes, algorithm, Rust, dynamic programming, leetcode, --- # Burst Balloons, Dynamic Programming, and Maybe More? I've always been pessimistic about my dynamic programming skill, which I think is largely because when I first learned it during my sophomore year I didn't understand shit, so this tag becomes my go-to whenever I want to sharpen my leetcode skills. Rise from where you fell, after all. So I once again stumbled upon [burst balllons](https://leetcode.com/problems/burst-balloons/description/). Wow, it's green, and I have zero idea what I wrote; another typical day when a programmer picks up one of their old projects! Except this time I *do* remember that when I wrote the submitted answer I was super duper comfused *why* the comment section pointed out it's basically *the matrix chain problem* stated in a slightly different way and claiming its hence obvious: I followed the steps as taught by the gool'ol [Introduction to Algorithms](https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/), got AC, but in the end of the day *why* and *how* this algorithm works? Before long I decided that future me would figure that out and I should better keep working on other problems. So future me I am. ## The Matrix Chain Problem The problem stems from an observation whoever had dealt with tedious hand-written matrix multiplications have had must discovered: that along with the non-commutative property and associativity of matrix multiplication comes with the fact that the order one multiply them matters a lot. Heck, if determining the best order multiplying chain of matrices itself takes considerable amount of time, why bother? Shut up and calculate! Luckily, this ain't the case: the meta-problem (which turns out to be of $O(n^3)$ as we'll soon see) of the matrix arithmetics typically has drastically lower dimensions than the matrices themselves, so this effort typically pays off. Sharpen your tools before you start the job! ### Naive Approach Using a recursive definition, one could see that total possible ways of parenthesization is the Catalan's numbers, which is $\omega(2^n)$; this definitely isn't what we want. ### The Partition Scheme Observe that a well-defined parenthesization always splits the list into two components which are themselves with well-defined parenthesization: not that it's the only way to do this, but we indeed find *one* way to define subproblems! Consequently, the optimal solution is to iterate over all the possible points for a well-formed parenthesization to split the sequence, compare and find max, and voila! ...Except that's not entirely the full story. Consider this: given $n$ indexed balls, one could grab any positive amount of them at once in the increasing order of the indexing, again and again till the $n$ balls are depleted, for instance consider $n=6$, one may say hey I grab 1, then 2, followed by 3, that's one way to do this. How many ways are there may one deplete this buffer of balls? Well, it's... exactly $2^n-1$: for $n=m$, it's either grab $m$ at once (which contributes $1$), grab $m-1$ then consider the $n=1$ case, grab $m-2$ then consider the $n-2$ case, so on and so forth till we consider the grab $1$ then consider the $n=m-1$ case, which follows by induction. The point is, our naive partitioning scheme seem to do little, in that we still need to consider *exponential* amount of possible configurations; the objective is to find an algorithm that somehow have a grasp of all the exponential amount of configs and gives the optimal one in polynomial time, but how is it possible to find a needle in an exponential sized haystack within polynomial time? Except we indeed can! Take searching in a sorted array for example: there are $n$ possible candidate, but we only need to check $\lg{(n)}$ of them before we conclude the answer. The key is to spot *some* structural information in the data: some data actually teaches us a lot more than itself, by carrying the ensemble of information of several more data points! The point here is *memoization*: there are *duplicates* in the set of subproblems, i.e. many of the subproblems are actually the same. Back to the $n$ balls analogy, consider these two ways of taking balls ($n=7$): if one were to try defining the problem recursively, one would find that the last $3$ in the two crude configurations give exactly the same subproblem! ``` [2, 2, 3] [1, 3, 3] ``` In our case, after factoring out the duplicate ones, we are only dealing with $O(n^2)$ of them: our partition scheme has a really nice feature, in that the subproblem it induces are based on the *subarray* of the original array, and the number of possible subarrays is simply $C^n_2$ which is merely quadratic over $n$. Together with the linear time search for max for each subproblem, we now know intuitively that the algorithm indeed takes $\Theta(n^3)$ time, *if each lookup to subproblem takes constant time*. ## The Burst Balloons Problem Let's re-state the problem: suppose one has a sequence of balloons, each tagged with some positive integer (why in the world does leetcode always use `i32` for such semantics again?); pop them and you get the product of the balloon and its neighbors, default to 1 if the target were on the boundary. After popping a balloon, they fill up the vacancy by moving by 1. E.g. consider `[1, 3, 5, 7]`, if one were to pop them in the order `[3, 5, 1, 7]`, one would get 15 (leaving `[1, 5, 7]`), 35 (leaving `[1, 7]`), 7, and finally 7, giving a total of 64 points. At first glance, this problem differs a *lot* from the matrix chain problem. Take a random matrix chain problem for example, say the dimensions are `[3, 1, 4, 1, 5]`, then one way to split up the problem is to consider `[3, 1, 4]` and `[4, 1, 5]`, i.e. for the 4 matrices, consider the possibility if optimal parenthesization is to split into 2 pairs of matrices first. This is nice since the subproblem are simply *subarrays*, making the look up straightforward and constant time: basically, to store all the possible $C^n_m$, consider triangular 2-D array. Similar naive strategy doesn't quite work for the balloons: being balloons, they *move*, taking up the vacancy in between; `[3, 1, 1, 5]` is *not* a subarray of `[3, 1, 4, 1, 5]` after we pop 4, and this approach leads to exponential number of subproblems, i.e. the power set. We might even suffer from factorial time if we're not careful on how we iterate through them. As a nail in the coffin, even if we have the answer to the proper subproblems, how do we even combine them to get the answer? `[1, 4, 1, 5]` is *vastly* different from the original question `[3, 1, 4, 1, 5]`, since the boundary condition changes from the default 1 to 3, so the optimal choices are probably different, yielding different answers! The trick here is to __*ask the right question*__, i.e. __*splitting the problem into subproblems in a nicer way*__. Instead of asking which balloon we should pop first (in the same spirit of matrix chain problem, what's the partition scheme for the outer most pair of parentheses), we might instead ask, what balloon should we pop *last*? Immediately, this makes one huge improvement: given $n$ balloons, suppose the $k$-th were to be popped last, then the following subproblems are indeed *subarrays* of the original problem: denoting the implicitly unbreakable sentinel balloons with uppercase English, we went from $\{ \text{ONE}, a_1, a_2, \cdots, a_n, \text{ONE} \}$ to $\{ \text{ONE}, a_1, a_2, \cdots, a_{k-1}, A_K, a_{k+1}, a_{k+2}, \cdots, a_n, \text{ONE} \}$; this is nice because we know the number of subarrays is merely quadratic in $n$, and the backing storage could be implemented using triangular 2-D array with constant time look up! With one small caveat: it turns out the subproblems are actually a broader category of the problem, i.e. the boundary may be multiplied with other numbers rather than 1, but this is OK since the subproblems including the unbreakable sentinels are again just subarrays of the original array. For the base case, just note the aforementioned fact that it's actually a broader category. ## Dynamic Programming Revisited 1. Check if a problem could be seen as being comprised of several subproblems - There may be multiple ways to do this, as illustrated by the burst balloons problem, and they might hint vastly different spacetime requirements! 2. Check if the subproblems overlap - One should find subproblem that resides in a significant amount of different subproblems turns out to be quite abundant. - The magic just won't work if all the subproblems are fresh and first seen: we're just brute-forcing it. 3. Check if the subproblems are easy to work with - Assmebling: is it trivial for one to calculate the original problem, once all the required pieces are ready? The first attempt towards the balloon problem certainly doesn't exhibit such nice a property - Memoization: Is it trivial to store and retrieve the answers to all the subproblems we've solved? Powerset is alarming since it hints exponential space storage and hence expoenential run time (since at least exponential time to allocate them), storing may be non-trivial bit-banging, and retriving is again non-trivial, maybe an $O(n)$ job, if one were to insist on the bit-banging. A nice hint that the problem could be tackled with dynamic programming is that all the subproblems could be __*indexed*__ s.t. they could be stored just like storing data in DRAM. 4. Hack: use any sort of `Map` to do proof of concept - It's kinda tedious to fit the indexing into proper (multi) dimentional array. The point is to make storing, querying, and accessing very quick, which is exactly the job for the `Map` data structure e.g. `BTreeMap` or `HashMap`, so one might instead just use these to do a proof of concept, and if everything goes well the runtime should probably acceptable. 5. Either top-down (recursively ask the subproblems; elegant and easy to implement but probably more expensive due to stack manipulation overhead) or bottom-up (somewhat more troublesome to implement since one needs to figure out both the indexing and the order of subproblems one should tackle with: some sort of __*partial ordering*__ between subproblems) ## More? When $n$ grows, typically the space of configuration grows at least exponentially. An algorithm implies the ability to pin point some specific config or deterimine some property of the ensemble, given arbitrary instance in such large a configuration space. Think of the good'ol sorting we've kinda taken for granted. It's $n!$ configuration of integers, how in the world do we pin point the one exact *sorted* configuration within polynomial time and little extra space? Of course we had been taught bubble sort or insertion sort in elementary school, and its quadratic time is just meh, but wow isn't it amazing we've crossed the exponential growth line like it's nothing? Then there's *typical* instance (and atypical ones): naive quick sort implementation deals with the typical ones elegantly and concisely within log-linear time and constant space, and typical is the typical case, i.e. the majority of the time. Information theory kicks in: a nice algorithm, at least most of the time, is just like some coding that captures the typical instances quite well. The complexity of the coding scheme relates directly to the runtime characteristics of the algorithm. Dynamic programming tells us that even though the configuration space is gigantic, there might be some sort of (subproblem) __*structure*__ that hides beneath, if we __*ask*__ in the right way, duplicating and repeating themselves like a crystal. With such structure in hand, we then see that the entropy isn't nearly as high as it might seem. P vs NP? ## References - [`HashMap` proof of concept](https://pastebin.com/rD9YVPS5) - [Proper implementation using 2-D array](https://pastebin.com/GWfB0iJA)