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]

Educational DP Contest - Problem Tags

Contest Link:  Educational DP Contest / DP まとめコンテスト - AtCoder

First Half:

Second Half:

L - Deque (atcoder.jp) [Interval DP/区間DP]

N - Slimes (atcoder.jp) [Interval DP/区間DP]

M - Candies (atcoder.jp) [DP + Prefix Sum Optimization]

O - Matching (atcoder.jp) [Bit DP]

P - Independent Set (atcoder.jp) [DP on Trees/Simple]

V - Subtree (atcoder.jp) [DP on Trees/All around]

Q - Flowers (atcoder.jp) [DP + Range Min Query Optimization]

R - Walk (atcoder.jp) [Power of adjacency matrix]

S - Digit Sum (atcoder.jp) [Digit DP]

T - Permutation (atcoder.jp) [Insertion DP]

U - Grouping (atcoder.jp) [Bit DP with nested subset O(3^16)]

W - Intervals (atcoder.jp) [Inline DP + Segment Tree]

Z - Frog 3 (atcoder.jp) [DP + Convex Hull]

Y - Grid 2 (atcoder.jp) [DP + Inclusion-Exclusion Principle]

X - Tower (atcoder.jp) [Custom Sorting + Knapsack]

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]

CSES. Police Chase

1.Problem

https://cses.fi/problemset/task/1695/

2.Idea

Find the max flow in the graph, and recover the minimum cut from the residual graph connectivity information.

3.Source

 int n, m;  
 Int adj[555][555];  
 Int oadj[555][555];  
 Int flow[555];  
 bool V[555];  
 int pa[555];  
 vector <pi> ans;  
 bool reachable() {  
      memset(V, false, sizeof V);  
      queue<int> Q;  
      Q.push(1); V[1] = 1;  
      while (!Q.empty()) {  
           int i = Q.front(); Q.pop();  
           RREP(j, n) if (adj[i][j] && !V[j]) {  
                V[j] = 1;  
                pa[j] = i;  
                Q.push(j);  
           }  
      }  
      return V[n];  
 }  
 void solve() {  
      cin >> n >> m;  
      RREP(i, n) RREP(j, n) adj[i][j] = oadj[i][j] = 0;  
      REP(i, m) {  
           Int a, b;  
           cin >> a >> b;  
           adj[a][b]++; adj[b][a]++;  
           oadj[a][b]++; oadj[b][a]++;  
      }  
      int v, u;  
      while (reachable()) {  
           Int flow = LINF;  
           for (v = n; v != 1; v = pa[v]) {  
                u = pa[v];  
                flow = min(flow, adj[u][v]);  
           }  
           for (v = n; v != 1; v = pa[v]) {  
                u = pa[v];  
                adj[u][v] -= flow;  
                adj[v][u] += flow;  
           }  
      }  
      reachable();  
      RREP(i, n) RREP(j, n) {  
           if (V[i] && !V[j] && oadj[i][j]) ans.push_back(pi(i, j));  
      }  
      cout << ans.size() << endl;  
      for (auto x : ans) cout << x.first << " " << x.second << endl;  
 }  

CSES. Road Reparation

1.Problem

https://cses.fi/problemset/task/1675

2.Idea

Standard MST with UnionFind implementation

3.Source

 int n, m;  
 struct Edge {  
      int u, v, c;  
      bool operator < (const Edge &a)const {  
           return c < a.c;  
      }  
 } Edges[N];  
 struct UF {  
      vector<int> Parent;  
      vector<int> Size;  
      int Count;  
      void init(int n) {  
           Count = n;  
           Parent.resize(n);  
           Size.resize(n);  
           REP(i, n) {  
                make_set(i);  
           }  
      }  
      void make_set(int v) {  
           Parent[v] = v;  
           Size[v] = 1;  
      }  
      int find_set(int v) {  
           if (v == Parent[v])  
                return v;  
           return Parent[v] = find_set(Parent[v]);  
      }  
      void union_sets(int a, int b) {  
           a = find_set(a);  
           b = find_set(b);  
           if (a != b) {  
                if (Size[a] < Size[b])  
                     swap(a, b);  
                Count--;  
                Parent[b] = a;  
                Size[a] += Size[b];  
           }  
      }  
 };  
 void solve()  
 {  
      cin >> n >> m;  
      REP(i, m) {  
           cin >> Edges[i].u >> Edges[i].v >> Edges[i].c;  
           Edges[i].u--;  
           Edges[i].v--;  
      }  
      sort(Edges, Edges + m);  
      UF uf;  
      uf.init(n);  
      Int ret = 0;  
      REP(i, m) {  
           int u = Edges[i].u;  
           int v = Edges[i].v;  
           int c = Edges[i].c;  
           if (uf.find_set(u) != uf.find_set(v)) {  
                ret += c;  
                uf.union_sets(u, v);  
           }  
      }  
      if (uf.Count == 1) cout << ret << endl;  
      else cout << "IMPOSSIBLE" << endl;  
 }  

