May 2024
CodeForces Fenwick Tree Find the structure and pattern of taking the Fenwick tree to powers It involves stars and bars method and combinatorics, counting method. Also helpful to have understanding about how binary indexed tree or fenwick trees work. Equal XOR Segment Related to range xor queries Can precompute the xor sums just like prefix sums algorithm. Greedy you split into either 2 or 3 segments. Division + LCP (Hard Version) z-algorithm memoization binary search Trails (medium) dynamic programming matrix exponentiation Trails (hard) Associativity in matrix multiplication. BCBCBC = B(CBCB)C matrix multiplication is not commutative. Get into format where it is a 2 x 2 matrix Exact Neighbors (hard) constructive, pattern If ai = 0, then you can place rest in zig zag They are all distinct can place (1, 2, …, n) in zig zag There is no ai ≠ 0 and they are all distinct, place zig zag, but skip at first repeat Min-Fund Prison (medium) graph theor...