Intro...

My competitive programming memo's and libraries...

Code formatter:
http://codeformatter.blogspot.com/

Awesome poj problem lists:
Data Structure Practice: for Collegiate Programming Contests and Education
Algorithm Design Practice for Collegiate Programming Contests and Education
https://github.com/gongzhitaao/oj/tree/master/poj
Algorithm Contest Problem Summary
http://tozangezan.hatenablog.com/entry/20111111/1320993464
セグメント木 問題集
CS 97SI
Geometry problems from POJ 
https://odan-null.hatenadiary.org/entry/20130114/1358162397

Checklist:

Start background noise

Pop Hits | Free Internet Radio | TuneIn

Set before 5min alarm

Online Timer (timeanddate.com)

brute force?

exp? sample work?

greedy?

binary search?

dp?

3999. Minimum Number of String Groups Through Transformations

 1,Problem

Minimum Number of String Groups Through Transformations - LeetCode

2.Idea

Using Booth's algorithm to find minimum cyclic shift of the given string.

3.Code

 class Solution {  
   string helper(const string &s) {  
     if(s.empty()) return "";  
     int n = s.length();  
     int i = 0, j = 1, k = 0;  
     while(i < n and j < n and k < n) {  
       int val = s[(i + k) % n] - s[(j + k) % n];  
       if(val == 0) {  
         ++k; // Characters match, extend the prefix length  
       } else {  
         if(val > 0) {  
           i += k + 1; // i's substring is lexicographically larger, shift i  
         } else {  
           j += k + 1; // j's substring is lexicographically larger, shift j  
         }  
         // Ensure i and j are evaluating different starting positions  
         if(i == j) j++;  
         k = 0; // Reset matching length  
       }  
     }  
     int mini = min(i, j);  
     return s.substr(mini) + s.substr(0, mini);  
   }  
 public:  
   int minimumGroups(vector<string>& words) {  
     unordered_set<string> groups;  
     for(string &s : words) {  
       string even = "", odd = "";  
       for(int i = 0; i < s.length(); ++i) {  
         if(i & 1) odd += s[i];  
         else even += s[i];  
       }  
       groups.insert(helper(even) + "#" + helper(odd));  
     }  
     return groups.size();  
   }  
 };  

3943. Number of Pairs After Increment

 1.Problem

Number of Pairs After Increment - LeetCode

2.Idea

Use sqrt decomposition to maintain the segment element frequency count which also supports range update

3.Code

 class Solution {  
 public:  
   vector<int> numberOfPairs(vector<int>& nums1, vector<int>& nums2, vector<vector<int>>& queries) {  
     int n = nums2.size();  
     int k = sqrt(n);  
     int N = (n+k-1)/k;  
     vector<long long>nums22(nums2.begin(), nums2.end());  
     vector<unordered_map<long long, int>>arr(N);  
     vector<long long>add(N, 0);  
     // 1. Initialize blocks  
     for(int i = 0; i < N; ++i)  
       for(int j = i*k; j < min((i+1)*k, n); ++j)  
         ++arr[i][nums2[j]];  
     vector<int>rt;   
     rt.reserve(queries.size());  
     for(auto& q : queries)  
     {  
       if(q[0] == 1) // Range Addition  
       {  
         int st = q[1], end = q[2];  
         long long val = q[3];  
         for(int i = st; i <= end; ++i)  
         {  
           int idx = i/k;  
           // Fully covered block: apply lazy tag  
           if((i % k) == 0 && i + k - 1 <= end)  
           {  
             add[idx] += val;  
             i += k-1; // Jump to the end of the block  
           }  
           else // Partially covered block: manual update  
           {  
             --arr[idx][nums22[i]];  
             // Pruning: prevent hash map bloat  
             if(arr[idx][nums22[i]] == 0) arr[idx].erase(nums22[i]);  
             nums22[i] += val;  
             ++arr[idx][nums22[i]];  
           }  
         }  
       }  
       else // Query Pairs  
       {  
         int c = 0;  
         for(auto& num : nums1)  
         {  
           for(int i = 0; i < N; ++i)  
           {  
             // Calculate required target considering the block's lazy tag  
             long long tar = q[1] - num - add[i];  
             // Use find() to avoid accidental zero-value insertions  
             if(arr[i].find(tar) != arr[i].end())  
               c += arr[i][tar];  
           }  
         }  
         rt.push_back(c);  
       }  
     }  
     return rt;  
   }  
 };  

Absurd Problems

C. Fillomino 2 
Problem - C - Codeforces

Not easy to construct the solution, but there is a nice way to solve it. 

Construction 2: Construct the region for (1,1),(2,2),…,(n,n)$(1,1),(2,2),\dots ,(n,n)$ in order. When starting at (i,i)$(i,i)$, we walk from (i,i)$(i,i)$ for x$x$ steps, where x$x$ is the number written on (i,i)$(i,i)$. For each step, if the cell to the left of your current cell is empty, we go to that cell and write x$x$ on it. Otherwise we go down and write x$x$ there.

C. Row GCD

Problem - C - Codeforces

GCD(a1+bj,…,an+bj)=GCD(a1+bj,a2−a1,…,an−a1).GCD(a1+bj,…,an+bj)=GCD(a1+bj,a2−a1,…,an−a1)

 GCD(a1+bj,…,an+bj)=GCD(a1+bj,a2−a1,…,an−a1)

 .

.

C. DMCA

Problem - P - Codeforces

digit root - keep adding number's digits until it gets less than 10

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;  
      }  
 }