Sign in to watch this lesson
Advanced - Number Theory · 4:39
Submask Enumeration and the 3ⁿ Bound
The loop s = (s - 1) & m walks every submask of a bitmask m from the largest down, at two operations per step, because the allowed bits behave like a small counter being decremented. We handle the empty submask safely, prove that looping over all masks and all their submasks costs 3ⁿ rather than 4ⁿ, and use it for the classic dynamic program that splits a set into the best teams.
You will learn
- Enumerate every submask of m with s = (s - 1) & m and explain why it visits each exactly once, in descending order
- Include the empty submask safely with the for(;;) ... if (s == 0) break form, and explain why dropping the test loops forever
- Prove that iterating over all masks and all their submasks costs 3ⁿ (three states per bit, or the sum of C(n,k)·2^k), and judge when n is small enough
- Write the partition DP over subsets, fixing the lowest element so that each split is considered once