220B: Little Elephant and Array

Idea 1: offline band sum

First, we need to process all queries offline, and order them by the end index so that we scan from left to right by the end index.

We need to maintain the band start where a number x has exactly x times from the start to the current end. To update the band quickly, use the band-to-delta technique,i.e.,maintain a +1 at the start of the end, and -1 at the end of the band, overall contribution is the sum over the band.

This means, for each entry we see:

  1. if cnt[x] LT X, do nothing
  2. if cnt[x] GTE X, delta[previous X times occurance ]++ => start the current valid gap
  3. if cnt[x] GTE X + 1, set delta[previous x-1 times occurance]-= 2 => potential end of the current gap, and cancel the end of the previous gap
  4. if cnt[x] GTE X + 1, set delta[previous x + 1 times occurance]– => cancel the start of the previous gap

Idea 2: online brute force

Claim: if we just consider numbers cnt(x) >= x, such potential candidates count LTE 2 * sqrt(n)!!!

Proof: If x > sqrt(n), then we know we can not have more than sqrt(n) distinct x. If x LT sqrt(n), then we have at most sqrt(n) distinct choices of x

So we can just brute force calucalte the number of appearances and answer the queries online

219D: Choosing Capital for Treeland

Set orientiation as 1 as the root

For other nodes, we calculate the following things:

  • in-cost, min cost to convert when every node is reachable is from the parent, this can be done by one single DFS
  • fix parent cost: # of in-direction edges from 1 to v
  • reverse parent cost: # of reverse direction dedges from v to 1

For each candidate, the cost = cost to fix orientation 1 - fix parent cost + reverse parent cost

439D: Devu and his Brother

  1. precalc how many effort to update the min/max/values to the next value,
  2. bsearch on effort.
  3. Given the effort, we bsearch on the target number, and see if the total effort LTE effort.

472D: Design Tutorial: Inverse the Problem

Think Kruskal’s MST theorem. For each node, we know its closest neighbor must be a single edge. So we can devise a similar reverse-MST algorithm, and then DFS on each node to verify the construction