unreasonably effective

link Dynamic Programming The optimal refueling would look like a subsequence of (start, stations, target). For each station, we can find how far we can go with different number of refuelings. Then the minimum number of refuelings that gets us to the target is the answer. Time: , space: . Greedy We refuel only if…

link Time: , space: . For a gas station, the net (gas-cost) >= 0 means we can make it to the next station. Since sum does not depend on the order of the numbers being summed up (commutativity), this also holds for a sequence of gas stations. Therefore, the sum of the nets of a…

link Blind alleys What works The best pairing for the heaviest person is the lightest person. If combining the weight of the lightest person does not work, the heaviest person must ride alone. So, we sort the weights and on each iteration try pairing the heaviest with the lightest. Time: , space: .

link As long as all indices (possibly except last index) have positive jumps, we can reach the end. Therefore, only way we may fail to reach the end is: Like the the case below: We keep improving the maximum allowed index. If current index is beyond our reach, we cannot reach the last index. Time:…

link Time: , space: . If all numbers were distinct, we could find which side of pivot is on by comparing with as below. Here, with duplicates allowed, we reduce the problem to the all-distinct case by making sure .

link Time: , space: Observations: Time: , space: .

Systematic methods in Calculus help solve huge swath of problems. On the other hand, reading through a book on Number Theory feels like every problem has been solved ad hoc, with ingenious insight, why? Guess: Something to do with how numbers are represented in human brain.