## Two Allocation and Tree Problems Implement both independent parts. ### Part A - IPO Share Allocation Each bid is `[user_id, requested_shares, price, timestamp]`. Given a number of available shares, allocate them under these rules: 1. Higher-price groups are processed before lower-price groups. 2. Within one price group, order bidders by ascending timestamp, breaking ties by ascending original input index. 3. Allocate one share at a time in round-robin order among bidders in that group who still have unfilled demand. 4. Continue until the group is fully satisfied or no shares remain, then move to the next price group. Implement: ```text allocate_shares(bids, total_shares) -> list[int] ``` Return allocations aligned with the original bid order. A user may appear in more than one bid; treat bids as separate requests. Example: ```text bids = [ [10, 3, 5, 2], [20, 2, 7, 1], [30, 2, 5, 1] ] total_shares = 5 result = [1, 2, 2] ``` The price-7 bid receives two shares first. At price 5, bid 30 precedes bid 10 by timestamp, and the remaining three shares are distributed round-robin as 2 and 1. Constraints: - `0 <= len(bids) <= 10000` - Requested shares and `total_shares` are nonnegative integers. - Prices and timestamps are integers. Hints: - Sort indices rather than losing original output positions. - Group by price after ordering, and skip a bidder once its demand is satisfied. - Consider how to avoid repeatedly scanning many already satisfied bids. ### Part B - Split a Weighted Drainage Tree A rooted tree has nodes `0..n-1`. `parent[0] = -1`; for every other node, `parent[i]` is its parent. `flow[i]` is the flow at node `i`. Cut exactly one parent-child edge. The cut separates the child's entire subtree from the rest of the tree. Implement: ```text best_drainage_cut(parent, flow) -> int ``` Return the child endpoint of the edge that minimizes the absolute difference between total flow on the two resulting sides. Break ties by smaller child index. If `n < 2`, return `-1`. Example: ```text parent = [-1, 0, 0, 1, 1] flow = [1, 2, 3, 4, 2] result = 1 ``` The total is 12. Cutting above node 1 separates subtree flow 8 from remaining flow 4, a difference of 4; the other cuts are no better. Constraints: - `1 <= n <= 100000` - The parent array describes a valid rooted tree. - Flow values are nonnegative integers. Hints: - Compute every subtree sum in one postorder traversal. - For a subtree sum `s` and total `S`, the difference is `abs(S - 2s)`. ### Discussion Extensions - Analyze the complexity of both parts. - How would Part A change if allocations were weighted rather than one-share round-robin? - How would Part B answer many flow-update queries?