Skip to main content

Practice Solutions and Feedback

Keep a first attempt before using this key. A matching number without a state, boundary, justification and required witness is incomplete. Accept alternative valid tied optima and equivalent well-defined indexing conventions.

P1–P5: foundations​

P1. s,a,u cannot append a again; s,b,u can. Key (visited,u) separates these histories. A general bound is O(n*2^n) states, with up to n outgoing choices each. On a DAG an extension cannot revisit an earlier prefix vertex, so endpoint-only longest-path state suffices under source-specific initialization.

P2. Rod cutting has n+1 lengths and n(n+1)/2 first-piece candidates. Matrix chains have n(n+1)/2 intervals and (n³-n)/6 split candidates. At n=4 both transition totals happen to be 10. Merge sort on eight positions has 15 calls in its full binary recursion tree, while merge work is Θ(n log n). Repair a table-size-only time bound by summing the work of each state.

P3. Tight states are cacheable for a fixed N,S; a fresh local cache per query is sufficient. If N changes, old entries can describe different suffix limits. Include the fixed input in the key or reset the cache. Coin 1 makes every nonnegative smaller remainder reachable, so the proposed sparsity example fails.

P4. value[4]=3 points to capacity 2 before the latter changes; value[2] then becomes 3 using the same item. A pointer walk yields repeated ID 0. Store the full prefix/capacity table, O((n+1)(W+1)) cells, and decrease the item prefix on every backward step. Reversing to ascending updates also changes the value to an illegal 6 for 0/1 use.

P5. Before iteration i the pair is (F(i),F(i+1)); simultaneous assignment preserves it. O(n) additions and O(1) integer objects do not mean O(1) bits: live numeric storage is O(n) bits and summing linear addition costs gives O(n²) bit work. Input/output representation and enormous iteration counts remain relevant.

P6–P10: sequences, capacity and grids​

P6. Strict LIS length 2, e.g. indices [0,3]; nondecreasing length 3, indices [0,1,3]. Strict search uses first tail>=x, nondecreasing uses first tail>x. For a fixed length, smaller tail dominates larger for future extension. Final tails [2,4,6] in the second input use positions 3,4,2 and violate order.

P7. Table rows are [0,1,2,3], [1,0,1,2], [2,1,1,1]; cost 1 alignment (a,a),(None,c),(b,b). Removing gaps gives exactly the two inputs. a -> b costs 1 with substitution or 2 with insert/delete only. Affine gap penalties require boundary state distinguishing an already-open gap from a new one; the single unit-cost table does not retain this information.

P8. Ratio-first takes (2,3) for value 3. The 0/1 optimum takes (3,4) for 4; unbounded takes two first items for 6. Exact-fill weight 1 is impossible. At-most bases are zero, exact-fill bases are reachable only at weight zero. Use descending capacities for 0/1, ascending for reuse, and preserve item layers or justified historical choices for reconstruction.

P9. Unordered objects are 1111,112,22, count 3; ordered sequences are 1111,112,121,211,22, count 5. Combinations process denominations outside ascending totals, using the current denomination any number of times. Ordered sequences sum over the last coin for each total. The single empty construction gives count[0]=1. Duplicate types can overcount equivalent denomination choices. Neither algorithm is wrong if its object contract actually differs.

P10. Obstacle-path count 2; reward maximum -11 along right/down. A blocked destination is unreachable, not zero. With four-direction moves row+column is not strictly increasing; a new graph algorithm or augmented-state proof is needed. Unrestricted walk counts may be infinite on relevant cycles.

P11–P14: intervals and trees​

P11. (A0*A1)*A2 costs 40+60=100; A0*(A1*A2) costs 24+30=54. Witness (0,(1,2)) preserves matrix order. The split cost is p[i]*p[k+1]*p[j+1]; fill shorter intervals first. Count all split trials, not just table cells, for O(n³) time and O(n²) table storage.

P12. First key as root costs 3*1+1*2=5; second as root costs 1*1+3*2=7. Empty-interval cost is 0, and each root candidate adds both subtree costs plus the interval's total successful frequency. A model with unsuccessful queries also charges gaps and changes base cases; the given successful-only calculation does not validate that richer model.

P13. Each leaf has (skip,take)=(0,3); center has (9,7), so choose all leaves for 9. All-negative weights give empty selection, value 0. A triangle plus an isolated vertex has four vertices and three edges but is neither connected nor acyclic. Validate structure rather than just edge count.

P14. Crossing parent->child decreases distances to the child's size vertices by one and increases the other n-size distances by one, so S(child)=S(parent)+n-2*size(child). Path sums are [6,4,4,6]. Each edge is processed a constant number of times in two passes. An iterative traversal avoids recursion-depth failure without changing this linear bound.

P15–P20: subsets, digits and algorithm choice​

P15. Original tour [0,1,2,0] costs 4; removing 2->0 leaves [0,2,1,0] costing 12. Only base D({0},0)=0 is initially reachable. An absent tour returns (None,[]). Signed costs remain finite since visits are bounded. Empty matrix convention is (0,[]); one city is (0,[0,0]) and ignores diagonal cost. Do not infer these conventions from the n>=2 formula.

P16. For each element choose outside mask, in mask only, or in mask and submask; multiply three choices n times. n=20 has 20,971,520 rectangular slots and 167,772,160 payload bytes, 160 MiB at eight bytes/slot. Omitted costs include dictionary/list structure, key objects, integer values, parents and output. Actual reachable allocation can differ, so this is a model estimate, not a measurement.

P17. Answers 3 (1,10,100), 1 (0), and 2 (12,21). Transition uses old tight AND chosen digit equal to bound digit. Terminal count is one iff the sum matches, including zero. Cache belongs to fixed bound and target. Padded zeros do not affect sum but can falsely satisfy digit-occurrence constraints.

P18. Drop (3,4) under at-most maximization because (2,5) is lighter and more valuable for the same remaining items. With exact target weight 3 and no future items, only the dropped state is feasible. Counting distinct optima also needs multiplicities even when one representative suffices for value.

P19. Replacing an optimum's first interval by the earliest finish leaves later intervals feasible and preserves cardinality. With weights, the two short jobs give 6 and the long gives 7, invalidating objective preservation. Prefix DP compares skip to value plus compatible-prefix optimum. With long value 6, either job-ID set {0,1} or {2} is valid. Return chronological order.

P20. Distances are [0,-5,-2,-3,None]; path to 3 is 0,2,3. All-zero initialization instead permits a start at any vertex with a zero-edge path of weight 0, a different question. Matrix-chain split cost requires both child optima plus multiplication cost, not one predecessor's path cost.

Repair and recheck​

Classify an error as state, decomposition, base, order, witness, cost or contract. Repair that specific issue, then solve a fresh instance without the key. The assessment rubric requires competence in every area; extra correct arithmetic cannot compensate for an invalid state or illegal witness.