1A: Waffle Choppers

Consider only one dimension, we can see that we can determistics decide which row to cut. If a row is empty - it doesn’t matter!!! Either way would do

1A: Bit Party

  1. bsearch on the final answer

  2. Note that R <= C, so we can just calculate the capacity for each cashier!!!

1B: Mysterious Road Signs

  1. Every time we see a new segment, we can assume its left is the start of new segment, and keep scaning until we have more than two possible choices. Then we know it is the end, of the segment, and we need to start again. Of course, we need to try both directions

  2. large dataset can be computed with divide and conquer - just need to guess the 3 possible cases: all in the seg, left works with left, and left works with right => T(S) = 2T(S/2) + O(S) gives O(SlogS)