Programming Challenges: The Programming Contest Training Manual

Programming Challenges......Page 1
Contents......Page 13
1.1 Getting Started With the Judge......Page 21
1.1.2 The Universidad de Valladolid Robot Judge......Page 22
1.1.3 Feedback From the Judge......Page 23
1.2 Choosing Your Weapon......Page 24
1.2.1 Programming Languages......Page 25
1.2.2 Reading Our Programs......Page 26
1.2.3 Standard Input/Output......Page 27
1.3 Programming Hints......Page 29
1.4 Elementary Data Types......Page 31
1.5 About the Problems......Page 33
1.6.1 The 3n + 1 Problem......Page 35
1.6.2 Minesweeper......Page 36
1.6.3 The Trip......Page 37
1.6.4 LCD Display......Page 38
1.6.5 Graphical Editor......Page 39
1.6.6 Interpreter......Page 41
1.6.7 Check the Check......Page 43
1.6.8 Australian Voting......Page 45
1.8 Notes......Page 46
2.1 Elementary Data Structures......Page 47
2.1.2 Queues......Page 48
2.1.3 Dictionaries......Page 50
2.1.4 Priority Queues......Page 51
2.1.5 Sets......Page 52
2.2.2 The Java java.util Package......Page 53
2.3 Program Design Example: Going to War......Page 54
2.4 Hitting the Deck......Page 55
2.5 String Input/Output......Page 57
2.6 Winning the War......Page 58
2.7 Testing and Debugging......Page 59
2.8.1 Jolly Jumpers......Page 62
2.8.2 Poker Hands......Page 63
2.8.3 Hartals......Page 65
2.8.4 Crypt Kicker......Page 67
2.8.5 Stack \'em Up......Page 68
2.8.6 Erd¨os Numbers......Page 70
2.8.7 Contest Scoreboard......Page 72
2.8.8 Yahtzee......Page 73
2.10 Notes......Page 75
3.1 Character Codes......Page 76
3.2 Representing Strings......Page 78
3.3 Program Design Example: Corporate Renamings......Page 79
3.4 Searching for Patterns......Page 81
3.5 Manipulating Strings......Page 82
3.6 Completing the Merger......Page 83
3.7 String Library Functions......Page 84
3.8.1 WERTYU......Page 86
3.8.2 Where\'s Waldorf?......Page 87
3.8.3 Common Permutation......Page 89
3.8.4 Crypt Kicker II......Page 90
3.8.5 Automated Judge Script......Page 91
3.8.6 File Fragmentation......Page 93
3.8.7 Doublets......Page 94
3.8.8 Fmt......Page 95
3.10 Notes......Page 97
4.1 Sorting Applications......Page 98
4.2 Sorting Algorithms......Page 99
4.3 Program Design Example: Rating the Field......Page 102
4.4 Sorting Library Functions......Page 103
4.5 Rating the Field......Page 105
4.6.1 Vito\'s Family......Page 108
4.6.2 Stacks of Flapjacks......Page 109
4.6.3 Bridge......Page 111
4.6.4 Longest Nap......Page 112
4.6.5 Shoemaker\'s Problem......Page 114
4.6.6 CDVII......Page 115
4.6.7 ShellSort......Page 117
4.6.8 Football (aka Soccer)......Page 119
4.8 Notes......Page 121
5.1 Machine Arithmetic......Page 122
5.2 High-Precision Integers......Page 123
5.3 High-Precision Arithmetic......Page 125
5.4 Numerical Bases and Conversion......Page 130
5.5 Real Numbers......Page 132
5.5.2 Fractions......Page 133
5.5.3 Decimals......Page 134
5.6.1 Manipulating Polynomials......Page 135
5.7 Logarithms......Page 136
5.8 Real Mathematical Libraries......Page 137
5.9.1 Primary Arithmetic......Page 139
5.9.2 Reverse and Add......Page 140
5.9.3 The Archeologist\'s Dilemma......Page 141
5.9.4 Ones......Page 142
5.9.5 A Multiplication Game......Page 143
5.9.6 Polynomial Coefficients......Page 144
5.9.7 The Stern-Brocot Number System......Page 145
5.9.8 Pairsumonious Numbers......Page 147
5.11 Notes......Page 148
6.1 Basic Counting Techniques......Page 149
6.3 Binomial Coefficients......Page 151
6.4 Other Counting Sequences......Page 153
6.5 Recursion and Induction......Page 155
6.6.1 How Many Fibs?......Page 157
6.6.2 How Many Pieces of Land?......Page 158
6.6.3 Counting......Page 159
6.6.4 Expressions......Page 160
6.6.5 Complete Tree Labeling......Page 161
6.6.6 The Priest Mathematician......Page 162
6.6.7 Self-describing Sequence......Page 164
6.6.8 Steps......Page 165
6.8 Notes......Page 166
7.1 Prime Numbers......Page 167
7.1.1 Finding Primes......Page 168
7.2 Divisibility......Page 169
7.2.1 Greatest Common Divisor......Page 170
7.2.2 Least Common Multiple......Page 171
7.3 Modular Arithmetic......Page 172
7.4.1 Operations on Congruences......Page 174
7.4.3 Diophantine Equations......Page 175
7.5 Number Theoretic Libraries......Page 176
7.6.1 Light, More Light......Page 177
7.6.2 Carmichael Numbers......Page 178
7.6.3 Euclid Problem......Page 179
7.6.4 Factovisors......Page 180
7.6.5 Summation of Four Primes......Page 181
7.6.6 Smith Numbers......Page 182
7.6.7 Marbles......Page 183
7.6.8 Repackaging......Page 184
7.8 Notes......Page 186
8.1 Backtracking......Page 187
8.2 Constructing All Subsets......Page 189
8.3 Constructing All Permutations......Page 190
8.4 Program Design Example: The Eight-Queens Problem......Page 192
8.5 Pruning Search......Page 193
8.6.1 Little Bishops......Page 196
8.6.2 15-Puzzle Problem......Page 197
8.6.3 Queue......Page 199
8.6.4 Servicing Stations......Page 200
8.6.5 Tug of War......Page 201
8.6.6 Garden of Eden......Page 202
8.6.7 Color Hash......Page 204
8.6.8 Bigger Square Please......Page 206
8.8 Notes......Page 208
9.1 Flavors of Graphs......Page 209
9.2 Data Structures for Graphs......Page 211
9.3.1 Breadth-First Search......Page 214
9.3.2 Exploiting Traversal......Page 215
9.3.3 Finding Paths......Page 216
9.4.1 Finding Cycles......Page 218
9.4.2 Connected Components......Page 219
9.5 Topological Sorting......Page 220
9.6.1 Bicoloring......Page 223
9.6.2 Playing With Wheels......Page 224
9.6.3 The Tourist Guide......Page 226
9.6.4 Slash Maze......Page 228
9.6.5 Edit Step Ladders......Page 230
9.6.6 Tower of Cubes......Page 231
9.6.7 From Dusk Till Dawn......Page 233
9.6.8 Hanoi Tower Troubles Again!......Page 235
9.7 Hints......Page 236
10.1.1 Degree Properties......Page 237
10.1.2 Connectivity......Page 238
10.1.3 Cycles in Graphs......Page 239
10.2 Minimum Spanning Trees......Page 240
10.3.1 Dijkstra\'s Algorithm......Page 243
10.3.2 All-Pairs Shortest Path......Page 245
10.4 Network Flows and Bipartite Matching......Page 247
10.5.1 Freckles......Page 251
10.5.2 The Necklace......Page 252
10.5.3 Fire Station......Page 254
10.5.4 Railroads......Page 255
10.5.5 War......Page 257
10.5.6 Tourist Guide......Page 259
10.5.7 The Grand Dinner......Page 261
10.5.8 The Problem With the Problem Setter......Page 262
10.6 Hints......Page 264
11.1 Don\'t Be Greedy......Page 265
11.2 Edit Distance......Page 266
11.3 Reconstructing the Path......Page 270
11.4 Varieties of Edit Distance......Page 271
11.5 Program Design Example: Elevator Optimization......Page 273
11.6.1 Is Bigger Smarter?......Page 277
11.6.2 Distinct Subsequences......Page 278
11.6.3 Weights and Measures......Page 279
11.6.4 Unidirectional TSP......Page 280
11.6.5 Cutting Sticks......Page 282
11.6.6 Ferry Loading......Page 283
11.6.7 Chopsticks......Page 285
11.6.8 Adventures in Moving: Part IV......Page 286
11.8 Notes......Page 287
12.1 Rectilinear Grids......Page 288
12.1.1 Traversal......Page 289
12.1.2 Dual Graphs and Representations......Page 290
12.2.1 Triangular Lattices......Page 291
12.2.2 Hexagonal Lattices......Page 292
12.3 Program Design Example: Plate Weight......Page 295
12.4 Circle Packings......Page 297
12.5 Longitude and Latitude......Page 298
12.6.1 Ant on a Chessboard......Page 299
12.6.2 The Monocycle......Page 300
12.6.3 Star......Page 302
12.6.4 Bee Maja......Page 303
12.6.5 Robbery......Page 304
12.6.6 (2/3/4)-D Sqr/Rects/Cubes/Boxes?......Page 306
12.6.7 Dermuba Triangle......Page 307
12.6.8 Airlines......Page 308
12.7 Hints......Page 310
13.1 Lines......Page 311
13.2 Triangles and Trigonometry......Page 314
13.2.2 Trigonometric Functions......Page 315
13.2.3 Solving Triangles......Page 316
13.3 Circles......Page 318
13.4 Program Design Example: Faster Than a Speeding Bullet......Page 319
13.5 Trigonometric Function Libraries......Page 322
13.6.1 Dog and Gopher......Page 324
13.6.2 Rope Crisis in Ropeland!......Page 325
13.6.3 The Knights of the Round Table......Page 326
13.6.4 Chocolate Chip Cookies......Page 327
13.6.5 Birthday Cake......Page 328
13.6.6 The Largest/Smallest Box......Page 329
13.6.7 Is This Integration?......Page 330
13.6.8 How Big Is It?......Page 331
13.7 Hints......Page 332
14.1 Line Segments and Intersection......Page 333
14.2 Polygons and Angle Computations......Page 335
14.3 Convex Hulls......Page 336
14.4 Triangulation: Algorithms and Related Problems......Page 339
14.4.1 Van Gogh\'s Algorithm......Page 340
14.4.3 Point Location......Page 342
14.5.1 Range Queries......Page 344
14.5.2 Lattice Polygons and Pick\'s Theorem......Page 345
14.6 Geometry Libraries......Page 346
14.7.1 Herding Frosh......Page 347
14.7.2 The Closest Pair Problem......Page 348
14.7.3 Chainsaw Massacre......Page 349
14.7.4 Hotter Colder......Page 350
14.7.5 Useless Tile Packers......Page 351
14.7.6 Radar Tracking......Page 353
14.7.7 Trees on My Island......Page 354
14.7.8 Nice Milk......Page 356
14.8 Hints......Page 357
A.1 The ACM International Collegiate Programming Contest......Page 359
A.1.1 Preparation......Page 360
A.1.2 Strategies and Tactics......Page 361
A.2.1 Participation......Page 363
A.2.2 Format......Page 364
A.3 Topcoder.com......Page 365
A.4 Go to Graduate School!......Page 366
A.5 Problem Credits......Page 368
References......Page 370
Index......Page 373