Exercise hints and answers

A, hint: compare two running totals. The difference of two prefix sums is a range's sum. Keep a hash map counting earlier prefix sums, and look up current_prefix - t before adding the current prefix. Start with the empty prefix counted once. O(n) time on average and O(n) space. In the example, the three answers are each 2 on its own and the whole ledger. A sliding window doesn't work here, because entries can be negative.

B, hint: look at how dropping the oldest packet changes the total. With positive sizes, grow the window to the right, and shrink from the left while it's big enough. Record each valid window before removing its left packet. O(n) time and O(1) extra space. The window [1, 2, 6] shrinks to [2, 6]. Negative sizes break this: [1, -1, 5] with capacity 5 shows the failure.

C, hint: which kept score is easiest for a new one to replace? Keep the largest k scores in a min-heap. Once it holds k scores, its top is the kth largest. Each arrival costs O(log k) time, with O(k) space. If any score can be deleted, a score you dropped might become the answer again, so keeping only k isn't enough.

D, hint: first check whether one given capacity works. Fill each day with as many jobs in a row as fit. That uses the fewest days for that capacity: no valid first day can end later, and the same holds for each day after. If a capacity works, every larger one does too. Search from the largest job up to the total of all jobs. Each check is O(n), so binary search on the answer costs O(n log R), where R is the number of capacities in that range. Capacity 5 allows [3, 2] and [4, 1].

E, hint: leave as much time free for later as you can. Always pick the compatible exhibit that ends earliest. Swapping this choice into any best schedule never makes it smaller, and the same holds for each later pick. Sorting dominates, at O(n log n). With rewards, the swap no longer protects the total: [0, 4) worth 100 beats three short exhibits worth 1 each. Use a DP instead: for each exhibit, compare skipping it with taking it plus the best schedule that ends before it starts.

F, hint: let every station start searching at once. Put every station in the BFS queue at distance 0. The first time BFS reaches a room gives its distance to the nearest station, because each layer is one hallway further. O(V + E) time and O(V) space, not counting the graph. Running a separate BFS from each station repeats work. Rooms with no station in their part of the graph stay unreachable.

G, hint: sort the answers by what happens on the last day. For the first i days, best(i) = max(best(i − 1), reward[i − 1] + best(i − 2)), with best(j) = 0 for j <= 0. If taking a reward blocks two days, change i − 2 to i − 3. Both take O(n) time, and O(1) space once you see what each value depends on. Greedily taking the bigger of each neighboring pair can miss a better total.

H, hint: reaching the same room twice may allow different moves next. Use (room, keys held) as the state, with the keys stored as a bitmask, and run BFS because every move costs one. Entering a room adds its key to the mask; going through a locked door needs its key. There are at most V × 2^K states. Scanning the edges for each mask gives O((V + E) × 2^K) time and O(V × 2^K) space for distances. A room you reached before picking up a key must be reachable again once you have it.

These exercises reuse familiar ideas on purpose. The point is to rebuild and justify the approach without being told the technique. Solving one reworded problem doesn't prove you can apply an idea everywhere.