ENGLISH

Competitive Programming 4

Book information

Year
2020
Language
english
Format
PDF
Filesize
12 MB (12160552 bytes)
Volume
Book 2 Chapter 5–9
Pages
\352
Time added
2022-12-28 16:21:39

Description

CP4: Book 2 Contents 5 Mathematics 5.1 Overview and Motivation 5.2 Ad Hoc Mathematical Problems 5.3 Number Theory 5.3.1 Prime Numbers 5.3.2 Probabilistic Prime Testing (Java Only) 5.3.3 Finding Prime Factors with Optimized Trial Divisions 5.3.4 Functions Involving Prime Factors 5.3.5 Modified Sieve 5.3.6 Greatest Common Divisor & Least Common Multiple 5.3.7 Factorial 5.3.8 Working with Prime Factors 5.3.9 Modular Arithmetic 5.3.10 Extended Euclidean Algorithm 5.3.11 Number Theory in Programming Contests 5.4 Combinatorics 5.4.1 Fibonacci Numbers 5.4.2 Binomial Coefficients 5.4.3 Catalan Numbers 5.4.4 Combinatorics in Programming Contests 5.5 Probability Theory 5.6 Cycle-Finding 5.6.1 Problem Description 5.6.2 Solutions using Efficient Data Structures 5.6.3 Floyd’s Cycle-Finding Algorithm 5.7 Game Theory (Basic) 5.8 Matrix Power 5.8.1 Some Definitions and Sample Usages 5.8.2 Efficient Modular Power (Exponentiation) 5.8.3 Efficient Matrix Modular Power (Exponentiation) 5.8.4 DP Speed-up with Matrix Power 5.9 Solution to Non-Starred Exercises 5.10 Chapter Notes 6 String Processing 6.1 Overview and Motivation 6.2 Ad Hoc String (Harder) 6.3 String Processing with DP 6.3.1 String Alignment (Edit Distance) 6.3.2 Longest Common Subsequence 6.3.3 Non Classical String Processing with DP 6.4 String Matching 6.4.1 Library Solutions 6.4.2 Knuth-Morris-Pratt (KMP) Algorithm 6.4.3 String Matching in a 2D Grid 6.5 Suffix Trie/Tree/Array 6.5.1 Suffix Trie and Applications 6.5.2 Suffix Tree 6.5.3 Applications of Suffix Tree 6.5.4 Suffix Array 6.5.5 Applications of Suffix Array 6.6 String Matching with Hashing 6.6.1 Hashing a String 6.6.2 Rolling Hash 6.6.3 Rabin-Karp String Matching Algorithm 6.6.4 Collisions Probability 6.7 Anagram and Palindrome 6.7.1 Anagram 6.7.2 Palindrome 6.8 Solution to Non-Starred Exercises 6.9 Chapter Notes 7 (Computational) Geometry 7.1 Overview and Motivation 7.2 Basic Geometry Objects with Libraries 7.2.1 0D Objects: Points 7.2.2 1D Objects: Lines 7.2.3 2D Objects: Circles 7.2.4 2D Objects: Triangles 7.2.5 2D Objects: Quadrilaterals 7.3 Algorithms on Polygon with Libraries 7.3.1 Polygon Representation 7.3.2 Perimeter of a Polygon 7.3.3 Area of a Polygon 7.3.4 Checking if a Polygon is Convex 7.3.5 Checking if a Point is Inside a Polygon 7.3.6 Cutting Polygon with a Straight Line 7.3.7 Finding the Convex Hull of a Set of Points 7.4 3D Geometry 7.5 Solution to Non-Starred Exercises 7.6 Chapter Notes 8 More Advanced Topics 8.1 Overview and Motivation 8.2 More Advanced Search Techniques 8.2.1 Backtracking with Bitmask 8.2.2 State-Space Search with BFS or Dijkstra’s 8.2.3 Meet in the Middle 8.3 More Advanced DP Techniques 8.3.1 DP with Bitmask 8.3.2 Compilation of Common (DP) Parameters 8.3.3 Handling Negative Parameter Values with O↵set 8.3.4 MLE/TLE? Use Better State Representation 8.3.5 MLE/TLE? Drop One Parameter, Recover It from Others 8.3.6 Multiple Test Cases? No Memo Table Re-initializations 8.3.7 MLE? Use bBST or Hash Table as Memo Table 8.3.8 TLE? Use Binary Search Transition Speedup 8.3.9 Other DP Techniques 8.4 Network Flow 8.4.1 Overview and Motivation 8.4.2 Ford-Fulkerson Method 8.4.3 Edmonds-Karp Algorithm 8.4.4 Dinic’s Algorithm 8.4.5 Flow Graph Modeling - Classic 8.4.6 Flow Graph Modeling - Non Classic 8.4.7 Network Flow in Programming Contests 8.5 Graph Matching 8.5.1 Overview and Motivation 8.5.2 Graph Matching Variants 8.5.3 Unweighted MCBM 8.5.4 Weighted MCBM and Unweighted/Weighted MCM 8.6 NP-hard/complete Problems 8.6.1 Preliminaries 8.6.2 Pseudo-Polynomial: Knapsack, Subset-Sum, Coin-Change 8.6.3 Traveling-Salesman-Problem (TSP) 8.6.4 Hamiltonian-Path/Tour 8.6.5 Longest-Path 8.6.6 Max-Independent-Set and Min-Vertex-Cover 8.6.7 Min-Set-Cover 8.6.8 Min-Path-Cover 8.6.9 Satisfiability (SAT) 8.6.10 Steiner-Tree 8.6.11 Graph-Coloring 8.6.12 Min-Clique-Cover 8.6.13 Other NP-hard/complete Problems 8.6.14 Summary 8.7 Problem Decomposition 8.7.1 Two Components: Binary Search the Answer and Other 8.7.2 Two Components: Involving Efficient Data Structure 8.7.3 Two Components: Involving Geometry 8.7.4 Two Components: Involving Graph 8.7.5 Two Components: Involving Mathematics 8.7.6 Two Components: Graph Preprocessing and DP 8.7.7 Two Components: Involving 1D Static RSQ/RMQ 8.7.8 Three (or More) Components 8.8 Solution to Non-Starred Exercises 8.9 Chapter Notes 9 Rare Topics 9.1 Overview and Motivation 9.2 Sliding Window 9.3 Sparse Table Data Structure 9.4 Square Root Decomposition 9.5 Heavy-Light Decomposition 9.6 Tower of Hanoi 9.7 Matrix Chain Multiplication 9.8 Lowest Common Ancestor 9.9 Tree Isomorphism 9.10 De Bruijn Sequence 9.11 Fast Fourier Transform 9.12 Pollard’s rho Algorithm 9.13 Chinese Remainder Theorem 9.14 Lucas’ Theorem 9.15 Rare Formulas or Theorems 9.16 Combinatorial Game Theory 9.17 Gaussian Elimination Algorithm 9.18 Art Gallery Problem 9.19 Closest Pair Problem 9.20 A* and IDA*: Informed Search 9.21 Pancake Sorting 9.22 Egg Dropping Puzzle 9.23 Dynamic Programming Optimization 9.24 Push-Relabel Algorithm 9.25 Min Cost (Max) Flow 9.26 Hopcroft-Karp Algorithm 9.27 Kuhn-Munkres Algorithm 9.28 Edmonds’ Matching Algorithm 9.29 Chinese Postman Problem 9.30 Constructive Problem 9.31 Interactive Problem 9.32 Linear Programming 9.33 Gradient Descent 9.34 Chapter Notes Index

