Algorithm Design Practice for Collegiate Programming Contests and Education

Description

This book can be used as an experiment and reference book for algorithm design courses, as well as a training manual for programming contests. It contains 247 problems selected from ACM-ICPC programming contests and other programming contests. There's detailed analysis for each problem. All problems, and test datum for most of problems will be provided online. The content will follow usual algorithms syllabus, and problem-solving strategies will be introduced in analyses and solutions to problem cases. For students in computer-related majors, contestants and programmers, this book can polish their programming and problem-solving skills with familarity of algorithms and mathematics. Cover Half Title Title Page Copyright Page Contents Preface Author Biographical Information 1. Practice for Ad Hoc Problems 1.1. Solving Problems by Mechanism Analysis 1.1.1. Factstone Benchmark 1.1.2. Bridge 1.2. Solving Problems by Statistical Analysis 1.2.1. Ants 1.2.2. Matches Game 1.3. Problems 2. Practice for Simulation Problems 2.1. Simulation of Direct Statement 2.1.1. The Hardest Problem Ever 2.1.2. Rock-Paper-Scissors Tournament 2.1.3. Robocode 2.1.4. Eurodiffusion 2.2. Simulation by Sieve Method 2.2.1. The Game 2.2.2. Game Schedule Required 2.3. Construction Simulation 2.3.1. Packets 2.3.2. Paper Cutting 2.4. Problems 3. Practice for Number Theory 3.1. Practice for Prime Numbers 3.1.1. Calculating Prime Numbers by a Sieve 3.1.2. Testing the Primality of Large Numbers 3.2. Practice for Indeterminate Equations and Congruence 3.2.1. Greatest Common Divisors and Indeterminate Equations 3.2.2. Congruences and Congruence Equations 3.3. Multiplicative Functions 3.4. Problems 4. Practice for Combinatorics 4.1. Generating Permutations 4.1.1. Generating the Next Permutation Based on Lexicographic Order 4.1.2. Generating All Permutations Based on Lexicographic Order 4.2. Enumeration of Permutations and Combinations 4.2.1. Calculating Numbers of Permutations and Combinations 4.2.2. Catalan Numbers, Bell Numbers and Stirling Numbers 4.3. Applications of the Pigeonhole Principle and the Inclusion–Exclusion Principle 4.3.1. Applications of the Pigeonhole Principle 4.3.2. Applications of the Inclusion–Exclusion Principle 4.4. Applications of the Pólya Counting Formula 4.4.1. Necklace of Beads 4.4.2. Toral Tickets 4.4.3. Color 4.5. Problems 5. Practice for Greedy Algorithms 5.1. Practices for Greedy Algorithms 5.1.1. Pass-Muraille 5.1.2. Tian Ji: The Horse Racing 5.2. Greedy-Choices Based on Sorted Data 5.2.1. The Shoemaker’s Problem 5.2.2. Add All 5.2.3. Wooden Sticks 5.2.4. Radar Installation 5.3. Greedy Algorithms Used with Other Methods to Solve P-Problems 5.3.1. Color a Tree 5.3.2. Copying Books 5.4. Problems 6. Practice for Dynamic Programming 6.1. Linear Dynamic Programming 6.1.1. Linear Dynamic Programming 6.1.2. Subset Sum 6.1.3. Longest Common Subsequence (LCS) 6.1.4. Longest Increasing Subsequence (LIS) 6.2. Tree-Like Dynamic Programming 6.2.1. Binary Apple Tree 6.2.2. Anniversary Party 6.3. Dynamic Programming with State Compression 6.3.1. Nuts for Nuts 6.3.2. Mondriaan’s Dream 6.4. Problems 7. Practice for Advanced Data Structures 7.1. Suffix Arrays 7.1.1. Doubling Algorithm Used to Calculate a Rank Array and a Suffix Array 7.1.2. The Longest Common Prefix 7.1.3. Application of Suffix Array 7.2. Segment Trees 7.2.1. Segment Trees 7.2.2. Updating a Single Point in a Segment Tree 7.2.3. Updating a Subinterval in a Segment Tree 7.3. Graph Algorithms 7.3.1. Euler Graphs 7.3.2. Traveling Salesman Problem and Tournaments 7.3.3. Maximum Independent Sets 7.3.4. Articulation Points, Bridges, and Biconnected Components 7.4. Problems 8. Practice for Computational Geometry 8.1. Points, Line Segments, and Plans 8.1.1. Dot Product and Cross Product 8.1.2. Line Segment Intersection 8.1.3. Solving Polyhedron Problems by Euler's Polyhedron Formula 8.2. Calculating the Area for Union of Rectangles by Sweep Line Algorithms 8.2.1. Sweeping in the Vertical Direction 8.2.2. Sweeping in the Horizontal Direction 8.3. Intersection of Half-Planes 8.3.1. On-Line Algorithm for Intersection of Half-Planes 8.3.2. Polar Angles 8.4. Convex Hull and Finding the Farthest Pair of Points 8.4.1. Convex Hull 8.4.2. Finding the Farthest Pair of Points 8.5. Problems 9. Practice for State Space Search 9.1. Constructing a State Space Tree 9.1.1. Robot 9.1.2. The New Villa 9.2. Optimizing State Space Search 9.2.1. Be Wary of Rose 9.2.2. Fill 9.2.3. Package Pricing 9.2.4. Eight 9.2.5. Remmarguts’ Date 9.2.6. Jaguar King 9.3. A Game Tree Used to Solve a Game Problem 9.3.1. Find the Winning Move 9.3.2. The Pawn Chess 9.4. Problems References Index