376 lines
26 KiB
TeX
376 lines
26 KiB
TeX
\babel@toc {english}{}
|
||
\contentsline {chapter}{Preface}{ix}{chapter*.2}%
|
||
\contentsline {part}{I\hspace {1em}Basic techniques}{1}{part.1}%
|
||
\contentsline {chapter}{\numberline {1}Introduction}{3}{chapter.1}%
|
||
\contentsline {section}{\numberline {1.1}Programming languages}{3}{section.1.1}%
|
||
\contentsline {subsubsection}{C++ code template}{4}{section.1.1}%
|
||
\contentsline {section}{\numberline {1.2}Input and output}{4}{section.1.2}%
|
||
\contentsline {section}{\numberline {1.3}Working with numbers}{6}{section.1.3}%
|
||
\contentsline {subsubsection}{Integers}{6}{section.1.3}%
|
||
\contentsline {subsubsection}{Modular arithmetic}{6}{lstnumber.-14.3}%
|
||
\contentsline {subsubsection}{Floating point numbers}{7}{lstnumber.-16.2}%
|
||
\contentsline {section}{\numberline {1.4}Shortening code}{8}{section.1.4}%
|
||
\contentsline {subsubsection}{Type names}{8}{section.1.4}%
|
||
\contentsline {subsubsection}{Macros}{9}{lstnumber.-23.2}%
|
||
\contentsline {section}{\numberline {1.5}Mathematics}{10}{section.1.5}%
|
||
\contentsline {subsubsection}{Sum formulas}{10}{section.1.5}%
|
||
\contentsline {subsubsection}{Set theory}{12}{section.1.5}%
|
||
\contentsline {subsubsection}{Logic}{13}{section.1.5}%
|
||
\contentsline {subsubsection}{Functions}{13}{section.1.5}%
|
||
\contentsline {subsubsection}{Logarithms}{14}{section.1.5}%
|
||
\contentsline {section}{\numberline {1.6}Contests and resources}{15}{section.1.6}%
|
||
\contentsline {subsubsection}{IOI}{15}{section.1.6}%
|
||
\contentsline {subsubsection}{ICPC}{15}{section.1.6}%
|
||
\contentsline {subsubsection}{Online contests}{16}{section.1.6}%
|
||
\contentsline {subsubsection}{Books}{16}{section.1.6}%
|
||
\contentsline {chapter}{\numberline {2}Time complexity}{17}{chapter.2}%
|
||
\contentsline {section}{\numberline {2.1}Calculation rules}{17}{section.2.1}%
|
||
\contentsline {section}{\numberline {2.2}Complexity classes}{20}{section.2.2}%
|
||
\contentsline {section}{\numberline {2.3}Estimating efficiency}{21}{section.2.3}%
|
||
\contentsline {section}{\numberline {2.4}Maximum subarray sum}{21}{section.2.4}%
|
||
\contentsline {subsubsection}{Algorithm 1}{22}{section.2.4}%
|
||
\contentsline {subsubsection}{Algorithm 2}{22}{lstnumber.-46.11}%
|
||
\contentsline {subsubsection}{Algorithm 3}{23}{lstnumber.-47.9}%
|
||
\contentsline {subsubsection}{Efficiency comparison}{23}{lstnumber.-48.6}%
|
||
\contentsline {chapter}{\numberline {3}Sorting}{25}{chapter.3}%
|
||
\contentsline {section}{\numberline {3.1}Sorting theory}{25}{section.3.1}%
|
||
\contentsline {subsubsection}{$O(n^2)$ algorithms}{25}{section.3.1}%
|
||
\contentsline {subsubsection}{Inversions}{26}{lstnumber.-49.7}%
|
||
\contentsline {subsubsection}{$O(n \qopname \relax o{log}n)$ algorithms}{27}{lstnumber.-49.7}%
|
||
\contentsline {subsubsection}{Sorting lower bound}{28}{Item.7}%
|
||
\contentsline {subsubsection}{Counting sort}{28}{Item.7}%
|
||
\contentsline {section}{\numberline {3.2}Sorting in C++}{29}{section.3.2}%
|
||
\contentsline {subsubsection}{Comparison operators}{30}{lstnumber.-53.2}%
|
||
\contentsline {subsubsection}{User-defined structs}{30}{lstnumber.-55.5}%
|
||
\contentsline {subsubsection}{Comparison functions}{31}{lstnumber.-56.7}%
|
||
\contentsline {section}{\numberline {3.3}Binary search}{31}{section.3.3}%
|
||
\contentsline {subsubsection}{Method 1}{32}{lstnumber.-59.5}%
|
||
\contentsline {subsubsection}{Method 2}{32}{lstnumber.-60.9}%
|
||
\contentsline {subsubsection}{C++ functions}{33}{lstnumber.-61.7}%
|
||
\contentsline {subsubsection}{Finding the smallest solution}{33}{lstnumber.-64.2}%
|
||
\contentsline {subsubsection}{Finding the maximum value}{34}{lstnumber.-65.5}%
|
||
\contentsline {chapter}{\numberline {4}Data structures}{35}{chapter.4}%
|
||
\contentsline {section}{\numberline {4.1}Dynamic arrays}{35}{section.4.1}%
|
||
\contentsline {section}{\numberline {4.2}Set structures}{37}{section.4.2}%
|
||
\contentsline {section}{\numberline {4.3}Map structures}{38}{section.4.3}%
|
||
\contentsline {section}{\numberline {4.4}Iterators and ranges}{39}{section.4.4}%
|
||
\contentsline {subsubsection}{Working with ranges}{39}{section.4.4}%
|
||
\contentsline {subsubsection}{Set iterators}{40}{lstnumber.-87.3}%
|
||
\contentsline {section}{\numberline {4.5}Other structures}{41}{section.4.5}%
|
||
\contentsline {subsubsection}{Bitset}{41}{section.4.5}%
|
||
\contentsline {subsubsection}{Deque}{42}{lstnumber.-98.5}%
|
||
\contentsline {subsubsection}{Stack}{42}{lstnumber.-99.6}%
|
||
\contentsline {subsubsection}{Queue}{43}{lstnumber.-100.7}%
|
||
\contentsline {subsubsection}{Priority queue}{43}{lstnumber.-101.7}%
|
||
\contentsline {subsubsection}{Policy-based data structures}{44}{lstnumber.-103.1}%
|
||
\contentsline {section}{\numberline {4.6}Comparison to sorting}{44}{section.4.6}%
|
||
\contentsline {subsubsection}{Algorithm 1}{45}{section.4.6}%
|
||
\contentsline {subsubsection}{Algorithm 2}{45}{section.4.6}%
|
||
\contentsline {subsubsection}{Algorithm 3}{45}{section.4.6}%
|
||
\contentsline {subsubsection}{Efficiency comparison}{45}{section.4.6}%
|
||
\contentsline {chapter}{\numberline {5}Complete search}{47}{chapter.5}%
|
||
\contentsline {section}{\numberline {5.1}Generating subsets}{47}{section.5.1}%
|
||
\contentsline {subsubsection}{Method 1}{47}{section.5.1}%
|
||
\contentsline {subsubsection}{Method 2}{48}{lstnumber.-110.10}%
|
||
\contentsline {section}{\numberline {5.2}Generating permutations}{49}{section.5.2}%
|
||
\contentsline {subsubsection}{Method 1}{49}{section.5.2}%
|
||
\contentsline {subsubsection}{Method 2}{49}{lstnumber.-113.14}%
|
||
\contentsline {section}{\numberline {5.3}Backtracking}{50}{section.5.3}%
|
||
\contentsline {section}{\numberline {5.4}Pruning the search}{51}{section.5.4}%
|
||
\contentsline {subsubsection}{Basic algorithm}{52}{section.5.4}%
|
||
\contentsline {subsubsection}{Optimization 1}{52}{section.5.4}%
|
||
\contentsline {subsubsection}{Optimization 2}{53}{section.5.4}%
|
||
\contentsline {subsubsection}{Optimization 3}{53}{section.5.4}%
|
||
\contentsline {subsubsection}{Optimization 4}{53}{section.5.4}%
|
||
\contentsline {section}{\numberline {5.5}Meet in the middle}{54}{section.5.5}%
|
||
\contentsline {chapter}{\numberline {6}Greedy algorithms}{57}{chapter.6}%
|
||
\contentsline {section}{\numberline {6.1}Coin problem}{57}{section.6.1}%
|
||
\contentsline {subsubsection}{Greedy algorithm}{57}{section.6.1}%
|
||
\contentsline {subsubsection}{General case}{58}{section.6.1}%
|
||
\contentsline {section}{\numberline {6.2}Scheduling}{58}{section.6.2}%
|
||
\contentsline {section}{\numberline {6.3}Tasks and deadlines}{60}{section.6.3}%
|
||
\contentsline {section}{\numberline {6.4}Minimizing sums}{61}{section.6.4}%
|
||
\contentsline {subsubsection}{Case $c=1$}{61}{section.6.4}%
|
||
\contentsline {subsubsection}{Case $c=2$}{61}{section.6.4}%
|
||
\contentsline {section}{\numberline {6.5}Data compression}{62}{section.6.5}%
|
||
\contentsline {subsubsection}{Huffman coding}{63}{section.6.5}%
|
||
\contentsline {chapter}{\numberline {7}Dynamic programming}{65}{chapter.7}%
|
||
\contentsline {section}{\numberline {7.1}Coin problem}{65}{section.7.1}%
|
||
\contentsline {subsubsection}{Recursive formulation}{66}{section.7.1}%
|
||
\contentsline {subsubsection}{Using memoization}{67}{lstnumber.-116.9}%
|
||
\contentsline {subsubsection}{Constructing a solution}{68}{lstnumber.-119.9}%
|
||
\contentsline {subsubsection}{Counting the number of solutions}{69}{lstnumber.-122.4}%
|
||
\contentsline {section}{\numberline {7.2}Longest increasing subsequence}{70}{section.7.2}%
|
||
\contentsline {section}{\numberline {7.3}Paths in a grid}{71}{section.7.3}%
|
||
\contentsline {section}{\numberline {7.4}Knapsack problems}{72}{section.7.4}%
|
||
\contentsline {section}{\numberline {7.5}Edit distance}{74}{section.7.5}%
|
||
\contentsline {section}{\numberline {7.6}Counting tilings}{75}{section.7.6}%
|
||
\contentsline {chapter}{\numberline {8}Amortized analysis}{77}{chapter.8}%
|
||
\contentsline {section}{\numberline {8.1}Two pointers method}{77}{section.8.1}%
|
||
\contentsline {subsubsection}{Subarray sum}{77}{section.8.1}%
|
||
\contentsline {subsubsection}{2SUM problem}{78}{section.8.1}%
|
||
\contentsline {section}{\numberline {8.2}Nearest smaller elements}{79}{section.8.2}%
|
||
\contentsline {section}{\numberline {8.3}Sliding window minimum}{81}{section.8.3}%
|
||
\contentsline {chapter}{\numberline {9}Range queries}{83}{chapter.9}%
|
||
\contentsline {section}{\numberline {9.1}Static array queries}{84}{section.9.1}%
|
||
\contentsline {subsubsection}{Sum queries}{84}{section.9.1}%
|
||
\contentsline {subsubsection}{Minimum queries}{85}{section.9.1}%
|
||
\contentsline {section}{\numberline {9.2}Binary indexed tree}{86}{section.9.2}%
|
||
\contentsline {subsubsection}{Structure}{86}{section.9.2}%
|
||
\contentsline {subsubsection}{Implementation}{88}{section.9.2}%
|
||
\contentsline {section}{\numberline {9.3}Segment tree}{89}{section.9.3}%
|
||
\contentsline {subsubsection}{Structure}{89}{section.9.3}%
|
||
\contentsline {subsubsection}{Implementation}{90}{section.9.3}%
|
||
\contentsline {subsubsection}{Other queries}{92}{lstnumber.-135.7}%
|
||
\contentsline {section}{\numberline {9.4}Additional techniques}{93}{section.9.4}%
|
||
\contentsline {subsubsection}{Index compression}{93}{section.9.4}%
|
||
\contentsline {subsubsection}{Range updates}{93}{section.9.4}%
|
||
\contentsline {chapter}{\numberline {10}Bit manipulation}{95}{chapter.10}%
|
||
\contentsline {section}{\numberline {10.1}Bit representation}{95}{section.10.1}%
|
||
\contentsline {section}{\numberline {10.2}Bit operations}{96}{section.10.2}%
|
||
\contentsline {subsubsection}{And operation}{96}{section.10.2}%
|
||
\contentsline {subsubsection}{Or operation}{96}{section.10.2}%
|
||
\contentsline {subsubsection}{Xor operation}{97}{section.10.2}%
|
||
\contentsline {subsubsection}{Not operation}{97}{section.10.2}%
|
||
\contentsline {subsubsection}{Bit shifts}{97}{section.10.2}%
|
||
\contentsline {subsubsection}{Applications}{97}{section.10.2}%
|
||
\contentsline {section}{\numberline {10.3}Representing sets}{98}{section.10.3}%
|
||
\contentsline {subsubsection}{Set implementation}{98}{section.10.3}%
|
||
\contentsline {subsubsection}{Set operations}{99}{lstnumber.-141.4}%
|
||
\contentsline {subsubsection}{Iterating through subsets}{99}{lstnumber.-142.4}%
|
||
\contentsline {section}{\numberline {10.4}Bit optimizations}{100}{section.10.4}%
|
||
\contentsline {subsubsection}{Hamming distances}{100}{section.10.4}%
|
||
\contentsline {subsubsection}{Counting subgrids}{101}{lstnumber.-147.3}%
|
||
\contentsline {section}{\numberline {10.5}Dynamic programming}{102}{section.10.5}%
|
||
\contentsline {subsubsection}{Optimal selection}{102}{section.10.5}%
|
||
\contentsline {subsubsection}{From permutations to subsets}{103}{lstnumber.-152.11}%
|
||
\contentsline {subsubsection}{Counting subsets}{105}{lstnumber.-155.18}%
|
||
\contentsline {part}{II\hspace {1em}Graph algorithms}{107}{part.2}%
|
||
\contentsline {chapter}{\numberline {11}Basics of graphs}{109}{chapter.11}%
|
||
\contentsline {section}{\numberline {11.1}Graph terminology}{109}{section.11.1}%
|
||
\contentsline {subsubsection}{Connectivity}{110}{section.11.1}%
|
||
\contentsline {subsubsection}{Edge directions}{110}{section.11.1}%
|
||
\contentsline {subsubsection}{Edge weights}{111}{section.11.1}%
|
||
\contentsline {subsubsection}{Neighbors and degrees}{111}{section.11.1}%
|
||
\contentsline {subsubsection}{Colorings}{112}{section.11.1}%
|
||
\contentsline {subsubsection}{Simplicity}{112}{section.11.1}%
|
||
\contentsline {section}{\numberline {11.2}Graph representation}{113}{section.11.2}%
|
||
\contentsline {subsubsection}{Adjacency list representation}{113}{section.11.2}%
|
||
\contentsline {subsubsection}{Adjacency matrix representation}{114}{lstnumber.-163.3}%
|
||
\contentsline {subsubsection}{Edge list representation}{115}{lstnumber.-164.1}%
|
||
\contentsline {chapter}{\numberline {12}Graph traversal}{117}{chapter.12}%
|
||
\contentsline {section}{\numberline {12.1}Depth-first search}{117}{section.12.1}%
|
||
\contentsline {section}{\numberline {12.2}Breadth-first search}{119}{section.12.2}%
|
||
\contentsline {section}{\numberline {12.3}Applications}{121}{section.12.3}%
|
||
\contentsline {subsubsection}{Connectivity check}{121}{section.12.3}%
|
||
\contentsline {subsubsection}{Finding cycles}{121}{section.12.3}%
|
||
\contentsline {subsubsection}{Bipartiteness check}{122}{section.12.3}%
|
||
\contentsline {chapter}{\numberline {13}Shortest paths}{123}{chapter.13}%
|
||
\contentsline {section}{\numberline {13.1}Bellman–Ford algorithm}{123}{section.13.1}%
|
||
\contentsline {subsubsection}{Example}{123}{section.13.1}%
|
||
\contentsline {subsubsection}{Implementation}{125}{section.13.1}%
|
||
\contentsline {subsubsection}{Negative cycles}{125}{lstnumber.-174.9}%
|
||
\contentsline {subsubsection}{SPFA algorithm}{126}{lstnumber.-174.9}%
|
||
\contentsline {section}{\numberline {13.2}Dijkstra's algorithm}{126}{section.13.2}%
|
||
\contentsline {subsubsection}{Example}{126}{section.13.2}%
|
||
\contentsline {subsubsection}{Negative edges}{128}{section.13.2}%
|
||
\contentsline {subsubsection}{Implementation}{128}{section.13.2}%
|
||
\contentsline {section}{\numberline {13.3}Floyd–Warshall algorithm}{129}{section.13.3}%
|
||
\contentsline {subsubsection}{Example}{129}{section.13.3}%
|
||
\contentsline {subsubsection}{Implementation}{131}{section.13.3}%
|
||
\contentsline {chapter}{\numberline {14}Tree algorithms}{133}{chapter.14}%
|
||
\contentsline {section}{\numberline {14.1}Tree traversal}{134}{section.14.1}%
|
||
\contentsline {subsubsection}{Dynamic programming}{134}{lstnumber.-179.1}%
|
||
\contentsline {section}{\numberline {14.2}Diameter}{135}{section.14.2}%
|
||
\contentsline {subsubsection}{Algorithm 1}{135}{section.14.2}%
|
||
\contentsline {subsubsection}{Algorithm 2}{136}{section.14.2}%
|
||
\contentsline {section}{\numberline {14.3}All longest paths}{137}{section.14.3}%
|
||
\contentsline {section}{\numberline {14.4}Binary trees}{139}{section.14.4}%
|
||
\contentsline {chapter}{\numberline {15}Spanning trees}{141}{chapter.15}%
|
||
\contentsline {section}{\numberline {15.1}Kruskal's algorithm}{142}{section.15.1}%
|
||
\contentsline {subsubsection}{Example}{142}{section.15.1}%
|
||
\contentsline {subsubsection}{Why does this work?}{144}{section.15.1}%
|
||
\contentsline {subsubsection}{Implementation}{145}{section.15.1}%
|
||
\contentsline {section}{\numberline {15.2}Union-find structure}{145}{section.15.2}%
|
||
\contentsline {subsubsection}{Structure}{145}{section.15.2}%
|
||
\contentsline {subsubsection}{Implementation}{146}{section.15.2}%
|
||
\contentsline {section}{\numberline {15.3}Prim's algorithm}{147}{section.15.3}%
|
||
\contentsline {subsubsection}{Example}{147}{section.15.3}%
|
||
\contentsline {subsubsection}{Implementation}{148}{section.15.3}%
|
||
\contentsline {chapter}{\numberline {16}Directed graphs}{149}{chapter.16}%
|
||
\contentsline {section}{\numberline {16.1}Topological sorting}{149}{section.16.1}%
|
||
\contentsline {subsubsection}{Algorithm}{150}{section.16.1}%
|
||
\contentsline {subsubsection}{Example 1}{150}{section.16.1}%
|
||
\contentsline {subsubsection}{Example 2}{151}{section.16.1}%
|
||
\contentsline {section}{\numberline {16.2}Dynamic programming}{151}{section.16.2}%
|
||
\contentsline {subsubsection}{Counting the number of paths}{152}{section.16.2}%
|
||
\contentsline {subsubsection}{Extending Dijkstra's algorithm}{153}{section.16.2}%
|
||
\contentsline {subsubsection}{Representing problems as graphs}{153}{section.16.2}%
|
||
\contentsline {section}{\numberline {16.3}Successor paths}{154}{section.16.3}%
|
||
\contentsline {section}{\numberline {16.4}Cycle detection}{155}{section.16.4}%
|
||
\contentsline {subsubsection}{Floyd's algorithm}{156}{section.16.4}%
|
||
\contentsline {chapter}{\numberline {17}Strong connectivity}{157}{chapter.17}%
|
||
\contentsline {section}{\numberline {17.1}Kosaraju's algorithm}{158}{section.17.1}%
|
||
\contentsline {subsubsection}{Search 1}{158}{section.17.1}%
|
||
\contentsline {subsubsection}{Search 2}{159}{section.17.1}%
|
||
\contentsline {section}{\numberline {17.2}2SAT problem}{160}{section.17.2}%
|
||
\contentsline {chapter}{\numberline {18}Tree queries}{163}{chapter.18}%
|
||
\contentsline {section}{\numberline {18.1}Finding ancestors}{163}{section.18.1}%
|
||
\contentsline {section}{\numberline {18.2}Subtrees and paths}{164}{section.18.2}%
|
||
\contentsline {subsubsection}{Subtree queries}{165}{section.18.2}%
|
||
\contentsline {subsubsection}{Path queries}{166}{section.18.2}%
|
||
\contentsline {section}{\numberline {18.3}Lowest common ancestor}{167}{section.18.3}%
|
||
\contentsline {subsubsection}{Method 1}{167}{section.18.3}%
|
||
\contentsline {subsubsection}{Method 2}{168}{section.18.3}%
|
||
\contentsline {subsubsection}{Distances of nodes}{169}{section.18.3}%
|
||
\contentsline {section}{\numberline {18.4}Offline algorithms}{170}{section.18.4}%
|
||
\contentsline {subsubsection}{Merging data structures}{170}{section.18.4}%
|
||
\contentsline {subsubsection}{Lowest common ancestors}{171}{lstnumber.-189.1}%
|
||
\contentsline {chapter}{\numberline {19}Paths and circuits}{173}{chapter.19}%
|
||
\contentsline {section}{\numberline {19.1}Eulerian paths}{173}{section.19.1}%
|
||
\contentsline {subsubsection}{Existence}{174}{section.19.1}%
|
||
\contentsline {subsubsection}{Hierholzer's algorithm}{175}{section.19.1}%
|
||
\contentsline {subsubsection}{Example}{176}{section.19.1}%
|
||
\contentsline {section}{\numberline {19.2}Hamiltonian paths}{177}{section.19.2}%
|
||
\contentsline {subsubsection}{Existence}{177}{section.19.2}%
|
||
\contentsline {subsubsection}{Construction}{178}{section.19.2}%
|
||
\contentsline {section}{\numberline {19.3}De Bruijn sequences}{178}{section.19.3}%
|
||
\contentsline {section}{\numberline {19.4}Knight's tours}{179}{section.19.4}%
|
||
\contentsline {subsubsection}{Warnsdorf's rule}{179}{section.19.4}%
|
||
\contentsline {chapter}{\numberline {20}Flows and cuts}{181}{chapter.20}%
|
||
\contentsline {subsubsection}{Maximum flow}{181}{chapter.20}%
|
||
\contentsline {subsubsection}{Minimum cut}{182}{chapter.20}%
|
||
\contentsline {section}{\numberline {20.1}Ford–Fulkerson algorithm}{182}{section.20.1}%
|
||
\contentsline {subsubsection}{Algorithm description}{183}{section.20.1}%
|
||
\contentsline {subsubsection}{Finding paths}{184}{section.20.1}%
|
||
\contentsline {subsubsection}{Minimum cuts}{185}{section.20.1}%
|
||
\contentsline {section}{\numberline {20.2}Disjoint paths}{186}{section.20.2}%
|
||
\contentsline {subsubsection}{Edge-disjoint paths}{186}{section.20.2}%
|
||
\contentsline {subsubsection}{Node-disjoint paths}{186}{section.20.2}%
|
||
\contentsline {section}{\numberline {20.3}Maximum matchings}{187}{section.20.3}%
|
||
\contentsline {subsubsection}{Finding maximum matchings}{188}{section.20.3}%
|
||
\contentsline {subsubsection}{Hall's theorem}{189}{section.20.3}%
|
||
\contentsline {subsubsection}{Kőnig's theorem}{189}{section.20.3}%
|
||
\contentsline {section}{\numberline {20.4}Path covers}{190}{section.20.4}%
|
||
\contentsline {subsubsection}{Node-disjoint path cover}{191}{section.20.4}%
|
||
\contentsline {subsubsection}{General path cover}{192}{section.20.4}%
|
||
\contentsline {subsubsection}{Dilworth's theorem}{193}{section.20.4}%
|
||
\contentsline {part}{III\hspace {1em}Advanced topics}{195}{part.3}%
|
||
\contentsline {chapter}{\numberline {21}Number theory}{197}{chapter.21}%
|
||
\contentsline {section}{\numberline {21.1}Primes and factors}{197}{section.21.1}%
|
||
\contentsline {subsubsection}{Number of primes}{198}{section.21.1}%
|
||
\contentsline {subsubsection}{Density of primes}{198}{section.21.1}%
|
||
\contentsline {subsubsection}{Conjectures}{199}{section.21.1}%
|
||
\contentsline {subsubsection}{Basic algorithms}{199}{section.21.1}%
|
||
\contentsline {subsubsection}{Sieve of Eratosthenes}{200}{lstnumber.-191.11}%
|
||
\contentsline {subsubsection}{Euclid's algorithm}{200}{lstnumber.-192.6}%
|
||
\contentsline {subsubsection}{Euler's totient function}{201}{lstnumber.-193.4}%
|
||
\contentsline {section}{\numberline {21.2}Modular arithmetic}{201}{section.21.2}%
|
||
\contentsline {subsubsection}{Modular exponentiation}{202}{section.21.2}%
|
||
\contentsline {subsubsection}{Fermat's theorem and Euler's theorem}{202}{lstnumber.-194.7}%
|
||
\contentsline {subsubsection}{Modular inverse}{202}{lstnumber.-194.7}%
|
||
\contentsline {subsubsection}{Computer arithmetic}{203}{lstnumber.-194.7}%
|
||
\contentsline {section}{\numberline {21.3}Solving equations}{204}{section.21.3}%
|
||
\contentsline {subsubsection}{Chinese remainder theorem}{205}{section.21.3}%
|
||
\contentsline {section}{\numberline {21.4}Other results}{205}{section.21.4}%
|
||
\contentsline {subsubsection}{Lagrange's theorem}{205}{section.21.4}%
|
||
\contentsline {subsubsection}{Zeckendorf's theorem}{206}{section.21.4}%
|
||
\contentsline {subsubsection}{Pythagorean triples}{206}{section.21.4}%
|
||
\contentsline {subsubsection}{Wilson's theorem}{206}{section.21.4}%
|
||
\contentsline {chapter}{\numberline {22}Combinatorics}{207}{chapter.22}%
|
||
\contentsline {section}{\numberline {22.1}Binomial coefficients}{208}{section.22.1}%
|
||
\contentsline {subsubsection}{Formula 1}{208}{section.22.1}%
|
||
\contentsline {subsubsection}{Formula 2}{208}{section.22.1}%
|
||
\contentsline {subsubsection}{Properties}{208}{section.22.1}%
|
||
\contentsline {subsubsection}{Boxes and balls}{209}{section.22.1}%
|
||
\contentsline {subsubsection}{Multinomial coefficients}{210}{section.22.1}%
|
||
\contentsline {section}{\numberline {22.2}Catalan numbers}{210}{section.22.2}%
|
||
\contentsline {subsubsection}{Parenthesis expressions}{211}{section.22.2}%
|
||
\contentsline {subsubsection}{Formula 1}{211}{section.22.2}%
|
||
\contentsline {subsubsection}{Formula 2}{211}{section.22.2}%
|
||
\contentsline {subsubsection}{Counting trees}{212}{section.22.2}%
|
||
\contentsline {section}{\numberline {22.3}Inclusion-exclusion}{212}{section.22.3}%
|
||
\contentsline {subsubsection}{Derangements}{213}{section.22.3}%
|
||
\contentsline {section}{\numberline {22.4}Burnside's lemma}{214}{section.22.4}%
|
||
\contentsline {section}{\numberline {22.5}Cayley's formula}{215}{section.22.5}%
|
||
\contentsline {subsubsection}{Prüfer code}{216}{section.22.5}%
|
||
\contentsline {chapter}{\numberline {23}Matrices}{217}{chapter.23}%
|
||
\contentsline {section}{\numberline {23.1}Operations}{217}{section.23.1}%
|
||
\contentsline {subsubsection}{Matrix multiplication}{218}{section.23.1}%
|
||
\contentsline {subsubsection}{Matrix power}{219}{section.23.1}%
|
||
\contentsline {subsubsection}{Determinant}{219}{section.23.1}%
|
||
\contentsline {section}{\numberline {23.2}Linear recurrences}{220}{section.23.2}%
|
||
\contentsline {subsubsection}{Fibonacci numbers}{220}{section.23.2}%
|
||
\contentsline {subsubsection}{General case}{221}{section.23.2}%
|
||
\contentsline {section}{\numberline {23.3}Graphs and matrices}{222}{section.23.3}%
|
||
\contentsline {subsubsection}{Counting paths}{222}{section.23.3}%
|
||
\contentsline {subsubsection}{Shortest paths}{222}{section.23.3}%
|
||
\contentsline {subsubsection}{Kirchhoff's theorem}{223}{section.23.3}%
|
||
\contentsline {chapter}{\numberline {24}Probability}{225}{chapter.24}%
|
||
\contentsline {section}{\numberline {24.1}Calculation}{225}{section.24.1}%
|
||
\contentsline {section}{\numberline {24.2}Events}{226}{section.24.2}%
|
||
\contentsline {subsubsection}{Complement}{227}{section.24.2}%
|
||
\contentsline {subsubsection}{Union}{227}{section.24.2}%
|
||
\contentsline {subsubsection}{Conditional probability}{227}{section.24.2}%
|
||
\contentsline {subsubsection}{Intersection}{228}{section.24.2}%
|
||
\contentsline {section}{\numberline {24.3}Random variables}{228}{section.24.3}%
|
||
\contentsline {subsubsection}{Expected value}{229}{section.24.3}%
|
||
\contentsline {subsubsection}{Distributions}{229}{section.24.3}%
|
||
\contentsline {section}{\numberline {24.4}Markov chains}{230}{section.24.4}%
|
||
\contentsline {section}{\numberline {24.5}Randomized algorithms}{231}{section.24.5}%
|
||
\contentsline {subsubsection}{Order statistics}{232}{section.24.5}%
|
||
\contentsline {subsubsection}{Verifying matrix multiplication}{232}{section.24.5}%
|
||
\contentsline {subsubsection}{Graph coloring}{233}{section.24.5}%
|
||
\contentsline {chapter}{\numberline {25}Game theory}{235}{chapter.25}%
|
||
\contentsline {section}{\numberline {25.1}Game states}{235}{section.25.1}%
|
||
\contentsline {subsubsection}{Winning and losing states}{235}{section.25.1}%
|
||
\contentsline {subsubsection}{State graph}{236}{section.25.1}%
|
||
\contentsline {section}{\numberline {25.2}Nim game}{237}{section.25.2}%
|
||
\contentsline {subsubsection}{Analysis}{237}{section.25.2}%
|
||
\contentsline {subsubsection}{Misère game}{238}{section.25.2}%
|
||
\contentsline {section}{\numberline {25.3}Sprague–Grundy theorem}{238}{section.25.3}%
|
||
\contentsline {subsubsection}{Grundy numbers}{238}{section.25.3}%
|
||
\contentsline {subsubsection}{Subgames}{240}{section.25.3}%
|
||
\contentsline {subsubsection}{Grundy's game}{240}{section.25.3}%
|
||
\contentsline {chapter}{\numberline {26}String algorithms}{243}{chapter.26}%
|
||
\contentsline {section}{\numberline {26.1}String terminology}{243}{section.26.1}%
|
||
\contentsline {section}{\numberline {26.2}Trie structure}{244}{section.26.2}%
|
||
\contentsline {section}{\numberline {26.3}String hashing}{245}{section.26.3}%
|
||
\contentsline {section}{\numberline {26.4}Z-algorithm}{247}{section.26.4}%
|
||
\contentsline {subsubsection}{Using the Z-array}{250}{section.26.4}%
|
||
\contentsline {subsubsection}{Implementation}{250}{section.26.4}%
|
||
\contentsline {chapter}{\numberline {27}Square root algorithms}{251}{chapter.27}%
|
||
\contentsline {section}{\numberline {27.1}Combining algorithms}{252}{section.27.1}%
|
||
\contentsline {subsubsection}{Case processing}{252}{section.27.1}%
|
||
\contentsline {subsubsection}{Batch processing}{253}{section.27.1}%
|
||
\contentsline {section}{\numberline {27.2}Integer partitions}{254}{section.27.2}%
|
||
\contentsline {subsubsection}{Knapsack}{254}{section.27.2}%
|
||
\contentsline {subsubsection}{String construction}{255}{section.27.2}%
|
||
\contentsline {section}{\numberline {27.3}Mo's algorithm}{255}{section.27.3}%
|
||
\contentsline {chapter}{\numberline {28}Segment trees revisited}{257}{chapter.28}%
|
||
\contentsline {section}{\numberline {28.1}Lazy propagation}{258}{section.28.1}%
|
||
\contentsline {subsubsection}{Lazy segment trees}{258}{section.28.1}%
|
||
\contentsline {subsubsection}{Polynomial updates}{260}{section.28.1}%
|
||
\contentsline {section}{\numberline {28.2}Dynamic trees}{261}{section.28.2}%
|
||
\contentsline {subsubsection}{Sparse segment trees}{261}{lstnumber.-202.4}%
|
||
\contentsline {subsubsection}{Persistent segment trees}{262}{lstnumber.-202.4}%
|
||
\contentsline {section}{\numberline {28.3}Data structures}{263}{section.28.3}%
|
||
\contentsline {section}{\numberline {28.4}Two-dimensionality}{264}{section.28.4}%
|
||
\contentsline {chapter}{\numberline {29}Geometry}{265}{chapter.29}%
|
||
\contentsline {section}{\numberline {29.1}Complex numbers}{266}{section.29.1}%
|
||
\contentsline {section}{\numberline {29.2}Points and lines}{268}{section.29.2}%
|
||
\contentsline {subsubsection}{Point location}{268}{lstnumber.-208.3}%
|
||
\contentsline {subsubsection}{Line segment intersection}{269}{lstnumber.-208.3}%
|
||
\contentsline {subsubsection}{Point distance from a line}{269}{lstnumber.-208.3}%
|
||
\contentsline {subsubsection}{Point inside a polygon}{270}{lstnumber.-208.3}%
|
||
\contentsline {section}{\numberline {29.3}Polygon area}{271}{section.29.3}%
|
||
\contentsline {subsubsection}{Pick's theorem}{272}{section.29.3}%
|
||
\contentsline {section}{\numberline {29.4}Distance functions}{272}{section.29.4}%
|
||
\contentsline {subsubsection}{Rotating coordinates}{273}{section.29.4}%
|
||
\contentsline {chapter}{\numberline {30}Sweep line algorithms}{275}{chapter.30}%
|
||
\contentsline {section}{\numberline {30.1}Intersection points}{276}{section.30.1}%
|
||
\contentsline {section}{\numberline {30.2}Closest pair problem}{277}{section.30.2}%
|
||
\contentsline {section}{\numberline {30.3}Convex hull problem}{278}{section.30.3}%
|
||
\contentsline {chapter}{Bibliography}{281}{section*.3}%
|
||
\contentsline {chapter}{Index}{287}{chapter*.5}%
|