Saturday, March 5, 2022

CSES Problem Set - 2

 

 Chapter 5: Range Queries

CSES - Static Range Sum Queries [prefix sum, cumulative sum]

CSES - Static Range Minimum Queries [doubling, sparse table]

CSES - Dynamic Range Sum Queries [Bit Indexed Tree/Point Set/Range Sum]

CSES - Dynamic Range Minimum Queries - Results [SegTree/Point Set/Range Min]

CSES - Range Xor Queries [SegTree/PointSet/Range Xor]

CSES - Range Update Queries [SegTree/Range Add/Point Get]

CSES - Forest Queries [2D prefix sum]

CSES - Hotel Queries [SegTree/Point Add/Range Max, Binary Search]

CSES - List Removals [BIT/Point Add/Range Sum, Binary Search]

CSES - Salary Queries [BIT/Point Add/Range Sum, Index Compression]

CSES - Prefix Sum Queries [SegTree/Point Set/Range Sum, Range Max Prefix]

CSES - Subarray Sum Queries [SegTree/Point Set/Range Sum, Range Max Prefix, Suffix, SubArray Sum]

CSES - Distinct Values Queries [BIT/Point Add/Range Sum, Count unique number in range]

CSES - Range Updates and Sums [Lazy SegTree/Range Set/Range Add/Range Sum Query]

CSES - Forest Queries II [2D BIT/Point Add/2D Range Sum Query]

CSES - Polynomial Queries [Lazy SegTree/Range Arithmetic Progress Add/Range Sum Query]

CSES - Pizzeria Queries [SegTree/Point Set/Range Min/Query Min + abs(pos[i]-cur)]

CSES - Increasing Array Queries [BIT/Point Add/Range Sum, precalc left increasing range, first left bigger index]

CSES - Range Queries and Copies [Persistent SegTree/Point Set/Range Sum]


 Chapter 6: Tree Algorithms

CSES - Subordinates [dfs, dp on tree]

CSES - Tree Matching [dfs, dp on tree]

CSES - Tree Diameter [dfs, tree diameter]

CSES - Tree Distances I [dfs, dp on tree, longest path from each node]

CSES - Tree Distances II [dp on tree-full, total paths sum from each node]

CSES - Company Queries I [binary lifting, doubling]

CSES - Company Queries II [lca, binary lifting, doubling]

CSES - Distance Queries [dfs, lca, binary lifting, doubling]

CSES - Counting Paths [imos on tree, dfs, lca, binary lifting, doubling]

CSES - Distinct Colors [dfs, dp on tree, merging]

CSES - Finding a Centroid [dfs, finding center]

CSES - Subtree Queries [BIT/Point add/Range Sum, dfs, in-order-array, subtree query]

CSES - Path Queries [SegTree/Range Add/Point Query, dfs, in-order-array, subtree query]

CSES - Fixed-Length Paths I [Centroid Decomposition, In-order-array]

CSES - Fixed-Length Paths II [Centroid Decomposition, In-order-array, range sum]

CSES - Path Queries II [Heavy-Light Decomposition] 

 Chapter 7: Mathematics

CSES - Exponentiation [modpow]

CSES - Counting Divisors [count divisors]

CSES - Exponentiation II [modpow, Fermat's theory]

CSES - Sum of Divisors [count divisors]

CSES - Divisor Analysis [module, count div, sum div, prod div]

CSES - Josephus Queries [mod, Josephus problem]

CSES - Binomial Coefficients [Binomial Coeff, Fac, Rev, nCk, nPk]

CSES - Creating Strings II [Multi-Binomial Coeff]

CSES - Distributing Apples [Binomial Coeff, Apples & Boxes]

CSES - Bracket Sequences I [Catalan number]

CSES - Christmas Party [Derangement number]

CSES - Prime Multiples [Inclusion-Exclusion, Overflow trick]

CSES - Counting Coprime Pairs [Mobius function]

CSES - Counting Necklaces [Burnside lemma, gcd, fast pow]

CSES - Counting Grids [Burnside lemma, fast pow]

CSES - Fibonacci Numbers [Matrix fast pow]

CSES - Throwing Dice [Matrix fast pow]

CSES - Graph Paths I [Matrix fast pow]

CSES - Graph Paths II [Matrix min fast pow]

CSES - Dice Probability [2D dp probability]

CSES - Candy Lottery [2D dp probability]

CSES - Moving Robots [3D dp probability/expectation]

CSES - Inversion Probability [linearity of expectation]

CSES - Stick Game [dp game]

CSES - Nim Game I [nim game]

CSES - Nim Game II [subtract game]

CSES - Stair Game [stair nim game]

CSES - Grundy's Game [dp like grundy number]

CSES - Another Game [Same move strategy]