6.006 Introduction to Algorithms, Problem Session 8 Solutions

Introduction to Algorithms: 6.006 Massachusetts Institute of Technology Instructors: Erik Demaine, Jason Ku, and Justin Solomon Problem Session 8 Problem Session 8 Problem 8-1. Sunny Studies Tim the Beaver needs to study for exams, but it’s getting warmer, and Tim wants to spend more time outside. Tim enjoys being outside more when the weather is warmer: specifically, if the temperature outside is t integer units above zero, Tim’s happiness will increase by t after spending the day outside (with a decrease in happiness when t is negative). On each of the n days until finals, Tim will either study or play outside (never both on the same day). In order to stay on top of coursework, Tim resolves never to play outside more than two days in a row. Given a weather forecast estimating temperature for the next n days, describe an O(n)-time dynamic programming algorithm to determine which days Tim should study in order to increase happiness the most. Solution: 1. Subproblems • Let t(i) be the temperature on day i • x(i): the maximum happiness increase possible during days i to n 2. Relate • Guess whether studying or playing on day i will yield more happiness • If study, no change in happiness, but may study or play on the next day, x(i + 1) • If play, change happiness by t(i) and either – study on day i + 1, t(i) + x(i + 2), or – play on day i + 1 and study on i + 2, t(i) + t(i + 1) + x(i + 3) • x(i) = max{x(i + 1), t(i) + x(i + 2), t(i) + t(i + 1) + x(i + 3)} for i ∈ {1, . . . , n − 1} 3. Topo. Order • Subproblem x(i) only depends on subproblems with strictly larger i, so acyclic 4. Base • x(n) = max{0, t(n)}, if only one day, either play or study • x(n + 1) = x(n + 2) = 0, if no more days, can’t increase happiness 5. Original • x(1) is the maximum happiness increase possible from day 1 to day n • Store parent pointers to reconstruct days studied 6. Time • # subproblems: x(i) for i ∈ {1, . . . , n + 2}, n + 2 = O(n) • work per subproblem: O(1) (constant branching factor) • O(n) running time Problem 8-2. Diffing Data Operating system Menix has a diff utility that can compare files. A file is an ordered sequence of strings, where the ith string is called the ith line of the file. A single change to a file is either: 2 Problem Session 8 • the insertion of a single new line into the file; • the removal of a single line from the file; or • swapping two adjacent lines in the file. In Menix, swapping two lines is cheap, as they are already in the file, but inserting or deleting a line is expensive. A diff from a file A to a file B is any sequence of changes that, when applied in sequence to A will transform it into B, under the conditions that any line may be swapped at most once and any pair of swapped lines appear adjacent in A and adjacent in B. Given two files A and B, each containing exactly n lines, describe an O(kn + n2 )-time algorithm to return a diff from A to B that minimizes the number of changes that are not swaps, assuming that any line from either file is at most k ASCII characters long. Solution: 1. Subproblems • First, use a hash table to assign each unique line a number in O(kn) time • Now each line can be compared to others in O(1) time • x(i, j): the minimum non-swap changes to transform A[: i] into B[: j] 2. Relate • If A[i] = B[j], then recurse on remainder • Otherwise maximize a last change applied: – A[i] is deleted – an insertion matches with B[j] – the last two in A[: i] are swapped to match the last two in B[: j] • if A[i] = A[j], x(i, j) = x(i − 1, j − 1) ⎫ ⎧ ⎨ 1 + x(i − 1, j) delete ⎬ 1 + x(i, j − 1) insert • otherwise, x(i, j) = min ⎩ ⎭ x(i − 2, j − 2) swap if A[i] = B[j − 1] and A[i − 1] = B[j] 3. Topo. Order • Subproblem x(i, j) only depends on subproblems with strictly smaller i + j, so acyclic 4. Base • x(0, 0) = 0, all lines converted • x(i, 0) = i, must delete remainder • x(0, j) = j, must insert remainder 5. Original • x(n, n, 0) by definition • Store parent pointers to reconstruct which changes were made (for cases where A[i] 6= A[j], remember whether a deletion, insertion, or swap occurred) 6. Time • pre-processing: O(kn) • # subproblems: (n + 1)2 = O(n2 ), x(i, j) for i, j ∈ {0, 1, . . . , n} • work per subproblem: O(1) Problem Session 8 3 • O(n2 ) running time Problem 8-3. Building Blocks Saggie Mimpson is a toddler who likes to build block towers. Each of her blocks is a 3D rectangular prism, where each block bi has a positive integer width wi , height hi , and length `i , and she has at least three of each type of block. Each block may be oriented so that any opposite pair of its rectangular faces may serve as its top and bottom faces, and the height of the block in that orientation is the distance between those faces. Saggie wants to construct a tower by stacking her blocks as high as possible, but she can only stack an oriented block bi on top of another oriented block bj if the dimensions of the bottom of block bi are strictly smaller1 than the dimensions of the top of block bj . Given the dimensions of each of her n blocks, describe an O(n2 )-time algorithm to determine the height of the tallest tower Saggie can build from her blocks. Solution: 1. Subproblems • Each block may be used in one of three vertical orientations • (without loss of generality, block bases can always be stacked with the base’s shorter side pointed in one direction) • Because the stacking requirement requires base dimensions to strictly decrease, any optimal tower may use any block type at most three times (once in each orientation) • Sort dimensions of each block and remove duplicates (e.g., in O(n) time with hash table) • For each block type with sorted dimensions a ≤ b ≤ c, construct three block orientations (a, b, c), (a, c, b), (b, c, a) (last dimension corresponding to height), and add them to an oriented block list in O(n) time • (triplicating block types allowable since there are at least three of each type) • Sort lexicographically (first dimension most significant) in O(n log n) time • Re-number sorted list, where block i has oriented dimensions (wi , `i , hi ) with wi ≤ `i • Any stackable tower of oriented blocks must be a subsequence of this sorted list since the wi are sorted, though not every subsequence of this list comprises a valid tower, since the `i are not necessarily sorted • x(i): the maximum tower height of any tower that uses block i and any subset of the remaining blocks 1 through i − 1 2. Relate • Guess the next lower block in the tower, only from blocks with strictly smaller `i • x(i) = hi + max{0} ∪ {x(j) | j ∈ {1, . . . , i − 1} s.t. `i < `j } 3. Topo. Order • Subproblem x(i) only depends on subproblems with strictly smaller i, so acyclic 4. Base • x(1) = h1 , since the maximum in the recurrence is trivially zero 5. Original 1 If the bottom of block bi has dimensions p × q and the top of block bj has dimensions s × t, then bi can be stacked on bj in this orientation if either: p < s and q < t; or p < t and q < s. 4 Problem Session 8 • Some block must be the top block, so compare all possible top blocks • max{x(i) | i ∈ {1, . . . , n}} 6. Time • • • • • • pre-processing: O(n log n) # subproblems: n, x(i) for i ∈ {1, . . . , n} work per subproblem: O(n) computing the solution: O(n) O(n2 ) running time Note that this problem can be solved in O(n log n) with a similar optimization as in Longest Increasing Subsequence from Recitation 15. Problem 8-4. Princess Plum Princess Plum is a video game character collecting mushrooms in a digital haunted forest. The forest is an n × n square grid where each grid square contains either a tree, mushroom, or is empty. Princess Plum can move from one grid square to another if the two squares share an edge, but she cannot enter a grid square containing a tree. Princess Plum starts in the upper left grid square and wants to reach her home in the bottom right grid square2 . The haunted forest is scary, so she wants to reach home via a quick path: a route from start to home that goes through at most 2n − 1 grid squares (including start and home). If Princess Plum enters a square with a mushroom, she will pick it up. Let k be the maximum number of mushrooms she could pick up along any quick path, and let a quick path be optimal if she could pick up k mushrooms along that path. (a) [15 points] Given a map of the forest grid, describe an O(n2 )-time algorithm to return the number of distinct optimal quick paths through the forest, assuming that some quick path exists. Solution: 1. Subproblems • Let upper left grid square be (1, 1) and bottom right grid square be O(n, n) • Let F [i][j] denote the contents of grid square (i, j) • Define two types of subproblems: one for optimal mushrooms and one to count number of paths • k(i, j): the maximum number of mushrooms to reach grid square (i, j) from grid square (1, 1) on a path touching i + j − 1 squares • x(i, j): the number of paths from (1, 1) to (i, j) collecting k(i, j) mushrooms and touching i + j − 1 squares 2. Relate • A path touching i + j − 1 squares ending at (i, j) must extend a path touching i + j − 2 squares to either its left or upper neighbor • If F [i][j] contains a tree: – There are no paths to (i, j) – k(i, j) = −∞ and x(i, j) = 0 2 Assume that both the start and home grid squares are empty. Problem Session 8 3. 4. 5. 6. • Otherwise: – Let m(i, j) be 1 if F [i][j] is a mushroom and 0 otherwise – k(i, j) = m(i, j) + max(k(i − 1, j), k(i, j − 1)) ⎧ ⎫ 0 always ⎨ ⎬ P x(i − 1, j) if k(i − 1, j) + m(i, j) = k(i, j) – x(i, j) = ⎩ ⎭ x(i, j − 1) if k(i, j − 1) + m(i, j) = k(i, j) Topo. Order • Subproblem k(i, j) only depends on k subproblems with strictly smaller i + j, so acyclic • Subproblem x(i, j) only depends on x subproblems with strictly smaller i + j (and k subproblems which do not depend on x subproblems), so acyclic Base • k(1, 1) = 0, no mushrooms to start • x(1, 1) = 1, one path at start • negative grid squares impossible • k(0, i) = k(i, 0) = −∞ for i ∈ {0, . . . , n} • x(0, i) = x(i, 0) = 0 for i ∈ {0, . . . , n} Original • x(n, n) by definition Time • # subproblems: 2(n + 1)2 = O(n2 ), k(i, j) and x(i, j) for i, j ∈ {0, 1, . . . , n} • work per subproblem: O(1) • O(n2 ) running time (b) [25 points] Write a Python function count paths(F) that implements your algorithm from (a). Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 def count_paths(F): n = len(F) K = [[-float(’inf’)]*(n + 1) for _ in range(n + 1)] # init K memo X = [[0]*(n + 1) for _ in range(n + 1)] # init X memo for i in range(1, n + 1): # bottom-up dynamic program for j in range(1, n + 1): if F[i - 1][j - 1] == ’t’: # base case continue if i == 1 and j == 1: # base case K[1][1], X[1][1] = 0, 1 continue if F[i - 1][j - 1] == ’m’: m = 1 else: m = 0 K[i][j] = m + max(K[i - 1][j], K[i][j - 1]) if K[i - 1][j] + m == K[i][j]: X[i][j] += X[i - 1][j] if K[i][j - 1] + m == K[i][j]: X[i][j] += X[i][j - 1] return X[n][n] 5