# 110 選手班 - 常見技巧 ###### tags: `宜中資訊` `CP` Ccucumber12 2021.08.03 --- ## Outline - Binary Exponentiation - Prefix Sum - Discretize - Enumeration - Backtracking - Binary Search - Divide & Conquer - Sorting --- ## Binary Exponentiation ---- ### Problem - calculate $a^n\ (mod\ 10^9+7)$ - $a,n \leq 10^9$ ---- ### Naive - for loop - $O(n)$ ---- ### Binary Exponentiation - $a^{b+c} = a^b \times a^c$ - $a^{13} = a^{(1101)_2} = a^8 \times a^4 \times a^1$ - calculate $a^1,\ a^2,\ a^4,\ ...,\ a^{2^{log\ n}}$ - multiply the ones we need ---- ### Time complexity - calculate: $O(log\ n)$ - multiply: $O(log\ n)$ - total: $O(log\ n)$ ---- ### Usage - combinatorics - modular inverse - matrix multiplication --- ## Prefix Sum ---- ### Static Range Sum Queries 靜態區間總和 - 給定數列 $a_1,\ a_2,\ a_3,\ ...,\ a_N$ - sum L R: 計算 $a_L\ +\ a_{L+1}\ +\ ...\ +\ a_R$ - $N,Q \leq 10^6$ ---- #### Naive - 暴力: $O(N) \times O(Q)$ - 預處理: $O(N^2) \times O(1)$ ---- #### Prefix Sum - let $b_i = a_1\ +\ a_2\ +\ ...\ +\ a_i$ | $a$ | 1 | 2 | 3 | 4 | 5 | | --- | --- | --- | --- | --- | --- | | $b$ | 1 | 3 | 6 | 10 | 15 | ---- - $b_i = a_1\ +\ a_2\ +\ ...\ +\ a_i$ - $b_{R+1} - b_L = a_i\ +\ a_{i+1}\ +\ ...\ +\ a_R$ - = sum L R ---- - 預處理: $O(N)$ - 計算: $O(1) \times O(Q)$ - total: $O(N + Q)$ ---- ### 2D Static RSQ 靜態二維矩形總和 - 給定 $N*M$ 個數字，第 $i$ 行第 $j$ 列的數字 $a_{i,j}$ - sum $x_1\ y_1\ x_2\ y_2$ = $\sum\limits^{x_2}_{i=x_1}\sum\limits^{y_2}_{j=y_1}a_{i,j}$ - $N*M, Q \leq 10^6$ ---- #### 1D Prefix Sum - prefix sum on the longer edge - $O(min(N,M)) \times O(Q)$ ---- #### 2D Prefix Sum - $b_{i,j}=\sum\limits_{x=1}^i\sum\limits_{y=1}^ja_{x,y}$ | $a$ | | | \| | $b$ | | | | --- | --- | --- | --- | --- | --- | --- | | 1 | 2 | 3 | \| | 1 | 3 | 6 | | 4 | 5 | 6 | \| | 5 | 12 | 21 | | 7 | 8 | 9 | \| | 12 | 27 | 45 | ---- - $b_{i,j}=\sum\limits_{x=1}^i\sum\limits_{y=1}^ja_{x,y}$ - $b_{x_2,y_2} - b_{x_1-1,y_2} - b_{x_2,y_1-1} + b_{x_1-1, y_1-1} = \sum\limits_{i=x_1}^{x_2}\sum\limits_{j=y_1}^{y_2}a_{i,j}$ - = sum $x_1\ y_1\ x_2\ y_2$ ---- - 預處理: $O(NM)$ - 計算: $O(1) \times O(Q)$ - total: $O(NM + Q)$ ---- ### 3D and Higher - $b_{x_2,y_2,z_2} - b_{x_1-1,y_2,z_2} - b_{x_2, y_1-1,z_2} - b_{x_2, y_2, z_1-1}\\ + b_{x_1-1,y_1-1,z_2} + b_{x_2, y_1-1,z_1-1} + b_{x_1-1, y_2, z_1-1}\\ - b_{x_1-1, y_1-1, z_1-1}$ - 排容原理 - $D$ Dimensions: $O(N^D) + O(2^D)$ / query ---- ### Interval Partitioning Problem - $N$ people attend an activity - person $i$ enters at $S_i$ and leaves at $E_i$ - find out the most amount of people at any moment - $N \leq 10^6,\ 0 \leq S_i \leq E_i \leq 10^9$ ---- #### Difference + Prefix Sum - $+1$ at $a[S_i]$, $-1$ at $a[E_i+1]$ - do prefix sum on $a$ - find the biggest number in it - $O(N + max(E_i)) \xrightarrow{discretize} O(N)$ ---- ### Range Add then Query - given $a_1, a_2, ..., a_N$ - add $L$ $R$ $k$ : $+k$ on $a[L,L+1,...,R]$ - query $X$ : find $a[X]$ after all the add operations - add $T$ times then query $Q$ times - $N \leq 10^6, (T,Q) \leq 10^6$ ---- #### Difference - $b_i=a_i-a_{i-1},\ (b_1=a_1)$ - $a_i = \sum\limits_{x=1}^{i}b_i$ | a | 1 | 5 | 3 | 2 | -1 | 3 | | --- | --- | --- | --- | --- | --- | --- | | b | 1 | 4 | -2 | -1 | 3 | 4 | ---- - for each $i$ - $+k$ at $b[S_i]$, $-k$ at $b[E_i+1]$ - do prefix sum on $b$ - $O(N + T + Q)$ ---- ### prefix Sum $\Leftrightarrow$ Difference ---- ### Prefix Sum on Tree - query sum of a $path(i,j)$ - $b_i$ = sum of $path(root,i)$ - edge: $path(i,j) = b_i + b_j - 2 \times b_{lca(i,j)}$ - vertex: $path(i,j) = b_i + b_j - b_{fa(lca(i,j))} - b_{lca(i,j)}$ --- ## Discretize ---- ### Problem - $N$ values, $a_1,\ a_2,\ ...,\ a_N$ - $N \leq 10^6,\ -10^9 \leq a_i \leq 10^9$ ---- ### Usage - order ~~distance~~ - fit in data structures - array, BIT, segment tree, etc. - decrease space complexity - decrease time complexity ---- - shift the numbers into $[1,n]$ - hash | a | -5 | -1 | 0 | 0 | 3 | 8 | | --- | --- | --- | --- | --- | --- | --- | | b | 1 | 2 | 3 | 3 | 4 | 5 | ---- ### Implementation - sort: sort() - remove dulplicates: unique() - apply new index: lower_bound() ---- ### Implementation - `pair<i, a[i]>` - `std::map` --- ## Enumeration ---- ### Key - Target - Approach - Necessity - Order - Optimization - Data Structures / Techniques ---- ### Opposite Number - given $N$ numbers $a_1,\ a_2,\ ...,\ a_N$ - find the number of pairs S.T. $a_i+a_j=0$ - $N \leq 10^6,\ -10^9 \leq a_i \leq 10^9$ ---- #### Necessity - enumerate $i$ and $j$ - $a_j$ is fixed when we enumerate $a_i$ - enumerate $i$ and search if $j$ exist ---- #### Order - enumerate $i$ and $j$ - if $A$ is sorted, $j$ decrease when $i$ increase (monotonic) - two pointer ---- ### Palindrome - given a string $S$ - find the longest palindrome ---- #### Approach - enumerate $L$ and $R$: $O(|S|^3)$ - symmetry at center - enumerate center: $O(|S|^2)$ - Manacher: $O(|S|)$ * ---- ### Bit Enumeration - $N$ items, $a_1,\ a_2,\ ...,\ a_N$ - True / False on each item - $O(2^N)$ enumeration ---- #### Problems - Knapsack - Longest Increasing Subsequence - Interval Partitioning Problem ---- #### Implementation - bitmask ```c= for(int msk=0;msk<(1<<N); ++msk){ for(int i=0; i<N; ++i) { if((1<<i) & msk) { // do something } } } ``` ---- ### Implicit Graph - BFS / DFS - every node is a status - hash ---- #### Water Pouring Puzzle - given $N$ cups, $a_1,\ a_2,\ ...,\ a_N$ - cup $i$ has a volume of $a_i$ - find out the smallest amount of steps to create $T$ liters of water or tell that it is impossible - $N \leq 5,\ 1 \leq a_i \leq 50$ ---- #### Graph - node: status of every cup - edge: pouring water from a cup to another ---- #### node - each cup: 0~50 (6bits) - five cups: 6 * 5 = 30 bits (int) | cup | 1 | 2 | 3 | 4 | 5 | | ---- | ------ | ------ | ------ | ------ | ------ | | stat | 2 | 0 | 13 | 41 | 5 | | hash | 000010 | 000000 | 001101 | 101001 | 000101 | ---- #### edge - pour $i$ into $j$ - clear cup $i$ - fill cup $i$ ---- #### Time Complexity - status: $O(50^5)$ - transition: $O(N)$ - total: $O(N \times 50^5) \approx 1.5\times10^9$ ---- #### 圖案推盤 一張 $5\times 5$的可推動拼圖上，有 $1$ 個空格 $N$、$3$ 個拼圖 $X$ 與 $21$ 個拼圖 $O$。起始狀態如下圖所示： | O | O | O | O | O | | ----- | ----- | ----- | ----- | ----- | | **X** | **O** | **X** | **O** | **X** | | **O** | **O** | **O** | **O** | **O** | | **O** | **O** | **O** | **O** | **O** | | **O** | **O** | **O** | **O** | **N** | ---- #### 圖案推盤 - 每次可以把空格上、下、左、右的拼圖移動到空格位置，同時空格會移到該拼圖原本的位置。 - 給定另一個 $5 \times 5$ 的圖案，請問最少須移動幾次方可達到給定的圖案？ - 若無解請輸出 $0$。 ---- - node - $[1,25]$ bits: O / X - $[26,30]$ bits: **N** position - edge: move adjacent cell to **N** - Time Complexity: $O(25^4 * 4 * 25) \approx 4\times 10^7$ --- ## Backtracking ---- ### Sudoku - given a 9*9 sudoku - find the solution ---- #### Difficulty - BFS will MLE - Hard to hash - Too many nodes ---- #### Backtracking - Only store current status - DFS - Pruning ---- #### Implementation ```c= int stat[100] ; void backtrack(int x) { if(x == N){ // check return ; } for (int i=1; i<=M; ++i) { if(pruning(x, i)) { stat[x] = i ; backtrack(x + 1) ; stat[x] = 0 ; } } } ``` ---- #### Time Complexity - Spend much time calculate precisely (**X**) - Believe it will work (**O**) ---- ### Eight Queens Puzzle - a queen can attack horizontally, vertically and diagonally - find the ways to place 8 queens on a chess board that won't attack each other ---- #### checking - horizontal: $h[8]$ - vertical: $v[8]$ - diagonal: $r[15],\ l[15]$ ---- ### Pruning - spend more time checking - spend less time on unnecessary nodes - not alway better to prune - trial and error --- ## Binary Search ---- ### Key - 00000001111111 - find the transition - $f(x)$ returns 0 or 1 - Time Complexity: $O(log\ N) \times O(f(x))$ ---- #### examples - lower_bound(): $f(x) := x \geq k$ - upper_bound(): $f(x) := x > k$ ---- ### Implementation - 左閉右閉 - 左閉右開 - 位元枚舉 ---- #### 左閉右閉 $[l,r] = 000000[0]1111111$ ```c= while(l < r) { int mid = l + r >> 1 ; if(f(mid)) r = mid - 1 ; else l = mid ; } return l // l == r ``` ---- #### 左閉右開 $[l,r] = 0000000[01]111111$ ```c= while(r-l > 1) { int mid = l + r >> 1 ; if(f(mid)) r = mid ; else l = mid ; } return l // l: last 0, r: first 1 ``` ---- #### 位元枚舉 ```c= int ret = 0; for(int i=log2(N); i>=0; --i) { if(f(ret + (1<<i)) == 0) ret += (1<<i) ; } return ret ; ``` ---- ### Binary Search the Answer - 最小值最大化 - 最大值最小化 - hard to find, easy to check ---- #### APCS 2017-0304-4 基地台 - $N$ 個服務點, $K$ 個基地台 - 求最小半徑使得架設 $K$ 個基地台足以覆蓋所有服務點 - $N, K \leq 50,000$ ---- #### solution - $f(x) :=$ radius $x$ can cover - $f(x)$: $O(N)$ (greedy) - binary search $x$: $O(log\ C)$ - total: $O(Nlog\ C)$ ---- #### 圖上連通問題 - 給定帶權圖 $G$ 及兩點 $S$，$T$ - 求最小 $K$ 使得 $S$ 可走到 $T$ 在不經過大於 $K$ 的邊 - $V,E \leq 10^6$ ---- #### solution - $f(x):=$ 使用所有小於等於 $x$ 的邊可使 $S$ 與 $T$ 連通 - $f(x)$: $O(E)$ (construct new graph + dfs) - binary search x: $O(log\ C)$ - total: $O(Elog\ C)$ ---- ### Ternay Search - Binary Search: 單調函數 - Ternary Search: 單峰函數 ---- ### Implementation - Real number - Integer ---- #### Real Number - divide into three: $L\ -\ a\ -\ b\ -\ R$ - $f(a) < f(b)$: not in $[b,\ R]$ - $f(a) > f(b)$: not in $[L,\ a]$ ```c= for(int i=0; i<100; ++i) { double a = l + (r - l) / 3 ; double b = a + (r - l) / 3 ; if(f(a) < f(b)) r = b ; else l = a ; } return (l + r) / 2 ; ``` ---- #### Integer - binary search on slope - slope: -----++++++ ```c= while(r - l > 1) { int mid = r + l >> 1 ; if(f(mid) < f(mid+1)) r = mid ; else l = mid ; } return l ; ``` ---- #### Time Complexity - real number: $O(log_{\frac{3}{2}}C)=O(log\ C)\ /\ O(K)$ - integer: $O(log\ C)$ ---- #### Horizontal Line - must be answer - otherwise will **WA** --- ## Divide & Conquer ---- ### Key - divide: split into $k$ parts - recursive: solve when it is small - conquer: merge the solution ---- ### Merge Sort - divide: split in half - recursive: return when len = 1 - conquer: two pointer ---- ### Maximum Sum Subarray - $L$: MSS $[L,\ i]$ - $R$: MSS $[i,\ R]$ - $M$: MSS $[i,\ j]$ - $S$: sum $[L,\ R]$ ---- - divide: split in half - recursive: when len = 1 - $L=R=M=max(0,a[i])$ - $S=a[i]$ - conquer: - $L=max(L_l,\ S_l+L_r)$ - $R=max(R_r,\ S_r+R_l)$ - $M=max(R_l+L_r,\ M_l,\ M_r)$ - $S=S_l+S_r$ ---- ### Dynamic Maximum Sum Subarray - put $L\ R\ M\ S$ in segment tree - update: $O(log\ N)$ - query: $O(log\ N)$ ---- ### Permutation Construction - 給定 $N$ - 請構造一個 $1\sim N$ 的排列 - 使得任三個位置的數不成等差數列 ---- - divide: split in half - recursive: return when len = 1 - conquer: ??? ---- - $N/2 \rightarrow N$ - ex. $(1,3,2,4) \rightarrow [1,8]$ - $+4$: $(5,7,6,8)\ (1,3,2,4)$ - $\times 2$: $(2,6,4,8)\ (1,5,3,7)$ ---- - $(2,6,4,8)\ (1,5,3,7)$ - $(2k...)\ (2k+1...)$ - LL / RR: $2k_1-2k_2=(2k_3+1)-(2k_4+1)=2k$ - LR: $2k_1-(2k_2+1)=2k+1$ - $(2,\ 6,\ 4,\ 8,\ 1,\ 5,\ 3,\ 7)$ ---- - divide: split in half - recursive: return L part when len = 1 - conquer: double L part ---- ### Belief - Decide your function - Believe it will work ---- ### Time complexity - Draw a tree - Guess and vertify - Master Theorem * --- ## Sorting ---- ### Counting Sort - Count occurrence - Insert index ---- - a: $(3, 2, 2, 1, 6)$ | index | 1 | 2 | 3 | 4 | 5 | 6 | | ----- | --- | --- | --- | --- | --- | --- | | $b$ | 1 | 2 | 1 | 0 | 0 | 1 | - sorted: $(1,2,2,3,6)$ ---- - time complexity: $O(N+C)$ - only integer ---- ### Bucket Sort - Create buckets - Scatter into buckets - Inner sort - Collect ---- - a: $(6,28,9,14,4,7,19,11,21,26)$ | index | 1~5 | 6~10 | 11~15 | 16~20 | 21~25 | 26~30 | | ----- | --- | --------- | -------- | ----- | ----- | -------- | | $b$ | $4$ | $6, 9, 7$ | $14, 11$ | $19$ | $21$ | $28, 26$ | - sorted: $((4),(6,7,9),(11,14),(19),(21),(26,28))$ ---- - Inner Sort: Insertion sort - Time complexity: - worst: $O(N^2)$ - average: $O(N+\frac{N^2}{K} + K)$ - if $K \approx N$, $O(N+K)$ ---- ### Radix Sort - Least Significant Digit - Inner sort - move on next digit ---- - $a$: $(26, 15, 27, 35, 17, 36, 28, 16)$ - $b_1$: $(15,35,26,36,16,27,17,28)$ - $b_2$: $(15,16,17,26,27,28,35,36)$ ---- - Inner sort: Radix sort / Bucket Sort (stable) - Time complexity: $O(d(N+K))$ - $d$: digits - $K$: number of elements each digit - integer: $O(Nlog_{10}\ N)$ - Apply: Suffix Array * ---- ### Other  --- Credit - 演算法筆記 - OI wiki - Rust Algorithm Club - Sprout - Wikipedia