Round 70: Min Distances

the classic shortest path relationship is that minD(a, b) = min (a, c) + min(c, b) over all cs

Note that when we can’t find c that satifies such relationships, either our graph is invalid, or a,b is direct!!!

so we just populate matrix and re-run f-w

Round 71: Binary Differences

Claim: the set must be continous

Proof: suppose we find the max diff, we can keep taking off left and right end and reduce the diff by 0, 1, or 2, as we like

so we can just find the max and min possible k value. Note that for the ease of calc, we can map f(0) = 1 and f(1) = -1

Round 71: Russian Dolls

easy to calculate # will gain by reducing to the next level, and keep track of the max # we have seen so far, we stop, when the new # >= seen

Round 72: Beautiful Matrix

only 4 possible cases

  1. swaping top row

  2. swapping bottom row

  3. swapping left col

  4. swapping right col

Round 72: Spring Cleaning

So the graph is a cycle or sunny graph. Easy to see we can clean all but 1 node. So just DFS and print it in reverse order except the last one

Round 73: Binary Isomorphism

Hard problem for me!!!