CF R767 C. Meximum Array

Problem.

https://codeforces.com/contest/1629/problem/C

Idea.

Find mex for all suffix a[i:n-1]
Split the array greedily.

Source.

 void solve()  
 {  
      int t; cin >> t;  
      while (t--) {  
           int n; cin >> n;  
           vector<int> a(n);  
           REP(i, n) cin >> a[i];  
           // find all suffix mex a[i:n-1]  
           vector<int> mex(n);  
           vector<int> cnt(n + 10, 0);  
           int now = 0;  
           for (int i = n - 1; i >= 0; i--) {  
                cnt[a[i]]++;  
                if (a[i] == now) {  
                     while (cnt[now]) now++;  
                }  
                mex[i] = now;  
           }  
           // split the array  
           vector<int> ret;  
           int cur = 0;  
           while (cur < n) {  
                ret.push_back(mex[cur]);  
                int i = cur;  
                set<int> st;  
                while (i < n) {  
                     if (a[i] < mex[cur]) st.insert(a[i]);  
                     if (st.size() == mex[cur]) break;  
                     i++;  
                }  
                cur = i + 1;  
           }  
           cout << ret.size() << endl;  
           for (int x : ret) cout << x << " "; cout << endl;  
      }  
 }  

競プロ典型 90 問

 ★2

004 - Cross Sum（★2） (atcoder.jp) [pre-processing the sum of each row and column]

022 - Cubic Cake（★2） (atcoder.jp) [find gcd=g of all side, and calculate the num of cuts to make g-sided cubes ]

024 - Select +／- One（★2） (atcoder.jp) [k should be equal or greater than sum of diffs, and reminder should be even]

027 - Sign Up Requests （★2） (atcoder.jp) [using set or map]

033 - Not Too Bright（★2） (atcoder.jp) [construction]

061 - Deck（★2） (atcoder.jp) [use two vectors in simulation]

010 - Score Sum Queries（★2） (atcoder.jp) [prefix sum]

067 - Base 8 to 9（★2） (atcoder.jp) [base converter]

055 - Select 5（★2） (atcoder.jp) [brute force, const opt]

