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)

359C: Robbers’ watch

Typical complete search problem with generate-filter pattern. Because we have 2 constraints (uniqueness and value upperbound), we can generate to-be-filtered data set in 2 different ways. The basic idea is to generate according to one constraint, and then filter generated with another.

  1. generate all permutations of 0-7 with next_permutation, and check it first dn + dm digits to make sure the number formed < n and m. In the end, divide by
(7-dn-dm)! to filter out duplications. You can also use a set to maintain it, but it is more cumbersome to code

  2. generate all possible (n, m) pairs, and check this pair has no duplicate. I find this is easiler to code.