Module 14 · The Algorithms You Will Use Weekly: accumulate to nth_element
CP and Interview Pack: Brute Force by Permutation, Prefix and Difference Arrays, the k-th Order Statistic
ProReading
A contest problem says n <= 10. Bob spends twenty minutes hunting for a clever trick. Zara just multiplies: 10! = 3628800 orders, and checking one order takes about 10 steps. That is about 36 million steps, well inside a second. The limit was the hint, and pattern 1 is reading it.
Checking what this lesson needs for you…
What is inside CP and Interview Pack: Brute Force by Permutation, Prefix and Difference Arrays, the k-th Order Statistic
- Pattern 1: every order, when n is small
- Pattern 2: prefix sums and difference arrays
- Pattern 3: the k-th order statistic, and the median that makes sticks equal
- Ten interview questions, with model answers