Problems Base course RU

Method

bit tricks

Articles

SRT Algorithm Counting sort and radix sort Without comparisons: count the keys or split them into digits, O(n + k) and O(d·n) instead of n log n. O(n + k) and O(d·(n + b)) 2 problems DS Data structure Fenwick tree Prefix sums with updates in O(log n) in a single array: blocks as long as the lowest one bit of the index. O(log n) per prefix sum and per update 2 problems DP Technique Bitmask DP The state is a subset written in the bits of a number: an exact travelling salesman, assignments, tilings by profile. O(2ⁿ · n²) for the travelling salesman 2 problems NUM Algorithm Fast exponentiation aⁿ in O(log n) multiplications: squares over the bits of the exponent. O(log n) multiplications 2 problems TEC Technique Bit tricks A number as a set of flags: masks, the lowest set bit, counting ones and going through subsets without recursion. O(1) per operation on a word 1 problem

Problems

Addresses in order An estimate from hashes File permissions A compressed list of positions A counter going both ways How many schemata survive The puzzle bank Decoding from code lengths Lights out The decoder Who takes which order Exam days Loading in order The goods lift The snowplough

Often together

classic 4 interviews 3 contests 3 array 2 prefix sums 2 sorting 1 stable 1 trie 1 version control 1 in production 1 range queries 1 frequencies 1