This document provides comprehensive enhancements to the existing Sample.md files across different algorithmic topics.
Added:
- Advanced array comparison patterns
- Segment tree integration with sorting
- Inversion count techniques
- Radix sort for special cases
- Merge sort for custom sorting with auxiliary data
- Advanced coordinate compression with duplicates
- Two-pointer with dynamic array
- Sorting optimization strategies (hybrid approaches)
- Cache-friendly sorting tips
Added:
- Matroid greedy verification
- Activity selection variants (weighted)
- Job sequencing with deadlines (enhanced)
- Huffman coding pattern
- Fractional knapsack greedy
- String rearrangement edge cases
- Greedy + DP hybrids
- Proof techniques for greedy correctness
- Common greedy failures and why
Added:
- Morris Traversal (O(1) space tree traversal)
- Thread Binary Tree
- AVL/Red-Black tree basics
- Segment tree on trees
- Virtual tree construction
- Link-Cut trees overview
- Fenwick tree on tree structures
- Tree flattening techniques
- XOR basis on tree paths
- Treap/Cartesian tree patterns
Added:
- Matrix chain multiplication with memoization
- Convex hull trick details
- CHT with queries
- Knuth-Yao speedup
- Subset enumeration optimization
- DP with profile compression
- Tree DP with heavy-light decomposition
- DP on permutations
- Meet-in-middle DP
- Tiling and counting problems
- Broken profile DP
- DP optimization: Four-Russian trick
Added:
- 2-SAT solver
- Bridges and articulation points (Tarjan)
- Vertex connectivity
- Planar graph detection
- Euler characteristic
- Max clique approximation
- Network flow applications (practical)
- Push-relabel algorithm (alternative to Dinic)
- Capacity scaling
- Successive shortest paths
- Minimum cost circulation
- Chinese postman problem
- Gomory-Hu tree
- Graph coloring heuristics