Round 68: Right Triangles

A variant of Fenwick tree

Round 68: Triangular Updates

For the banded updates, one technique is to convert the original array to an delta array. The main benefit is that update can be translated to exactly 2 updates instead of variable sizes => the original items will be recovered by calculating the prefix sum of the delta array.

This problem has similar idea, except that to retrieve the items, prefix sum is diagonal

Round 69: Build Correct Brackets

n^2 DP

Official solution

keep track of cost[i][j], and ways[i][j], i.e., cost/ways to make the first i chars correct out j outstanding (s, for each incoming char, we just see if we can flip or not, and update the answer as we go

Final answer is cost[N][0]

Round 69: Cover the Tree

Official solution

  1. need to find a node s.t. no subtree is dominant !!!

  2. Obiously, we should try each path to be leave to leave. This means we will have at least ceil(nl/2) pairs = # of pathes, so we can just pick two two leaves for the biggest two subtrees, form a path, and add the remaining leaves back to the pq

  3. If there is one remaining at the end, we just connect it to the root