Determine Redeemable Promotion Offers from Event History

## Problem Determine which promotion offers each user may redeem at a cutoff time. Offers have an ID, an inclusive start time, an exclusive end time, and a per-user limit on active redemptions. Events record a user redeeming or unredeeming an offer. Apply all events at or before the cutoff, then return every event user's currently redeemable offers. ### Function Contract Implement `redeemable_offers(offer_ids, start_times, end_times, limits, event_users, event_offer_ids, event_times, event_actions, cutoff) -> list[list[str]]`. The four offer arrays are parallel: index `i` describes offer `offer_ids[i]`. The four event arrays are also parallel: index `j` describes one event. Times and `cutoff` are nonnegative integer UTC seconds. Each action is exactly `"redeem"` or `"unredeem"`. Return one row per distinct user appearing in `event_users`, sorted by user ID. A row begins with the user ID, followed by every offer that is active at the cutoff and whose active redemption count for that user is below its limit. Sort those offer IDs lexicographically. A user with no eligible offer is represented by a one-element row containing only the user ID. ### Constraints - `1 <= len(offer_ids) <= 2000`; offer IDs are unique nonempty ASCII strings of at most 32 characters. - `len(start_times) = len(end_times) = len(limits) = len(offer_ids)`. - `0 <= start_times[i] < end_times[i] <= 9007199254740991`. - `1 <= limits[i] <= 10^9`. - `0 <= len(event_users) <= 200000`, and all four event arrays have that length. - User IDs are nonempty ASCII strings of at most 32 characters; every event offer ID appears in `offer_ids`. - `0 <= event_times[j], cutoff <= 9007199254740991`. - Events need not be sorted. Process events with `event_times[j] <= cutoff` by `(event_times[j], j)`. - Valid input never lets an active redemption count become negative or exceed its offer limit. - The number of distinct event users multiplied by the number of offers is at most 200000. - Offer `i` is active exactly when `start_times[i] <= cutoff < end_times[i]`. ### Examples - Offers `["A","B","C"]` have starts `[0,0,50]`, ends `[100,40,100]`, and limits `[2,1,1]`. Events have users `["u1","u1","u2","u2"]`, offer IDs `["A","A","A","B"]`, times `[10,20,5,10]`, and actions `["redeem","unredeem","redeem","redeem"]`. At cutoff `60`, return `[["u1","A","C"],["u2","A","C"]]`. - An offer whose end time equals the cutoff is not returned. ```hint Aggregate by user and offer Sort the relevant event indices by time and original position, then maintain a nested active-count map. ``` ### Edge Cases - A user can unredeem and later redeem again. - Events after the cutoff have no effect. - Expired offers can remain in the count map but are not returned. - A user with no eligible offer still appears in the output.