372A: Counting Kangaroos is Fun (!!!)

since max answer <= n/2, we can partition the data into 2 halves, each with size n/2.

Claim: there always exists an optimal solution where all big ones are in the right half, while small ones are in the left half

  Proof: suppose we have a pair (a, b) in the same half. 

  If the other half has empty space, we can move a or b to that space, while preserving the max value

  If the other half has no empty space, and  no pair exist in the other half, then overall count > n/2, contradiction.

  Thus, there must exist a pair (c, d) in the other half, with a < b < c < d, i.e., we can just swap b, c to form (a,c), (b,d) and the optimal
value still preserves

So we can use a two pointer approach, start from one side, and search for the matching other side

567C: Geometric Progressions

So we need to find a(i), a(j), a(k) which forms a geometric sequence. Similar to the problem where you find a longest increasing subarray with one odd point, we can focus search for the middle point, the benefit is that we can break down the solution into 2 parts, we can easily bsearch on each part

475B: Strongly Connected City

Given the constraint, a DFS on each node would do in O(n^2 * m^2), but can we do better?

Consider base case: 2 rows, 2 cols, the for edeges must form a cycle (cw or ccw)

If add a a new row or col, it would do as well

Claim: as long as the outer sell forms a cw or ccw cycle, we can form a SCC

  Proof: by induction
  When we all a a new row, any new point can reach any old point, and any old point can reach any new point, and any new point can reach any
  new point