Round 60: Digit Permutation

Note that for topologic sort, after each dfs call, even if you start with a node without incoming edge, the component may not be traversed fully yet!!! A counter example is a -> b <- c. C is not touched after we did a -> b

This is not a problem will not occur if 1. the graph is a tree (only 1 node with incoming endge 0)

2. undirected, flood fill problems

3. a depends on b, i.e., b should be printed first

However, in this problme I chose a < b => a -> b, i.e., a should be printed first. This means I should reverse the orddr until the whole traverse is over!!!

To assign 0, we can just start with 1, and skip it when we reach the 0 node in the final list. Because the 0 node has no incoming edge, it will not cause conflict.

Round 60: Card Groups

This is an example of meet in the middle, a search technique I see for the first time!!!

2^40 is not too huge, but still huge enough to not apply direct brute force search. Meet in the middle will reduce complexity to around 2^20 => slightly over 1M!

Meet in the middle

Consider the each half, the combination of answer should give B0 + B1 = R0 + R1 => B0 - R0 = R1 - B1

So we iterate over all 2^20 sets of potential B0, and calculate B0 - R0, put them in a set, keeping track of min diff.

And we iterate over all 2^20 sets of potential B1, while we iterate, we look up to see if there is any potential matching ones, and then update the final answer.

Round 10: Shifted Diagonal Sum

Just calc all potential diagonals. Suppose we shift to the right by X, and down by Y

Extended question: after the X, Y shift, which two orginal diagonals become the new main diagonal? Note that the formula is different when X > Y and X < Y

Round 10: Subarray Medians

Done in O(N^2)!!!

To calculate all medians for subarrays starting at i, and online algorithm takes O(nlogn), with two heaps. So we will try an offline approach, i.e., calculate the complete picture, and then deduce parts from it.

The explanation is very confusing…

Round 9: Flip Game

Obviously, we need to change all in column 1 to 1. Two options, rows flips to 0, and then col flip, and then col flip

After that, we just do col flip as long as we get more 1s => i.e., in the original column, # of 0s < # of 1s

Note that

  1. The order of ops doesn’t matter!

  2. Each row/col will receive AT MOST one ops

  3. Suppose we flip a set of R rows and C cols, the final result is EXACTLY same as flip the complement of these 2 sets, because flipping 0 times = flipping 2 times.

  4. This means that, for every possible choice we have at flipping the first columns, we have a corresponding and equivalent chose at at NOT flipping the first coliumns, i.e., the optimal solution at not flipping the first column cases covers all other cases!!!

Round 9: Array Removal

Reverse the order of ops, and use a union find to keep track of the start of subarrays. and update the max sum as we move

Note that we can also update it with linked list approach -> but more cumbersome