357C - Heap operations

The simple greedy approach would work. I TLEed because I did not include ios_base::sync_with_stdio(false);

Consider the first invalid case we run into. Options

  1. removeMin() on empty heap,

  2. getMin() > current min on heap

  3. getMin() < current min on heap

We can fix the heap on the spot, and repeat this step, by induction, our result will be consistent.

  1. we missed an insert, the value does not matter
  
  2. we missed removal

  3. we missed insert

In contest I spent more time proving the greedy approach is optimal than writing code!

358C - Alyona and the Tree

These types of problems introduce a speical definition, so we need to focus on that definition and infer conditions out of it.

From the perspective of a node, it must be removed if path to any of its ancestor > value of this node,i.e., we need to keep track of the max path from ANY ancestor to the node itself

MaxPath(node) =  E(parent, node) +  max(0, MaxPath(parent))

Also, since we remove from leaves, we need to go from root, and remove the subtree rooted at the first bad node

To make implementation easier, instead of calculating how many are removed, we calculate how many nodes are saved, the result is N - saved. (Inclusion-exclustion principle)