Similar books

Session C11: Ancient Cultural Landscapes in South Europe – their Ecological Setting and Evolution, Session C22: Gardeners from South America, Session S04: Agro-Pastoralism and Early Metallurgy Sessions, Session WS29: The Idea of Enclosure in Recent Iberian Prehistory, Session C88: Rhytmes et causalites des dynamiques de l'anthropisation en Europe entre 6500 ET 500 BC: Hypotheses socio-culturelles et/ou climatiques: Proceedings of the XV UISPP World Congress (Lisbon 4-9 September 2006) / Actes du XV Congrès Mondial (Lisbonne 4-9 Septembre 2006) Vol.36

Session C11: Ancient Cultural Landscapes in South Europe – their Ecological Setting and Evolution, Session C22: Gardeners from South America, Session S04: Agro-Pastoralism and Early Metallurgy Sessions, Session WS29: The Idea of Enclosure in Recent Iberian Prehistory, Session C88: Rhytmes et causalites des dynamiques de l'anthropisation en Europe entre 6500 ET 500 BC: Hypotheses socio-culturelles et/ou climatiques: Proceedings of the XV UISPP World Congress (Lisbon 4-9 September 2006) / Actes du XV Congrès Mondial (Lisbonne 4-9 Septembre 2006) Vol.36

2010 · PDF

THE BRITISH ARMY IN INDIA: ITS PRESERVATION BY AN APPROPRIATE CLOTHING, HOUSING, LOCATING, RECREATIVE EMPLOYMENT, AND HOPEFUL ENCOURAGEMENT OF THE TROOPS. with AN APPENDIX ON INDIA : THE CLIMATE OP ITS HILLS ; THE DEVELOPMENT OF ITS RESODRCBS, INDUSTRY, AND ARTS ; THE ADMINISTRATION OF JUSTICE ; THE BLACK ACT ; THE PROGRESS OF CHRISTIANITY ; THE TRAFFIC IN OPIUM ; THE VALUE OF INDIA ; PERMANENT CAUSES OF DISAFFECTION, AND OF THE RECENT REBELLION ; THE TRADITIONARY POLICY; MISGOVERNMENT BY NATIVE RULERS ; ANNEXATIONS OF THEIR TERRITORY, ETC.

