Enforce spend caps across a tree of subagents

Agent buildHard40 min

Your task

Your orchestrator agent starts subagents, and they start their own. Each agent has a spend cap in cents that covers what it and every agent under it spend. A meter sees each charge as it arrives and decides at once whether to allow it.

Write meter(parents, caps, charges) that returns one decision per charge.

Input and output:

  • parents: who started each agent, 1 to 100,000 agents. parents[0] is -1 for the orchestrator. For every other agent i, parents[i] is a smaller agent number.
  • caps: each agent's cap in cents, from 1 to 1,000,000,000,000.
  • charges: up to 100,000 pairs [agent, amount] in arrival order. amount is from 1 to 1,000,000,000 cents.
  • Return a list of booleans, one per charge: True if it is allowed.

Rules:

  • An agent's total is the sum of the allowed charges made by that agent and by every agent under it, at any depth.
  • Allow a charge only if, with it added, the total of the charging agent and the total of every agent above it each stay at or below that agent's cap.
  • A refused charge changes nothing.

Examples

meter(parents: list[int], caps: list[int], charges: list[list[int]]) -> list[bool]
Example 1
Inputmeter([-1, 0, 0, 1], [100, 60, 50, 30], [[3, 30], [3, 1], [1, 25], [2, 50], [2, 40]])
Output[True, False, True, False, True]
Example 2
Inputmeter([-1], [10], [[0, 10], [0, 1]])
Output[True, False]
Example 3
Inputmeter([-1, 0, 1], [5, 100, 100], [[2, 3], [1, 3], [0, 2], [2, 1]])
Output[True, False, True, False]

About this question

Enforce spend caps across a tree of subagents

Spend limitsSubagentsTree queries

Model answer

Free on every account

Approach

Give each agent a room: its cap minus its total. A charge fits when the smallest room on the path from the charging agent up to the orchestrator is at least the amount, and then it takes the amount from every room on that path. So the task is two operations on a path to the root: the smallest value, and subtract from all. Walking the parents does both, in as many steps as the agent is deep, and a chain of 100,000 agents with 100,000 charges makes that about 10 billion steps.

Split the tree with heavy path decomposition. For each agent, call the child with the largest subtree its heavy child. These links cut the tree into paths, and a walk to the root changes paths at most about log2(n) times, because each change to a new path at least doubles the size of the subtree you are in. Since parents[i] is smaller than i, one backward pass gives the subtree sizes with no recursion.

Give each path its own segment tree. A charge touches a prefix of each path it crosses: from the path's head down to where the walk joined it. So each tree needs only two things, the smallest of a prefix and subtract from a prefix. Each node stores the smallest room in its subtree and a pending change for that subtree. Walking up from the leaf, a right child brings in its whole left sibling. Check every path on the way up first, and refuse if any fails, so a refused charge changes nothing. Only then apply the charge to every path.

There are correct shortcuts for the walk, and none of them makes it fast enough on every tree. All the charges are known in advance, so you can cut the tree down to the charged agents and their branch points, since between two kept agents only the tightest cap matters. You can drop an agent whose cap covers everything it will ever be asked for. You can skip an agent whose cap is no lower than its parent's, and while the meter runs you can skip an agent that has at least as much room as an agent above it, because that stays true for good. Each helps on some trees. The tests include a long chain, charged deepest first, with caps just tight enough that these leave nearly all of it.

Why the obvious approaches fail

  • Walking the ancestors for every charge is correct, and it takes up to about 10 billion steps at these bounds.
  • Checking only the charging agent and the orchestrator misses a tight cap in between.
  • Adding the charge on the way up and stopping at a failure leaves part of a refused charge on the agents below. Putting it back makes that correct, and it is still a walk.
  • A Fenwick tree over an Euler tour gives one agent's total quickly, but the check needs the room of every agent on the path.

Complexity

O(n) to build, and O(log^2 n) per charge at worst, since each of about log n paths costs up to log n steps. O(n) space.

The code for this answer is in the Reference solution tab, on the plan.The code for this answer is in the Reference solution tab.

Concept guide

Related questions