371D: Vessels

The idea is similar to union-find’s path compression, i.e.,we need to know the next empty ship, therefore, every time we do a pour, we can do a path compression.

Implementation-wise, the fill() should return the next possible vessel which may have the capacity, if we fill at that vessel again. This means this could the vessel itself. This is to handle the case where the fill does not cover the existing capacity=> Otherwise, we will short circuit the link , skipping the current vessel regardless of whether it can accept more

91B: Queue(!!!)

For each number, we need to find the position of the right most number that is less than the current number.

Note that min(i, n) <= min(i+1, n) for all i, and thus forms a monotonic functions. The right most one will be the highest i such that min(i,n) < target and min(i+1, n) > target

461B: Appleman and Tree(!!!)

Doing a count(v) dp seems hard, this suggests the DP state should have more granularity

Since we need tree with exactly 1 sub tree, we consider the sub problem

1. ways(v, i) = number of ways to cut tree at v, with the cut part at v has i black vertex , while the rest all have exactly 1 black vertex.
   This separate i for the root is to help us merge between child and parent

2. for each child u, consider the case if u is not included in the subtree, update ways(v, 0) and ways(v, 1)

3. for each child u, consider the case if u IS included in the subtree rooted at v after cut, updates ways(v, 0) and ways(v, 1)

4. Final answer is ways(root, 1)