078 - Easy Graph Problem（★2） (atcoder.jp) [tracking nodes' state in array]

★3

050 - Stair Jump（★3） (atcoder.jp) [simple linear dp]

038 - Large LCM（★3） (atcoder.jp) [lcm, gcd, formula transformation]

046 - I Love 46（★3） (atcoder.jp) [mod hash array, counting]

002 - Encyclopedia of Parentheses（★3） (atcoder.jp) [valid parentheses checker]

084 - There are two types of characters（★3） (atcoder.jp) [2 pointers, same char segments]

048 - I will not drop out（★3） (atcoder.jp) [sort by b & (a-b)]

044 - Shift and Swapping（★3） (atcoder.jp) [keep track of shift number, us it as offset]

007 - CP Classes（★3） (atcoder.jp) [upper_bound, lower_bound]

020 - Log Inequality（★3） (atcoder.jp) [long long int, log formula transformation]

032 - AtCoder Ekiden（★3） [next_permutation, set, brute-force + pruning]

014 - We Used to Sing a Song Together（★3） (atcoder.jp) [sorting]

016 - Minimum Coins（★3） (atcoder.jp) [Brute force + pruning]

076 - Cake Cut（★3） (atcoder.jp) [2 pointers, Caterpillar method]

075 - Magic For Balls（★3） (atcoder.jp) [Factorization prime divisors]

069 - Colorful Blocks 2（★3） (atcoder.jp) [Combinatoric, fast mod pow]

052 - Dice Product（★3） (atcoder.jp) [dp by the number dice]

079 - Two by Two（★3） (atcoder.jp) [greedy, flipping from top left corner]

064 - Uplift（★3） (atcoder.jp) [diff of neighbors]

082 - Counting Numbers（★3） (atcoder.jp) [calculate answer for each digit length]

018 - Statue of Chokudai（★3） (atcoder.jp) [geometry, triangle, sin, cos, arctan]

★4

034 - There are few types of elements（★4） (atcoder.jp) [2 pointers, Caterpillar method]

042 - Multiple of 9（★4） (atcoder.jp) [dp for sum of digits]

003 - Longest Circular Road（★4） (atcoder.jp) [dp on tree, dfs]

008 - AtCounter（★4） (atcoder.jp) [dp, string]

026 - Independent Set on a Tree（★4） (atcoder.jp) [dfs, centroid decomposition]

028 - Cluttered Paper（★4） (atcoder.jp) [2d line sweeping/imos]

058 - Original Calculator（★4） (atcoder.jp) [cycle detection]

070 - Plant Planning（★4） (atcoder.jp) [Manhattan dist, find median]

001 - Yokan Party（★4） (atcoder.jp) [binary search]

072 - Loop Railway Plan（★4） (atcoder.jp) [dfs on grid]

012 - Red Painting（★4） (atcoder.jp) [union find]

063 - Monochromatic Subgrid（★4） (atcoder.jp) [bit dp]

085 - Multiplication 085（★4） (atcoder.jp) [divisor factoring, backtracking]

043 - Maze Challenge with Lack of Sleep（★4） (atcoder.jp) [01-BFS]

★5

029 - Long Bricks（★5） (atcoder.jp) [Simulate by using range set/range max segtree]

039 - Tree Distance（★5） (atcoder.jp) [dp on tree, dfs]

056 - Lucky Bag（★5） (atcoder.jp) [knapsack dp, sub sum problem]

006 - Smallest Subsequence（★5） (atcoder.jp) [Greedy, String]

013 - Passing（★5） (atcoder.jp) [Dijksra from start and end node]

021 - Come Back in One Piece（★5） (atcoder.jp) [Strongly Connected Components]

060 - Chimera（★5） (atcoder.jp) [Do LIS twice from left & right side]

087 - Chokudai's Demand（★5） (atcoder.jp) [Use binary search to find upper & lower bound + Floyd-Warshall]

073 - We Need Both a and b（★5） (atcoder.jp) [dp on tree, dfs]

051 - Typical Shop（★5） (atcoder.jp) [meet-in-the-middle, binary search]

081 - Friendly Group（★5） (atcoder.jp) [2D Plot, 2D prefix sum]

036 - Max Manhattan Distance（★5） (atcoder.jp) [45 degrees rotation]

030 - K Factors（★5） (atcoder.jp) [Sieve Of Eratosthenes, prime factoring]

037 - Don't Leave the Spice（★5） (atcoder.jp) [Knapsack like dp optimized by RangeMax SegTree]

066 - Various Arrays（★5） (atcoder.jp) [Linearity of expectation, probability]

086 - Snuke's Favorite Arrays（★5） (atcoder.jp) [Bit partitioning, combinatorics, bit-brute force]

068 - Paired Information（★5） (atcoder.jp) [UnionFind, Set, Pre-processing queries]

★6

019 - Pick Two（★6） (atcoder.jp) [range dp, interval dp]

045 - Simple Grouping（★6） (atcoder.jp) [bitDP, nested subset loop O(3^n)]

062 - Paint All（★6） (atcoder.jp) [Simulate in reverse order of operations]

083 - Colorful Graph（★6） (atcoder.jp) [Sqrt decomposotion, split deg>=B, deg<B nodes]

054 - Takahashi Number（★6） (atcoder.jp) [Reduce edge number by changing graph]

080 - Let's Share Bit（★6） (atcoder.jp) [Combinatorics, inclusion & exclusion principle, bit operations]

015 - Don't be too close（★6） (atcoder.jp) [Combinatorics, nCk, Harmonic series = O(logN)]

011 - Gravy Jobs（★6） (atcoder.jp) [dp[i][j] - i days and j jobs ans, process jobs in deadline order]

031 - VS AtCoder（★6） [grundy, dp[i][j] - i blue & j white state grundy number]

088 - Similar but Different Ways（★6） (atcoder.jp) [Pigeonhole Principle, dfs + pruning]

009 - Three Point Angle（★6） (atcoder.jp) [drift angle, atan2, geometry]

049 - Flip Digits 2（★6） (atcoder.jp) [Interval Flipping, converting to graph, MST, UnionFind]

057 - Flip Flap（★6） (atcoder.jp) [Matrix rank, Gaussian method, Elimination method]

074 - ABC String 2（★6） (atcoder.jp) [Ad-hoc, Experiment, Potential, Semi-Invariant, 2^60=10^18]

★7

023 - Avoid War（★7） (atcoder.jp) [BitDP, Profiling, State Elimination]

077 - Planes on a 2D Plane（★7） (atcoder.jp) [Max Flow, Bipartite max matching, Find match]

047 - Monochromatic Diagonal（★7） (atcoder.jp) [String modification RGB->012, Rolling-hash]

005 - Restricted Digits（★7） (atcoder.jp) [Digit DP, doubling, pow matrix]

017 - Crossing Segments（★7） (atcoder.jp) [BIT, counting left/right ends]

089 - Partitions and Inversions（★7） (atcoder.jp) [DP, 2 pointers, BIT, index compression]

059 - Many Graph Queries（★7） (atcoder.jp) [DP, x64 faster bit dp]

041 - Piles in AtCoder Farm（★7） [Geometry, Pick's theorem - Wikipedia]

053 - Discrete Dowsing（★7） (atcoder.jp) [Golden-section search - Wikipedia]

025 - Digit Product Equation（★7） (atcoder.jp) [dfs, prime divisors, brute-force]

035 - Preserve Connectivity（★7） (atcoder.jp) [Euler tour, lca, dfs, auxillary tree]