All Your Base

Insight:

  1. If digits are fixed, then the base should be as small as possible, to the point of larget digit + 1

  2. If base is fixed, then the first digit should be 1, and second 0, and third 2..

  3. Special case: only 1 digit

Pseudo code

base = the number of unique digits
create a map
first char -> 1
for i = [1, n)
  if digit does not exists in map, 
    map[char] = map.count or 0 if map.count == 1
  digit  = map[char]

translate digits into the base

Center of Mass

Consider only the 2 dimesnion case

only 1 firefly: distance toward a single line

2 fireflies:

both x and y are fully determined by time of inspection t. i.e., xC= fX(t), yC = fY(t), and both fX(t) and fY(t) are linear functions.

Therefore, yC can be resolved into a linear function of xC in a closed form. i.e., we can reduce the 2 fireflies case into our simplistic case

Same argument applies to 3 dimension case

Bribe the Prisoners

Translate the requirement: find the order of release the prisoners such that # of coins paid

Swap unknown and known: suppose we release first prisoner. It becomes 2 segments, each of which will represent the original problem

i.e.,

max(start, end) if(start == end) return 0;

releaseHead = 1 + max(start+1, end)
releaseTail = 1+ max(start, end -1)

  For i = start + 1 to end -1
    releaseMiddle = max(start, i) + max(i+2, end) + 2  

it would be the min of all choices