Interval, tree and bitmask DP

Rewards on a referral tree

A referral programme pays each user a reward, and the referrals form a tree: each user sits under the one who invited them. Rings of friends were referring each other and splitting the money, so there is a fraud rule: in one campaign, never reward both a user and the person who referred them. The question is the largest total that obeys the rule.

The obvious plan works by levels of the tree: reward levels 1, 3, 5 and so on, or levels 2, 4, 6 and so on, whichever pays more. Check it on a pilot city's tree of 30 users against a script that tries every set of users. There are 2³⁰ = 1,073,741,824 sets, so the script takes a long lunch to finish. The levels plan gives ₹4,100, but the true best is ₹4,650. In two places the best plan skips two levels in a row, because a user with a large reward sits right under a user with a small one.

The real tree has two lakh users, so trying every set is impossible, and the levels plan gives wrong answers. Each user has to decide using only what their own subtree can report.

Pause and predict What should each user's subtree report up to the user above?

A state that is a subtree, a range or a set

Every DP so far moved along a line: a prefix in Unit 18, two prefixes in Unit 19. Some problems have no such line. In one, the houses form a tree. In another, the order of operations changes the score. In a third, the answer depends on which items have been used, in any order.

The four questions from Unit 18 still work: define the cell in words, then find the transition, the base and the order. What changes is the answer to the first question. A cell now stands for a subtree, a range or a set.

The second half of that invariant is the hard part. If the smaller pieces can still affect each other, the table gives wrong answers, however correct the code looks.

A tree: return one answer per state

In Unit 8, each subtree returned the one value its parent needed. House Robber III is the referral tree from the opening: no house may be robbed together with its parent. One value per subtree is not enough here, because the parent's choice depends on whether the child was robbed.

So each node returns its best total for each state the parent might need: the pair (rob, skip). Robbing the node rules out robbing its children, so rob = val + left.skip + right.skip. Skipping the node leaves each child free to be robbed or not, so skip = max(left) + max(right), where max(left) is the larger number in the left child's pair. A missing child returns (0, 0), and the answer is the larger number in the root's pair.

The proof is the same as in Unit 18, with "the last choice" replaced by "the choice at this node". Every plan for a subtree either robs its root or does not. Either way, once that one fact is fixed, the two child subtrees do not affect each other, and the pair carries exactly that fact.

Binary Tree Cameras needs three states: the node has a camera, the node is watched by a child's camera, or the node is not yet watched and needs its parent to have a camera. The well-known greedy, "put a camera on any node with an unwatched child", is this DP after an exchange argument has decided the best state at every node. A camera on a leaf watches the leaf and its parent. A camera on the parent watches those two as well as the leaf's sibling and the grandparent. So a leaf never needs a camera, and each node can return a single state instead of a cost for each of the three.

A range: choose the last operation

In Burst Balloons, bursting a balloon pays its number times the numbers of its two current neighbours, and then those two neighbours become next to each other. So the order of bursts changes every later score. Trying every order takes n! steps.

Pause and predict To split a range of balloons around one balloon k, which k makes the two sides independent?

The last balloon acts as a wall between the two sides. So define dp[l][r] as the most coins you can get from bursting balloons l..r while balloons l - 1 and r + 1 are still standing. Add a balloon with value 1 at each end of the row, so that every range has a wall on both sides. Then

dp[l][r] = max over k in l..r of
dp[l][k - 1] + v[l - 1]·v[k]·v[r + 1]
+ dp[k + 1][r]

Both sides are shorter ranges, so fill the table in order of length: every range of length 1, then every range of length 2, and so on up to dp[1][n]. This is called an interval DP. It has O(n²) cells with O(n) choices each, so it takes O(n³) time in all.

Minimum Cost to Cut a Stick has the same shape. Sort the cut positions and add the stick's ends, 0 and n. The cut made first in a piece costs the length of the whole piece and leaves two separate sticks that never affect each other again. So the rule is to split on whichever operation makes the two sides independent, whether it happens first or last. If you read the cuts backwards in time, they become merges, and the last merge pays the whole length.

A set: forget the order

Shortest Path Visiting All Nodes asks for the shortest walk that visits every node of a graph with at most 12 nodes, where the walk may visit a node more than once. A walk is a sequence of nodes, and there are a great many sequences. But what a walk can still do from its current point depends only on where it stands and which nodes it has already seen. The order in which it saw them does not matter.

Pause and predict With 12 nodes, how many (node, set seen) states are there?

Every move costs 1, so plain BFS over the states finds the shortest walk. Putting every starting state (i, 1 << i) in the queue at the beginning lets the walk start at any node in a single search; this is the multi-source trick from Unit 14. If moves had different costs, you would run Dijkstra on the same states, or fill a table dp[mask][last], the cheapest way to visit exactly the nodes in mask and end at last, in order of growing masks.

How to recognise it

Ask what the answer for a piece of the input depends on. If the piece is a range and the order of operations inside it matters, split on the operation that separates the range. If the input is a tree with a choice at each node, have each node return a tuple with one value per state. If n is at most about 20 and the statement says "visit all", "assign each" or "every subset", the state contains a set.

Pause and predict Assign each of 14 workers to one of 14 tasks at the least total cost. What does a cell's state hold?

Four that only look like it

• Two strings, or a grid. The state is two prefixes, and each cell reads its neighbours, as in Unit 19. Palindromes use ranges too, but there a range reads only the range one or two shorter, never a split point. Interval DP tries every split point k.
• A tree where one value per subtree is enough. Depth, diameter and a balance check need only plain recursion, from Unit 8.
• A request to list every order or assignment. The output itself can be exponentially long, so it needs backtracking. A count or a best value over n ≤ 20 items fits a bitmask table.
• Start and end times. Merging or covering intervals is Unit 10, solved by sorting and sweeping. Interval DP is about ranges of positions in one array.

Where it bites

Pause and predict Burst Balloons on [3, 6, 2], with the table filled row by row instead of by length. The answer should be 45. What comes out?

• Splitting on the first operation when that leaves the sides affecting each other. Ask which operation keeps the two sides apart: for balloons it is the last burst, and for the stick it is the first cut.
• Scoring the last balloon with its original neighbours. When it bursts last, its neighbours are the walls, v[l - 1] and v[r + 1].
• Filling an interval table row by row. dp[k + 1][r] is in a later row and still 0, so on [3, 6, 2] the answer comes out 32 instead of 45. Fill by length.
• Returning one number per tree node when the parent's choice depends on the child's state. Return the tuple, and take the max only at the root.
• Marking visited nodes instead of visited states in a bitmask BFS. A walk may have to pass through a node twice; it is the (node, mask) state that must not repeat.
• Using a bitmask DP with n = 40. 2⁴⁰ states do not fit in memory. A small n in the constraints is the signal for a bitmask; without it, look for another structure.