Table of Contents
Foreword xv
Acknowledgments xvii
Introduction xix
Online Resources xx
Who This Book Is For xx
The Programming Language xx
Why Use C? xxi
Static Keyword xxi
Include Files xxii
Freeing Memory xxii
Topics xxii
Judges xxiii
Anatomy of a Problem Description xxv
Problem: Food Lines xxvi
The Problem xxvi
Solving the Problem xxvii
Notes xxix
1 Hash Tables 1
Problem 1: Unique Snowflakes 1
The Problem 2
Simplifying the Problem 3
Solving the Core Problem 4
Solution 1: Pairwise Comparisons 7
Solution 2: Doing Less Work 11
Hash Tables 16
Hash Table Design 16
Why Use Hash Tables? 19
Problem 2: Compound Words 19
The Problem 19
Identifying Compound Words 20
Solution 20
Problem 3: Spelling Check: Deleting a Letter 24
The Problem 24
Thinking About Hash Tables 25
An Ad Hoc Solution 27
Summary 30
Notes 30
2 Trees and Recursion 31
Problem 1: Halloween Haul 31
The Problem 32
Binary Trees 33
Solving the Sample Instance 35
Representing Binary Trees 35
Collecting All the Candy 39
A Completely Different Solution 45
Walking the Minimum Number of Streets 50
Reading the Input 53
Why Use Recursion? 59
Problem 2: Descendant Distance 59
The Problem 59
Reading the Input 62
Number of Descendants from One Node 65
Number of Descendants from All Nodes 67
Sorting Nodes 67
Outputting the Information 68
The main Function 69
Summary 70
Notes 70
3 Memoization and Dynamic Programming 71
Problem 1: Burger Fervor 72
The Problem 72
Forming a Plan 72
Characterizing Optimal Solutions 74
Solution 1: Recursion 75
Solution 2: Memoization 80
Solution 3: Dynamic Programming 85
Memoization and Dynamic Programming 88
Step 1: Structure of Optimal Solutions 88
Step 2: Recursive Solution 89
Step 3: Memoization 90
Step 4: Dynamic Programming 90
Problem 2: Moneygrubbers 91
The Problem 91
Characterizing Optimal Solutions 92
Solution 1: Recursion 94
The main Function 98
Solution 2: Memoization 100
Problem 3: Hockey Rivalry 102
The Problem 102
About Rivalries 103
Characterizing Optimal Solutions 105
Solution 1: Recursion 107
Solution 2: Memoization 110
Solution 3: Dynamic Programming 111
A Space Optimization 114
Problem 4: Ways to Pass 115
The Problem 116
Solution: Memoization 116
Summary 118
Notes 118
4 Graphs and Breadth-First Search 119
Problem 1: Knight Chase 119
The Problem 120
Moving Optimally 122
Best Knight Outcome 131
The Knight Flip-Flop 133
A Time Optimization 136
Graphs and BFS 137
What Are Graphs? 137
Graphs vs. Trees 138
BFS on Graphs 140
Problem 2: Rope Climb 141
The Problem 141
Solution 1: Finding the Moves 142
Solution 2: A Remodel 147
Problem 3: Book Translation 155
The Problem 155
Building the Graph 156
The BFS 160
Total Cost 162
Summary 162
Notes 163
5 Shortest Paths in Weighted Graphs 165
Problem 1: Mice Maze 166
The Problem 166
Moving On from BFS 166
Shortest Paths in Weighted Graphs 168
Building the Graph 171
Implementing Dijkstra's Algorithm 173
Two Optimizations 175
Dijkstra's Algorithm 177
Runtime of Dijkstra's Algorithm 177
Negative-weight Edges 178
Problem 2: Grandma Planner 180
The Problem 180
Adjacency Matrix 181
Building the Graph 182
Weird Paths 184
Task 1: Shortest Paths 187
Task 2: Number of Shortest Paths 189
Summary 196
Notes 196
6 Binary Search 197
Problem 1: Feeding Ants 197
The Problem 198
A New Flavor of Tree Problem 199
Reading the Input 201
Testing Feasibility 203
Searching for a Solution 205
Binary Search 206
Runtime of Binary Search 207
Determining Feasibility 208
Searching a Sorted Array 208
Problem 2: River Jump 209
The Problem 209
A Greedy Idea 210
Testing Feasibility 212
Searching for a Solution 216
Reading the Input 219
Problem 3: Living Quality 220
The Problem 220
Sorting Every Rectangle 221
Binary Search 224
Testing Feasibility 225
Testing Feasibility More Quickly 227
Problem 4: Cave Doors 233
The Problem 233
Solving a Subtask 234
Using a Linear Search 236
Using Binary Search 238
Summary 240
Notes 241
7 Heaps and Segment Trees 243
Problem 1: Supermarket Promotion 243
The Problem 243
Solution 1: Maximum and Minimum in an Array 244
Max-Heaps 248
Min-Heaps 259
Solution 2: Heaps 261
Heaps 263
Two More Applications 264
Choosing a Data Structure 265
Problem 2: Building Treaps 265
The Problem 265
Recursively Outputting Treaps 267
Sorting by Label 268
Solution 1: Recursion 269
Range Maximum Queries 272
Segment Trees 273
Solution 2: Segment Trees 281
Segment Trees 282
Problem 3: Two Sum 283
The Problem 283
Filling the Segment Tree 284
Querying the Segment Tree 288
Updating the Segment Tree 290
The Main Function 293
Summary 294
Notes 294
8 Problem 1: Social Network 296
The Problem 296
Modeling as a Graph 297
Solution 1: BFS 300
Union-Find 304
Solution 2: Union-Find 307
Optimization 1: Union by Size 310
Optimization 2: Path Compression 314
Union-Find 316
Relationships: Three Requirements 316
Choosing Union-Find 317
Optimizations 317
Problem 2: Friends and Enemies 317
The Problem 318
Augmentation: Enemies 319
The main Function 323
Find and Union 324
SetFriends and SetEnemies 325
AreFriends and AreEnemies 327
Problem 3: Drawer Chore 328
The Problem 328
Equivalent Drawers 329
The main Function 334
Find and Union 335
Summary 336
Notes 337
Afterword 339
A Algorithm Runtime 341
The Case for Timing … and Something Else 341
Big O Notation 343
Linear Time 343
Constant Time 344
Another Example 345
Quadratic Time 345
Big O in This Book 346
B Because I Can't Resist 347
Unique Snowflakes: Implicit Linked Lists 347
Burger Fervor: Reconstructing a Solution 350
Knight Chase: Encoding Moves 352
Dijkstra's Algorithm: Using a Heap 354
Mice Maze: Tracing with Heaps 354
Mice Maze: Implementation with Heaps 357
Compressing Path Compression 358
Step 1: No More Ternary If 358
Step 2: Cleaner Assignment Operator 359
Step 3: Understand the Recursion 360
C Problem Credits 361
Index 365
