Saturday, October 22, 2022

CSES Problem Set - 3

 Chapter 8: String Algorithms

CSES - String Matching [Rolling Hash]

CSES - Word Combinations [dp, rolling hash]

CSES - Finding Borders [rolling hash]

CSES - Minimal Rotation [rolling hash, binary search, double string]

CSES - Finding Periods [rolling hash, harmonic series]

CSES - Longest Palindrome [Manacher]


Chapter 8: Geometry

CSES - Point Location Test [cross product]

CSES - Polygon Area [Polygon area]

CSES - Line Segment Intersection [cross product]

CSES - Point in Polygon [cross product, count intersections]

CSES - Polygon Lattice Points [Polygon, area, Pick's theorem, Lattice points in segment]

CSES - Minimum Euclidean Distance [Line sweeping with set]

CSES - Convex Hull [Construct convex hull, Andrew's algo]


Chapter 9: Advanced Techniques

CSES - Meet in the Middle [Meet in the middle]

CSES - Hamming Distance [Xor, bit-parallel]

CSES - Beautiful Subgrids [Bitset, bit-parallel, #pragma GCC target("popcnt")]

CSES - Reachable Nodes [TopSort, bit-parallel, #pragma GCC target("popcnt")]

CSES - Reachability Queries [SCC, TopSort, bit-parallel, #pragma GCC target("popcnt")]

CSES - Cut and Paste [Treaps]

CSES - Substring Reversals [Treaps]

CSES - Reversals and Sums [Treaps + Lazy propogation]

CSES - Necessary Roads [Bridges]

CSES - Necessary Cities [Articulation Points]

CSES - Eulerian Subgraphs [Eulerian Subgraph]

CSES - Monster Game I [dp + convex hull trick]

CSES - Monster Game II [dp + convex hull trick + binary search]