THE BRITISH ARMY IN INDIA: ITS PRESERVATION BY AN APPROPRIATE CLOTHING, HOUSING, LOCATING, RECREATIVE EMPLOYMENT, AND HOPEFUL ENCOURAGEMENT OF THE TROOPS. with AN APPENDIX ON INDIA : THE CLIMATE OP ITS HILLS ; THE DEVELOPMENT OF ITS RESODRCBS, INDUSTRY, AND ARTS ; THE ADMINISTRATION OF JUSTICE ; THE BLACK ACT ; THE PROGRESS OF CHRISTIANITY ; THE TRAFFIC IN OPIUM ; THE VALUE OF INDIA ; PERMANENT CAUSES OF DISAFFECTION, AND OF THE RECENT REBELLION ; THE TRADITIONARY POLICY; MISGOVERNMENT BY NATIVE RULERS ; ANNEXATIONS OF THEIR TERRITORY, ETC.

1858 · PDF

Idries Shah 27 Books Collection : A Perfumed Scorpion, A Veiled Gazelle, Caravan of Dreams, Darkest England, Destination Mecca, Evenings with Idries Shah, Knowing How to Know, Learning How to Learn, Letters and Lectures of Idries Shah, Neglected aspects of Sufi study, Observations, Oriental Magic, Reflections, Seeker after Truth, Special Illumination, Special Problems in the study of Sufi ideas, Sufi thought and action, Tales of the Dervishes, The Dermis Probe, The Elephant in the Dark, The Englishman Handbook, Idries Shah Antology, The Magic Monastery, The natives are restless, wisdom of the Idiots PDF.

Idries Shah 27 Books Collection : A Perfumed Scorpion, A Veiled Gazelle, Caravan of Dreams, Darkest England, Destination Mecca, Evenings with Idries Shah, Knowing How to Know, Learning How to Learn, Letters and Lectures of Idries Shah, Neglected aspects of Sufi study, Observations, Oriental Magic, Reflections, Seeker after Truth, Special Illumination, Special Problems in the study of Sufi ideas, Sufi thought and action, Tales of the Dervishes, The Dermis Probe, The Elephant in the Dark, The Englishman Handbook, Idries Shah Antology, The Magic Monastery, The natives are restless, wisdom of the Idiots PDF.

2022 · PDF

The travels of Capts. Lewis and Clarke from St. Louis, by way of the Missouri and Columbia rivers, to the Pacific ocean; performed in the years 1804, 1805 & 1806, by order of the government of the United States. Containing delineations of the manners, customs, religion, &c. of the Indians, comp. from various authentic sources, and original documents, and a summary of the Statistical view of the Indian nations, from the official communication of Meriwether Lewis. Illustrated with a map of the country, inhabited by the western tribes of Indians

The travels of Capts. Lewis and Clarke from St. Louis, by way of the Missouri and Columbia rivers, to the Pacific ocean; performed in the years 1804, 1805 & 1806, by order of the government of the United States. Containing delineations of the manners, customs, religion, &c. of the Indians, comp. from various authentic sources, and original documents, and a summary of the Statistical view of the Indian nations, from the official communication of Meriwether Lewis. Illustrated with a map of the country, inhabited by the western tribes of Indians

1809 · PDF

Professional Linux kernel architecture ''Wrox programmer to programmer''--Cover. - ''What you are reading right now is the result of an evolution over more than seven years: After two years of writing, the first edition was published in German by Carl Hanser Verlag in 2003. It then described kernel 2.6.0. The test was used as a basis for the low-level design documentation for the EAL4+ security evaluation of Red Hat Enterprise Linux 5, requiring to update it to kernel 2.6.18 (if the EAL acronym does not mean anything to you, then Wikipedia is once more your friend). Hewlett-Packard sponsored the translation into English and has, thankfully, granted the rights to publish the result. Updates to kernel 2.6.24 were then performed specifically for this book''--P. ix

Professional Linux kernel architecture ''Wrox programmer to programmer''--Cover. - ''What you are reading right now is the result of an evolution over more than seven years: After two years of writing, the first edition was published in German by Carl Hanser Verlag in 2003. It then described kernel 2.6.0. The test was used as a basis for the low-level design documentation for the EAL4+ security evaluation of Red Hat Enterprise Linux 5, requiring to update it to kernel 2.6.18 (if the EAL acronym does not mean anything to you, then Wikipedia is once more your friend). Hewlett-Packard sponsored the translation into English and has, thankfully, granted the rights to publish the result. Updates to kernel 2.6.24 were then performed specifically for this book''--P. ix

2008 · PDF