Transfer exercises

These exercises test the book's ideas in new settings. They don't name the technique on purpose, so work from the problem statement. Chapter 28 has hints and answers; keep it closed while you try.

Exercise A: Parcel ledger. A ledger has n integer balance changes, positive or negative. Count the runs of one or more neighboring entries whose total is exactly t. For [2, -2, 2] and t = 2, return 3. Assume every sum and the count fit in i64. Aim for O(n) time on average.

Exercise B: Radio buffer. Packets with positive sizes arrive in order. Find the fewest neighboring packets whose total is at least a positive capacity c, or report that none exist. For [4, 1, 2, 6] and c = 7, return 2. Then decide whether your method still works if sizes can be negative.

Exercise C: Exhibit scores. Scores arrive one at a time, with repeats. Once at least k have arrived, report the kth-largest score so far after each arrival. For k = 3 and arrivals [8, 2, 8, 5], the last two reports are 2 and 5. Keep only O(k) values. Explain what breaks if old scores can be deleted.

Exercise D: Printer capacity. A machine handles jobs of positive sizes in the given order. Each day it handles a run of neighboring jobs totaling at most capacity c, and jobs can't be split. Find the smallest capacity that finishes within d days, where 1 <= d <= n. For [3, 2, 4, 1] and d = 2, return 5. Explain your yes/no test and your search range.

Exercise E: Gallery visits. Each exhibit runs from its start time up to (not including) its end time, with start < end. Pick the most exhibits with no overlaps. For [0, 4), [1, 2), [2, 3), [3, 5), return 3. Then give each exhibit a reward, and explain whether the same rule gets the most reward.

Exercise F: Maintenance corridor. Rooms form a graph where every hallway goes both ways and has the same length. Some rooms have maintenance stations. For every room, find the fewest hallways to any station, or report that none can be reached. In the path 0-1-2-3-4 with stations at 0 and 4, return [0, 1, 2, 1, 0].

Exercise G: Cooling schedule. Each day offers a reward of zero or more, but taking one day's reward means you can't take the next day's. Find the largest total. For [4, 7, 2, 9], return 16. Then change the rule so taking a reward blocks the next two days, and work out the new recurrence.

Exercise H: Museum door. A graph has doors that need particular keys. You pick up keys at rooms and keep them. Find the fewest moves from a start room to a target. Explain why marking only the room as visited can throw away a route you need. Assume at most six different keys.

For each exercise, write down five things: a brute force, the key idea, what stays true (or the recurrence), the cost, and a counterexample to a tempting wrong approach. Getting the example right is only the start.