UVA problems
Further reading
| ID | Title | Keyword | Links |
|---|---|---|---|
| 100 | The 3n + 1 problem | ad hoc, simulation. |
|
| 101 | The Blocks Problem | ad hoc, simulation. |
|
| 102 | Ecological bin packaging | greedy, ad hoc. |
|
| 103 | Stacking Boxes | DP, graph theory, longest path, DAG, sorting. |
|
| 104 | Arbitrage | graph theory, all-pairs shortests paths, APSP, negative weight cycle, Floyd-Warshall (modified relaxation operation). |
|
| 105 | The Skyline Problem | computational geometry, sweep line (or ad hoc: brute force, height map). |
|
| 106 | Fermat vs Pythagoras | number theory, math, Pythagorean triples, Euclid's formula. |
|
| 107 | The Cat in the Hat | trees, math, number of leaves and internal nodes. |
|
| 108 | Maximum Sum | maximum 2D sum, maximum 1D sum, DP. |
|
| 109 | Scud Busters | computational geometry, convex hull, point in convex polygon. |
|
| 110 | Meta-Loopless Sorts | backtracking, permutations, insertion sort. |
|
| 111 | History Grading | DP, LIS (modified) (or LCS). |
|
| 112 | Tree Summing | backtracking. |
|
| 113 | Power of Cryptography | math, n'th root of an integer (can use builtin pow-function). |
|
| 114 | Simulation Wizardry | simulation, ad hoc. |
|
| 115 | Climbing Trees | trees, tree traversal, lowest common ancestor. |
|
| 116 | Unidirectional TSP | DP. |
|
| 117 | The Postal Worker Rings Once | graph theory, Euler tour, shortest paths, SSSP, Bellman-Ford. |
|
| 118 | Mutant Flatworld Explorers | ad hoc, simulation. |
|
| 119 | Greedy Gift Givers | ad hoc. |
|
| 120 | Stack of Flapjacks | greedy, sorting, stacks, queues. |
|
| 121 | Pipe Fitters | geometry, grid packing. |
|
| 122 | Trees on the level | ad hoc, tree traversal. |
|
| 123 | Searching quickly | ad hoc, sorting. |
|
| 124 | Following orders | graph theory, topological sort. |
|
| 125 | Numbering Paths | graph theory, DFS, cycles, strongly connected components (or Floyd-Warshall/transitive closure). |
|
| 126 | The Errant Physicist | ad hoc, polynomials, parsing. |
|
| 127 | Accordian Patience | ad hoc, simulation. |
|
| 128 | Software CRC | number theory, modulo, math. |
|
| 129 | Krypton Factor | graph theory, DFS, brute force, backtracking. |
|
| 130 | Roman Roulette | ad hoc, simulation, Josephus problem. |
|
| 131 | The Psychic Poker Player | ad hoc, simulation, brute force. |
|
| 132 | Bumpy Objects | geometry, brute force, triangles, angles (or convex hull). |
|
| 133 | The Dole Queue | ad hoc, simulation. |
|
| 134 | Loglan - A Logical Language | parsing, recursive decent parsing. |
|
| 135 | No Rectangles | math, finite fields, cyclic permutations, primes. |
|
| 136 | Ugly Numbers | ad hoc, brute force, no input. |
|
| 137 | Polygons | computational geometry, intersection of convex polygons, cutting polygons by a straight line. |
|
| 138 | Street Numbers | math, brute force, no input. |
|
| 139 | Telephone Tangles | ad hoc, simulation. |
|
| 140 | Bandwidth | backtracking, NP-complete, minimum bandwidth problem. |
|
| 141 | The Spot Game | ad hoc, simulation. |
|
| 142 | Mouse Clicks | geometry, simulation, ad hoc. |
|
| 143 | Orchard Trees | computational geometry, point in triangle, brute force. |
|
| 144 | Student Grants | ad hoc, simulation. |
|
| 145 | Gondwanaland Telecom | ad hoc. |
|
| 146 | ID Codes | permutations, math, sorting (or next_permutation in STL). |
|
| 147 | Dollars | DP, coin change. |
|
| 148 | Anagram Checker | ad hoc, string manipulation, backtracking. |
|
| 151 | Power Crisis | ad hoc, simulation, Josephus problem. |
|
| 152 | Tree's a Crowd | ad hoc, sorting, geometry. |
|
| 153 | Permalex | strings, multinomial coefficients, permutations. |
|
| 154 | Recycling | ad hoc. |
|
| 155 | All Squares | ad hoc, recursion, geometry. |
|
| 156 | Ananagrams | ad hoc, sorting. |
|
| 159 | Word Crosses | ad hoc, strings. |
|
| 160 | Factors and Factorials | number theory, primes, summations, math. |
|
| 161 | Traffic Lights | ad hoc, simulation. |
|
| 162 | Beggar My Neighbour | ad hoc, card games, simulation. |
|
| 164 | String Computer | DP, edit distance (Levenshtein), printing solution. |
|
| 165 | Stamps | brute force, backtracking. |
|
| 166 | Making Change | DP (or greedy), coin change (or backtracking). |
|
| 167 | Sultans Successors | backtracking, 8-queens problem. |
|
| 168 | Theseus and the Minotaur | graph theory, simulation |
|
| 170 | Clock Patience | ad hoc, simulation. |
|
| 172 | Calculator Language | parsing, evaluating infix expressions, stacks. |
|
| 183 | Bit Maps | ad hoc, recursion. |
|
| 184 | Laser Lines | computational geometry, signed triangle area, collinearity, |
|
| 186 | Trip Routing | graph theory, all-pairs shortest paths, APSP, Floyd-Warshall. |
|
| 187 | Transaction Processing | ad hoc, simulation. |
|
| 188 | Perfect Hash | ad hoc, hashing. |
|
| 190 | Circle Through Three Points | geometry, circles. |
|
| 191 | Intersection | geometry, lines, intersection, rectangles, line segment intersection. |
|
| 193 | Graph Coloring | graph theory, brute force, backtracking, NP-complete, maximum independent set. |
|
| 195 | Anagram | ad hoc, sorting, recursion. |
|
| 196 | Spreadsheet | graph theory, topological sort. |
|
| 200 | Rare Order | graph theory, topological sort. |
|
| 201 | Squares | ad hoc. |
|
| 202 | Repeating Decimals | cycle finding, decimal expansion. |
|
| 216 | Getting in Line | graph theory, TSP, brute force, backtracking. |
|
| 218 | Moth Eradication | computational geometry, convex hull. |
|
| 227 | Puzzle | ad hoc, simulation. |
|
| 231 | Testing the Catcher | DP, LIS (nonincreasing). |
|
| 232 | Crossword Answers | ad hoc. |
|
| 253 | Cube Painting | ad hoc, cyclic rotations, strings. |
|
| 254 | Towers of Hanoi | ad hoc, bignum, bit manipulations, (or recursion). |
|
| 256 | Quirksome Squares | ad hoc, number theory. |
|
| 259 | Software Allocation | graph theory, max-flow. |
|
| 260 | Il Gioco dell'X | graph theory, graph traversal, DFS. |
|
| 263 | Number Chains | ad hoc, simulation, sorting, strings. |
|
| 264 | Count on Cantor | math, binary search (or closed form solution), (like UVA 880) |
|
| 270 | Lining Up | computational geometry, sorting, line gradients (slopes). |
|
| 271 | Simply Syntax | parsing, recursive descent parsing. |
|
| 272 | Tex Quotes | ad hoc. |
|
| 275 | Expanding Fractions | cycle finding, decimal expansion (like UVA 202). |
|
| 278 | Chess | ad hoc. |
|
| 280 | Vertex | graph theory, traversal, reachability. |
|
| 288 | Arithmetic Operations with Large Integers | simple math, bignum, repeated squaring, parsing, converting from infix to postfix. |
|
| 290 | Palindroms <---> smordinilaP | ad hoc, simulation, number bases, bignum, addition, strings, palindromes. |
|
| 291 | The House of Santa Claus | graph theory, traversal, DFS (Euler tour, brute force), no input. |
|
| 294 | Divisors | number theory, sieve, primes, trial division. |
|
| 297 | Quadtree | ad hoc, recursion. |
|
| 299 | Train Swapping | sorting, counting inversions. |
|
| 300 | Maya Calendar | ad hoc. |
|
| 301 | Transportation | brute force, backtracking. |
|
| 302 | John's Trip | graph theory, Euler tour. |
|
| 303 | Pipe | computational geometry, farthest visible point, sorting, sweep line, line slope, line intersection. |
|
| 305 | Joseph | ad hoc, simulation, Josephus problem. |
|
| 306 | Cipher | permutations, repeated squaring (on permutations). |
|
| 308 | Tin Cutter | geometry, flood fill, interval compression. |
|
| 310 | L-System | graph theory, graph traversal, DFS. |
|
| 311 | Packets | ad hoc, greedy, case analysis. |
|
| 313 | Intervals | geometry, circle line tangents, sorting, line intersection. |
|
| 314 | Robot | graph theory, BFS. |
|
| 315 | Network | graph theory, articulation point, graph traversal, DFS. |
|
| 320 | Border | ad hoc (or graph theory, graph traversal). |
|
| 324 | Factorial Frequencies | ad hoc, bignum, addition. |
|
| 325 | Identifying Legal Pascal Real Constants | parsing, recursive descent parsing. |
|
| 326 | Extrapolation using a Difference Table | combinatorics, binomial theorem, difference tables. |
|
| 327 | Evaluating Simple C Expressions | parsing, recursive descent parsing, abstract syntax trees, tree traversal. |
|
| 331 | Mapping the Swaps | ad hoc, brute force. |
|
| 332 | Rational Numbers from Repeating Fractions | ad hoc, gcd. |
|
| 333 | Recognizing Good ISBNs | ad hoc. |
|
| 336 | A Node Too Far | graph theory, graph traversal, BFS. |
|
| 337 | Interpreting Control Sequences | ad hoc, simulation |
|
| 340 | Mastermind Hints | ad hoc, sorting, simulation. |
|
| 341 | Non-Stop Travel | graph theory, shortest paths, SSSP. |
|
| 343 | What Base Is This? | number theory, number base conversion, ad hoc, brute force. |
|
| 344 | Roman Digititis | ad hoc. |
|
| 347 | Run, Run, Runaround Numbers | backtracking, permutations. |
|
| 348 | Optimal Array Multiplication Sequence | DP. |
|
| 350 | Pseudo-Random Numbers | cycle finding (Floyd's cycle finding algorithm). |
|
| 352 | Seasonal War | graph theory, graph traversal, BFS, flood fill, number of components. |
|
| 353 | Pesky Palindromes | ad hoc, strings, sets, string matching, palindromes. |
|
| 355 | The Bases are Loaded | ad hoc, number base conversion. |
|
| 356 | Square Pegs and Round Holes | ad hoc, geometry, number theory. |
|
| 357 | Let Me Count The Ways | DP, coin change. |
|
| 361 | Cops and Robbers | computational geometry, convex hull, point in polygon, point on line segment. |
|
| 362 | 18,000 Seconds | ad hoc, simulation |
|
| 369 | Combinations | ad hoc, combinatorics, number theory, binomial theorem. |
|
| 371 | Ackermann Functions | ad hoc, simulation, Collatz conjecture, 3n+1 problem (same as UVA 100). |
|
| 374 | Big Mod | number theory, modulo, repeated squaring (modular). |
|
| 377 | Cowculations | ad hoc, number base conversion (base 4). |
|
| 378 | Intersecting Lines | geometry, lines. |
|
| 382 | Perfection | ad hoc, number theory, |
|
| 383 | Shipping Routes | graph theory, BFS, shortest paths. |
|
| 384 | Slurpys | ad hoc, parsing. |
|
| 386 | Perfect Cubes | ad hoc, number theory, simple math, cube root, no input. |
|
| 389 | Basically Speaking | ad hoc, number base conversion. |
|
| 392 | Polynomial Showdown | ad hoc. |
|
| 394 | Mapmaker | ad hoc, simulation. |
|
| 400 | Unix Is | ad hoc, sorting. |
|
| 401 | Palindromes | ad hoc, strings, palindromes. |
|
| 402 | M*A*S*H | ad hoc, simulation. |
|
| 406 | Prime Cuts | number theory, sieve, primes. |
|
| 408 | Uniform Generator | cycle finding (Floyd's cycle finding algorithm). |
|
| 409 | Excuses, Excuses! | ad hoc, string matching. |
|
| 410 | Station Balance | greedy, sorting, graph theory, matchings, math. |
|
| 412 | Pi | ad hoc, simulation, number theory, gcd. |
|
| 413 | Up and Down Sequences | ad hoc. |
|
| 414 | Machined Surfaces | ad hoc. |
|
| 417 | Word Index | graph theory, BFS. |
|
| 422 | Word-Search Wonder | ad hoc, string matching. |
|
| 423 | MPI Maelstrom | graph theory, shortest paths, SSSP, Dijkstra, Bellman-Ford. |
|
| 424 | Integer Inquiry | bignum, addition, simple math. |
|
| 436 | Arbitrage (II) | graph theory, all-pairs shortest paths, APSP, Floyd-Warshall, negative weight cycle (like UVA 104). |
|
| 437 | The Tower of Babylon | DP, LIS (non-standard). |
|
| 438 | Circumference of the Circle | geometry, circle through 3 points. |
|
| 439 | Knight Moves | graph theory, BFS. |
|
| 440 | Eeny Meeny Moo | ad hoc, simulation, Josephus problem. |
|
| 441 | Lotto | backtracking. |
|
| 442 | Matrix Chain Multiplication | parsing, stacks, matrix properties. |
|
| 443 | Humble Numbers | ad hoc, number theory. |
|
| 444 | Encoder and Decoder | ad hoc. |
|
| 445 | Marvelous Mazes | ad hoc, simulation. |
|
| 446 | Kibbles 'n' Bits 'n' Bits 'n' Bits | ad hoc, number base conversion. |
|
| 448 | Oops! | ad hoc, simulation, bitmasks. |
|
| 450 | Little Black Book | ad hoc, sorting. |
|
| 453 | Intersecting Circles | geometry, circle and circle intersection. |
|
| 455 | Periodic Strings | ad hoc, string matching, string period. |
|
| 457 | Linear Cellular Automata | ad hoc, simulation. |
|
| 458 | The Decoder | ad hoc. |
|
| 459 | Graph Connectivity | graph theory, connectivity, union-find. |
|
| 460 | Overlapping Rectangles | computational geometry, rectangle-rectangle intersection (very easy). |
|
| 465 | Overflow | bignum, parsing. |
|
| 466 | Mirror, Mirror | ad hoc. |
|
| 469 | Wetlands of Florida | graph theory, BFS, DFS, graph traversal, flood-fill. |
|
| 473 | Raucous Rockers | DP, iterative, space saving tricks (USACO problem, chapter 3). |
|
| 474 | Heads Tails Probability | ad hoc. |
|
| 476 | Points in Figures: Rectangles | geometry, point in rectangle. |
|
| 477 | Points in Figures: Rectangles and Circles | geometry, points in rectangles and circles. |
|
| 478 | Points in Figures: Rectangles, Circles, and Triangles | geometry, points in figures. |
|
| 481 | What Goes Up | DP, LIS. |
|
| 482 | Permutation Arrays | ad hoc, sorting. |
|
| 483 | Word Scramble | ad hoc. |
|
| 484 | The Department of Redundancy Department | ad hoc. |
|
| 485 | Pascal's Triangle of Death | bignum, number theory, no input. |
|
| 486 | English Number Translator | ad hoc. |
|
| 488 | Triangle Wave | ad hoc. |
|
| 489 | Hangman Judge | ad hoc, simulation. |
|
| 490 | Rotating Sentences | ad hoc. |
|
| 492 | Pig Latin | ad hoc. |
|
| 494 | Kindergarden Counting Game | ad hoc. |
|
| 495 | Fibonacci Freeze | bignum, addition, Fibonacci numbers. |
|
| 496 | Simply Subsets | ad hoc, set intersection. |
|
| 497 | Strategic Defense Initiative | DP, LIS. |
|
| 498 | Polly The Polynomial | polynomials, Horner's rule. |
|
| 499 | What's the frequency Kenneth? | ad hoc. |
|
| 507 | Jill Rides Again | maximum consecutive subsequence in 1D (maximum 1D sum), DP. |
|
| 514 | Rails | ad hoc, stacks. |
|
| 515 | King | graph theory, difference constraints, Bellman-Ford. |
|
| 516 | Prime Land | number theory, sieve, primes, prime factorization. |
|
| 517 | Word | cycle finding (Floyd's cycle finding algorithm). |
|
| 523 | Minimum Transport Cost | graph theory, shortest paths, all-pairs shortest paths, APSP, Floyd-Warshall, printing the path. |
|
| 524 | Prime Ring Problem | brute force, backtracking, number theory, sieve. |
|
| 530 | Binomial Showdown | ad hoc, number theory, gcd, binomial theorem. |
|
| 531 | Compromise | DP, LCS on strings. |
|
| 532 | Dungeon Master | graph theory, BFS. |
|
| 533 | Equation Solver | parsing, recursive descent parsing, AST, operator precedence grammar, simple math, solving linear equations, constant folding. |
|
| 534 | Frogger | graph theory, shortests paths, SSSP, Bellman-Ford (different distance notion). |
|
| 535 | Globetrotter | geometry, great circle distances. |
|
| 536 | Tree Recovery | trees, tree traversal, reconstructing tree from preorder and inorder. |
|
| 537 | Artificial Intelligence | ad hoc, string manipulation. |
|
| 539 | The Settlers of Catan | graph theory, longest path, NP-complete, backtracking, brute force. |
|
| 541 | Error Correction | ad hoc. |
|
| 542 | France 98 | probability theory, conditional probabilities, math. |
|
| 543 | Goldbach's Conjecture | number theory, sieve, primes, searching. |
|
| 544 | Heavy Cargo | graph theory, MST (maximum spanning tree). |
|
| 547 | DDF | ad hoc, simulation, math, number theory, divisors. |
|
| 555 | Bridge Hands | ad hoc, sorting. |
|
| 558 | Wormholes | graph theory, negative weight cycle, Bellman-Ford. |
|
| 562 | Dividing Coins | DP, 0-1 knapsack, subset sum. |
|
| 563 | Crimewave | graph theory, max-flow. |
|
| 565 | Pizza Anyone? | SAT, satisfiability, NP-complete, backtracking. |
|
| 567 | Risk | graph theory, BFS. |
|
| 568 | Just the Facts | ad hoc, number theory, factorials (or bignum). |
|
| 571 | Jugs | number theory, relative primality, the sequence iA mod B for i=0..B-1 (or graph traversal, eg. BFS). |
|
| 572 | Oil Deposits | graph theory, BFS, flood fill. |
|
| 573 | The Snail | ad hoc, simulation, math. |
|
| 574 | Sum It Up | subset sum, brute force, backtracking. |
|
| 575 | Skew Binary | ad hoc. |
|
| 576 | Haiku Review | ad hoc. |
|
| 579 | ClockHands | ad hoc. |
|
| 580 | Critical Mass | number theory, recurrences. |
|
| 583 | Prime Factors | number theory, sieve, primes, trial division, prime factorization. |
|
| 585 | Triangles | ad hoc. |
|
| 587 | There's Treasure Everywhere | ad hoc. |
|
| 590 | Always on the Run | DP. |
|
| 591 | Box of Bricks | ad hoc. |
|
| 594 | One Little, Two Little, Three Little Endians | ad hoc, bitmasking, and/or etc. |
|
| 600 | A Duckpin Tournament | ad hoc, simulation, duckpin bowling. |
|
| 601 | The Path | graph theory, shortest paths, BFS. |
|
| 602 | What Day Is It? | ad hoc, math, modulo, simulation. |
|
| 603 | Parking Lot | ad hoc, simulation. |
|
| 604 | The Boggle Game | backtracking. |
|
| 607 | Scheduling Lectures | DP. |
|
| 608 | Counterfeit Dollar | ad hoc. |
|
| 610 | Street Directions | graph theory, bridge, biconnected components, DFS. |
|
| 612 | DNA Sorting | ad hoc, sorting, inversion counting (insertion sort). |
|
| 613 | Numbers that Count | ad hoc, simulation. |
|
| 615 | Is It A Tree | graph theory, trees, connectivity. |
|
| 616 | Coconuts, Revisited | math, number theory, divisors, monkey and coconut problem. |
|
| 619 | Numerically Speaking | ad hoc, lexicographic order, bignum. |
|
| 620 | Cellular Structure | DP, parsing. |
|
| 621 | Secret Research | ad hoc. |
|
| 623 | 500! | bignum. |
|
| 624 | CD | DP, 0/1 knapsack, subset sum, or brute force. |
|
| 628 | Passwords | ad hoc, recursion. |
|
| 634 | Polygon | computational geometry, point in polygon. |
|
| 636 | Squares | number theory, ad hoc, base conversion. |
|
| 637 | Booklet Printing | ad hoc. |
|
| 639 | Don't Get Rooked | backtracking, brute force. |
|
| 640 | Self Numbers | ad hoc. |
|
| 641 | Do the Untwist | ad hoc. |
|
| 642 | Word Amalgamation | ad hoc, sorting, multimaps. |
|
| 644 | Immediate Decodability | ad hoc, string matching. |
|
| 656 | Optimal Programs | exhaustive search, graph theory, IDDFS (iterative deepening DFS). |
|
| 657 | The Die is Cast | graph theory, flood fill, DFS. |
|
| 661 | Blowing Fuses | ad hoc, simulation. |
|
| 663 | Sorting Slides | graph theory, maximum cardinality bipartite matching. |
|
| 670 | The Dog Task | graph theory, maximum cardinality bipartite matching. |
|
| 673 | Parentheses Balance | ad hoc, stacks. |
|
| 674 | Coin Change | DP, coin change. |
|
| 679 | Dropping Balls | ad hoc, trees, binary representation. |
|
| 681 | Convex Hull Finding | computational geometry, convex hull. |
|
| 684 | Integral Determinant | Gaussian elimination, matrices, determinants. |
|
| 686 | Goldbach's Conjecture (II) | number theory, sieve, primes, searching. |
|
| 694 | The Collatz Sequence | ad hoc, simulation (like UVA 100). |
|
| 696 | How Many Knights | math, closed solution. |
|
| 699 | The Falling Leaves | trees, preorder traversal. |
|
| 700 | Date Bugs | ad hoc. |
|
| 701 | Archaelogist's Dilemma | math, brute force. |
|
| 702 | The Vindictive Coach | DP. |
|
| 703 | Triple Ties: The Organizer's Nightmare | ad hoc, brute force. |
|
| 705 | Slash Maze | graphs, DFS, traversal, flood fill. |
|
| 706 | LC-Display | ad hoc. |
|
| 707 | Robbery | graph theory, graph traversal, DFS. |
|
| 709 | Formatting Text | DP, printing the solution. |
|
| 711 | Dividing up | DP. |
|
| 712 | S-Trees | trees, tree traversal. |
|
| 713 | Adding Reversed Numbers | ad hoc, simple math, bignum addition. |
|
| 714 | Copying Books | binary search, greedy (or DP). |
|
| 715 | Substitution Cipher | graph theory, DAG, topological sorting, linear ordering, Floyd-Warshall, transitive closure, strings, lexicographic comparision, cryptography, substitution cipher, sorting. |
|
| 716 | Commedia dell Arte | math, abstract algebra, 15 puzzle, generalized 15 puzzle, 15 puzzle in 3D, permutations, sign of a permutation, manhattan metric, invariants, induction. |
|
| 718 | Skyscraper Floors | graph theory, DFS, reachability, math, modular congruences, linear diophantine equations, extended gcd, Bezout's identity. |
|
| 719 | Glass Beads | strings, minimum lexicographic rotation. |
|
| 721 | Invitation Cards | graph theory, shortest paths, Dijkstra, SSSP. |
|
| 725 | Division | ad hoc, division, brute force. |
|
| 727 | Equation | parsing, infix to postfix. |
|
| 729 | Hamming Distance Problem | brute force, backtracking. |
|
| 737 | Gleaming the Cubes | computational geometry, intersection of cubes. |
|
| 739 | Soundex Indexing | ad hoc. |
|
| 740 | Baudot Data Communication Code | ad hoc. |
|
| 741 | Burrows Wheeler Decoder | string algorithms, data compression, BWT, Burrows Wheeler Transform, inverse BWT, block-sorting compression. |
|
| 748 | Exponentiation | bignum. |
|
| 750 | 8 Queens Chess Problem | backtracking, 8-queens problem. |
|
| 753 | A Plug for Unix | graph theory, max-flow. |
|
| 755 | 487-3279 | ad hoc, sorting. |
|
| 756 | Biorhythms | math, modular arithmetic, Chinese Remainder Theorem, CRT, Euclid's extended algorithm. |
|
| 762 | We Ship Cheap | graph theory, BFS, shortest paths, printing the path. |
|
| 763 | Fibinary Numbers | ad hoc, math, Fibonacci numbers, Zeckendorf representation, addition of numbers in Zeckendorf representation, (or Bignum, greedy). |
|
| 784 | Maze Exploration | graph theory, graph traversal, flood fill. |
|
| 787 | Maximum Sub-sequence Product | bignum, DP, simple math. |
|
| 793 | Network Connections | partially dynamic connected components, union-find. |
|
| 796 | Critical Links | graph theory, bridge (biconnected components). |
|
| 802 | Lead or Gold | linear programming, one-phase simplex method. |
|
| 820 | Internet Bandwidth | graph theory, max-flow. |
|
| 821 | Page Hopping | graph theory, all-pairs shortest paths, APSP, Floyd-Warshall (or BFS). |
|
| 825 | Walking on the Safe Side | graph theory, DAG, counting paths in a DAG, DP. |
|
| 834 | Continued Fractions | ad hoc. |
|
| 836 | Largest Submatrix | maximum 2D sum (special case, reduction, see UVA 108), DP. |
|
| 839 | Not so Mobile | ad hoc, simulation, simple math, recursion. |
|
| 843 | Crypt Kicker | backtracking, sorting. |
|
| 846 | Steps | ad hoc, math. |
|
| 847 | A multiplication game | ad hoc, game theory, number theory. |
|
| 848 | FMT | greedy, ad hoc. |
|
| 850 | Crypt Kicker II | ad hoc. |
|
| 861 | Little Bishops | backtracking, combinatorics, product rule. |
|
| 866 | Intersecting Line Segments | computational geometry, line segment intersection. |
|
| 872 | Ordering | graph theory, topological sort, backtracking (like UVA 124). |
|
| 880 | Cantor Fractions | math, binary search (or closed form solution), (like UVA 264). |
|
| 882 | The Mailbox Manufacturers Problem | DP. |
|
| 884 | Factorial Factors | number theory, sieve (modified), primes. |
|
| 895 | Word Problem | ad hoc. |
|
| 900 | Brick Wall Patterns | number theory, recurrences, Fibonacci numbers. |
|
| 902 | Password Search | strings, maximum repeated substring of a fixed length, hashing. |
|
| 903 | Spiral of Numbers | ad hoc, coordinate systems, simple math, (or fast simulation), (see also UVA 10920). |
|
| 904 | Overlapping Air Traffic Control | computational geometry, volume of union of 3D boxes, intersection of 3D boxes, coordinate compression. |
|
| 905 | Tacos Panchita | ad hoc, simple math, geometry. |
|
| 906 | Rational Neighbor | ad hoc, simple math, fractions, linear search. |
|
| 907 | Winterim Backpacking Trip | DP, (or binary search, greedy). |
|
| 908 | Re-connecting Computer Sites | graph theory, MST. |
|
| 909 | The BitPack Data Compression Problem | DP, printing the solution. |
|
| 910 | TV game | DP, graph theory. |
|
| 911 | Multinomial Coefficients | math, multinomial coefficients. |
|
| 912 | Live From Mars | ad hoc, string manipulation, data structures, union-find, graph theory. |
|
| 913 | Joanna and the Odd Numbers | number theory, odd numbers, summations. |
|
| 914 | Jumping Champion | number theory, sieve, primes, linear search. |
|
| 918 | ASCII Mandelbrot | ad hoc, simulation, math, complex numbers, Mandelbrot set. |
|
| 920 | Sunny Mountains | computational geometry, sweep line, line and line intersection, sorting. |
|
| 922 | Rectangle by the Ocean | geometry, area of polygon, rectangles. |
|
| 924 | Spreading the News | graph theory, shortest paths, BFS. |
|
| 925 | No more prerequisites, please! | graph theory, DAG, topological sorting, identifying direct dependencies, transitive closure, Floyd-Warshall. |
|
| 926 | Walking Around Wisely | DP, graph theory, DAG, counting paths in a DAG. |
|
| 927 | Integer Sequences from Addition of Terms | ad hoc, simple math, sum of first n integers, evaluating polynomials, quadratic equations (or binary search). |
|
| 928 | Eternal Truths | graph theory, BFS, shortest paths. |
|
| 929 | Number Maze | graph theory, shortest paths, Dijkstra (on a sparse graph), array priority queue, see CLRS exercise 24.3-6. |
|
| 944 | Happy Numbers | simple math, happy numbers, DP, brute force, cycle detection. |
|
| 948 | Fibonaccimal Base | ad hoc, math, Fibonacci numbers, Zeckendorf representation, greedy. |
|
| 957 | Popes | ad hoc. |
|
| 962 | Taxicab Numbers | simple math, brute force, (or precalculation). |
|
| 967 | Circular | number theory, sieve, primes, prefix sums. |
|
| 972 | Horizon Line | ad hoc, geometry, sweep line algorithm, computing the upper envelope. |
|
| 974 | Kaprekar Numbers | number theory. |
|
| 985 | Round And Round Maze | graph theory, shortest paths, BFS. |
|
| 986 | How Many? | DP, math, combinatorics. |
|
| 988 | Many paths, one destination | graph theory, DAG, counting number of paths in a DAG, DP. |
|
| 989 | Su Doku | sudoku, logic puzzles, backtracking, NP-complete, brute force. |
|
| 990 | Diving For Gold | DP, knapsack, printing the solution. |
|
| 991 | Safe Salutations | DP, Catalan numbers, number theory. |
|
| 993 | Product of digits | simple math, greedy, prime factorization, (see also SRM 424 Div 1 250). |
|
| 995 | Super Divisible Numbers | ad hoc, recursion, simple math, divisibility, modulo. |
|
| 997 | Show the Sequence | ad hoc, simple math, parsing. |
|
| 10000 | Longest Paths | graph theory, DAG, longest path (similar to DAG shortest paths). |
|
| 10001 | Garden of Eden | backtracking. |
|
| 10002 | Center Of Masses | computational geometry, convex hull, centroids. |
|
| 10003 | Cutting Sticks | DP, memoization. |
|
| 10004 | Bicoloring | graph theory, DFS, bipartite graphs, 2-colorability. |
|
| 10005 | Packing Polygons | computational geometry, brute force, circle through 2 points, point in circle. |
|
| 10006 | Carmichael Numbers | number theory, math, primes, pseudoprimes. |
|
| 10007 | Count the Trees | bignum, Catalan numbers, binary trees. |
|
| 10008 | What's Cryptanalysis? | ad hoc, sorting. |
|
| 10009 | All Roads Lead Where? | graph theory, BFS, shortest paths. |
|
| 10010 | Where's Waldorf | ad hoc, string matching. |
|
| 10012 | How Big Is It | geometry, brute force, backtracking. |
|
| 10013 | Super long sums | bignum, addition. |
|
| 10014 | Simple Calculations | recurrences, ad hoc. |
|
| 10015 | Joseph's Cousin | ad hoc, simulation, Josephus problem, number theory, primes, sieve. |
|
| 10017 | The Never Ending Towers of Hanoi | ad hoc, simulation, towers of hanoi, the recursive algorithm. |
|
| 10018 | Reverse and Add | ad hoc. |
|
| 10019 | Funny Encryption Method | ad hoc. |
|
| 10020 | Minimal Coverage | greedy. |
|
| 10023 | Square Root | bignum, integer square root, divide and conquer (google for Modern Computer Arithmetic). |
|
| 10024 | Curling up the cube | ad hoc, graph theory, DFS, "rolling the die", (see TopCoder SRM 417 Div 1 500, CubeNets). |
|
| 10025 | The ?1?2?3?...?n = k problem | number theory, triangular numbers. |
|
| 10026 | Shoemaker's problem | greedy, sorting. |
|
| 10029 | Edit Step Ladders | graph theory, DAG, longest paths, hashing, DP. |
|
| 10032 | Tug of War | DP, memoization, pruning, subset sum, knapsack. |
|
| 10033 | Interpreter | ad hoc, simulation. |
|
| 10034 | Freckles | graph theory, MST (or Euclidean MST). |
|
| 10035 | Primary Arithmetic | ad hoc, addition. |
|
| 10036 | Divisibility | DP, subset sum, number theory, NP-hard, pseudopolynomial. |
|
| 10037 | Bridge | ad hoc, puzzles, river crossing problem, bridge and torch problem. |
|
| 10038 | Jolly Jumpers | ad hoc. |
|
| 10039 | Railroads | graph theory, DFS, reachability. |
|
| 10040 | Ouroboros Snake | graph theory, Euler tour, De Bruijn sequences (or backtracking, brute force). |
|
| 10041 | Vito's family | sorting, median selection. |
|
| 10042 | Smith numbers | number theory, sieve, primes. |
|
| 10043 | Chainsaw Massacre | computational geometry, sweep line, maximum area empty rectangle. |
|
| 10044 | Erdos numbers | graph theory, BFS. |
|
| 10045 | Echo | ad hoc. |
|
| 10047 | The Monocycle | graph theory, BFS. |
|
| 10048 | Audiophobia | graph theory, MST. |
|
| 10049 | Self-describing sequence | ad hoc, number theory, searching. |
|
| 10050 | Hartals | ad hoc, simulation, sorting. |
|
| 10051 | Tower of Cubes | DP, graph theory, DAG, longest path. |
|
| 10054 | The Necklace | graph theory, Euler tour, connectivity. |
|
| 10055 | Hashmat The Brave Warrior | ad hoc. |
|
| 10056 | What is the Probability? | probability theory, infinite geometric series. |
|
| 10057 | A mid-summer night's dream | ad hoc, simple math, "prefix sums". |
|
| 10061 | How Many Zeros and How Many Digits? | math, number theory, primes, sieve, divisibility, logarithms. |
|
| 10062 | Tell Me The Frequencies | ad hoc, sorting. |
|
| 10063 | Knuth's Permutation | ad hoc, generating permutations. |
|
| 10065 | Useless Tile Packers | computational geometry, convex hull, area of polygons. |
|
| 10066 | The Twin Towers | DP, LCS. |
|
| 10067 | Playing with Wheels | graph theory, BFS. |
|
| 10069 | Distinct Subsequences | DP. |
|
| 10070 | Leap Year or Not Leap Year and ... | ad hoc, bignum, modular arithmetic. |
|
| 10071 | Back To High School Physics | ad hoc, physics. |
|
| 10072 | Bob Laptop Woolmer and Eddie Desktop Barlow | maximum cost weighted maximum cardinality bipartite matching, Kuhn-Munkres (Hungarian) algorithm, max-cost max-flow. |
|
| 10074 | Take the Land | maximum 2D sum (like UVA 108), DP. |
|
| 10075 | Airlines | graph theory, APSP, all-pairs shortest paths, Floyd-Warshall, geometry, great-circle distances. |
|
| 10077 | Stern-Brocot | number theory, binary search. |
|
| 10078 | The Art Gallery | computational geometry, convex hull, testing if a polygon is convex. |
|
| 10079 | Pizza Cutting | math, recurrences. |
|
| 10080 | Gopher II | graph theory, maximum cardinality bipartite matching. |
|
| 10081 | Tight words | DP. |
|
| 10082 | WERTYU | ad hoc. |
|
| 10083 | Division | bignum, math. |
|
| 10084 | Hotter Colder | computational geometry, cutting polygons by a straight line. |
|
| 10085 | The Most Distant State | graph theory, BFS, shortest paths, 8-puzzle, permutation encoding, hashmap. |
|
| 10088 | Trees on My Island | computational geometry, gcd, Pick's theorem, area computation. |
|
| 10089 | Repackaging | linear algebra, vectors, angles. |
|
| 10090 | Marbles | number theory, extended Euclidean algorithm, gcd. |
|
| 10092 | The Problem with the Problemsetter | graph theory, maximum cardinality bipartite matching. |
|
| 10093 | An Easy Problem | number theory, number base conversion, modulo. |
|
| 10094 | Place The Guards | ad hoc, case analysis, even/odd numbers, spotting the pattern, (or backtracking, pruning). |
|
| 10097 | The Color Game | graph theory, shortest paths, BFS. |
|
| 10098 | Generating Fast Sorted Permutations | ad hoc, sorting, recursion (like UVA 195). |
|
| 10099 | Tourist Guide | graph theory, SSSP, shortest paths, Bellman-Ford (different relaxation operation). |
|
| 10100 | Longest Match | DP, LCS (on words), parsing. |
|
| 10101 | Bangla Numbers | ad hoc. |
|
| 10102 | The Path in the Colored Field | graph theory, BFS, shortest paths. |
|
| 10103 | Karpovich Blocks | graph theory, DFS. |
|
| 10104 | Euclid Problem | number theory, extended euclidean algorithm, gcd. |
|
| 10105 | Polynomial coefficient | number theory, binomial coefficients. |
|
| 10106 | Product | bignum, simple math, multiplication. |
|
| 10107 | What is the Median | sorting, median selection, dynamic algorithm. |
|
| 10108 | The Mosquito Killer Mosquitos | bignum, square roots. |
|
| 10109 | Solving Systems of Linear Equations | systems of linear equations, Gaussian elimination, exact rational arithmetic. |
|
| 10110 | Light, more light | number theory, math, divisors, prime factorization, perfect squares. |
|
| 10111 | Find the Winning Move | DP, tic-tac-toe, game tree evaluation. |
|
| 10112 | Myacm Triangles | geometry, brute force, point in triangle, triangle area. |
|
| 10113 | Exchange Rates | graph theory, DFS, gcd. |
|
| 10114 | Loansome Car Buyer | ad hoc, simulation. |
|
| 10115 | Automatic Editing | string manipulation, ad hoc. |
|
| 10116 | Robot Motion | ad hoc, simulation. |
|
| 10117 | Nice Milk | computational geometry, cutting polygons by lines, brute force, vectors. |
|
| 10118 | Free Candies | DP. |
|
| 10120 | Gift?! | math, simulation. |
|
| 10122 | Mysterious Mountain | graph theory, maximum cardinality bipartite matching, binary search (bisection). |
|
| 10123 | No Tipping | geometry, physics, backtracking, brute force. |
|
| 10125 | Sumsets | brute force, sorting. |
|
| 10126 | Zipf's Law | ad hoc, string manipulation. |
|
| 10127 | Ones | number theory, modular arithmetic. |
|
| 10128 | Queue | DP, permutations, recurrences. |
|
| 10129 | Play on Words | graph theory, Euler tour, connectivity, union-find (or DFS). |
|
| 10130 | SuperSale | DP, knapsack. |
|
| 10131 | Is Bigger Smarter? | DP, LIS, LCS, sorting (or graph theory, DAG, longest path). |
|
| 10132 | File Fragmentation | sorting, ad hoc. |
|
| 10133 | Audubon's Stormy Artic Trip | graph theory, DAG, traversal. |
|
| 10134 | Autofish | ad hoc, simulation. |
|
| 10135 | Herding Frosh | computational geometry, convex hull, brute force, sorting. |
|
| 10136 | Chocolate Chip Cookies | geometry, circles, circle through 2 points, point in circle. |
|
| 10137 | The Trip | ad hoc. |
|
| 10138 | CDVII | ad hoc, simulation, sorting. |
|
| 10139 | Factovisors | number theory. |
|
| 10140 | Prime Distances | number theory, primality testing, sieve, segmented sieve. |
|
| 10141 | Request for Proposal | ad hoc. |
|
| 10142 | Australian Voting | ad hoc, simulation. |
|
| 10144 | Expression | math, Boolean logic, NAND gates, binary addition. |
|
| 10145 | Lock Manager | ad hoc, simulation. |
|
| 10146 | Dictionary | ad hoc, string manipulation. |
|
| 10147 | Highways | graph theory, MST. |
|
| 10148 | Advertisement | greedy, sorting. |
|
| 10149 | Yahtzee | DP, bitmasks. |
|
| 10150 | Doublets | backtracking, sorting. |
|
| 10151 | Spaghetti | graph theory, graph traversal, DFS, DP, program equivalence, control flow graph, dataflow analysis, string manipulation, loop unrolling, cycle detection. |
|
| 10152 | Shellsort | ad hoc, stacks. |
|
| 10154 | Weights and Measures | DP, sorting, LIS (modified). |
|
| 10156 | Sala-ma-Sond, A Nice Little Pond | ad hoc, simulation, pretty printing |
|
| 10157 | Expressions | DP, recurrences, Catalan numbers, bignum. |
|
| 10158 | War | data structures, augmenting data structures, union-find, equivalence relations (see also 10505). |
|
| 10159 | Star | DP, geometry, triangular grids. |
|
| 10160 | Servicing Stations | backtracking, graph theory, dominating set, NP-complete. |
|
| 10161 | Ant on a Chessboard | ad hoc, math. |
|
| 10162 | Last Digit | cycle finding, number theory, modulo, bignum. |
|
| 10163 | Storage Keepers | DP, binary search. |
|
| 10164 | Number Game | math. |
|
| 10165 | Stone Game | combinatorial game theory, nim. |
|
| 10166 | Travel | graph theory, shortest paths, SSSP, DAG shortest paths, DP. |
|
| 10167 | Birthday Cake | computational geometry, brute force. |
|
| 10168 | Summation of 4 primes | math, number theory, sieve, primes. |
|
| 10169 | Urn-ball probabilities | DP, probability theory. |
|
| 10170 | The Hotel with Infinte Rooms | number theory, quadratic equation. |
|
| 10171 | Meeting Prof. Miguel | graph theory, shortest paths, Floyd-Warshall. |
|
| 10172 | The Lonesome Cargo Distributor | ad hoc, simulation. |
|
| 10173 | Smallest Bounding Rectangle | computational geometry, minimum area enclosing rectangle, convex hull, binary search, rotations, extreme point in a given direction (or rotating calipers). |
|
| 10174 | Couple-Bachelor-Spinster Numbers | number theory, math, case analysis (modulo 4). |
|
| 10176 | Ocean Deep! Make it shallow! | number theory, divisibility, modulo. |
|
| 10177 | (2/3/4)-D Sqr/Rects/Cubes/Boxes? | simple math, summations, sums of i^th powers of the first n integers. |
|
| 10178 | Count the Faces | graph theory, Euler's formula, connectivity, connected components, graph traversal, DFS. |
|
| 10179 | Irreducible Basic Fractions | math, number theory, totient function, prime factorization. |
|
| 10180 | Rope Crisis In Ropeland | geometry, closest point on line segment, circles, tangents, angles. |
|
| 10181 | 15 Puzzle Problem | 15 puzzle, graph theory, IDDFS (iterative deepening DFS), heuristics, math, abstract algebra, determining if there is no solution. |
|
| 10182 | Bee Maja | ad hoc, simulation, coordinate systems, hexagonal grid. |
|
| 10183 | How many Fibs? | bignum, math, Fibonacci numbers. |
|
| 10185 | Phylogenetic Trees Inherited | strings, trees, complete binary tree, greedy, (or DP). |
|
| 10186 | Euro Cup 2000 | ad hoc, backtracking, brute force. |
|
| 10187 | From Dusk till Dawn | graph theory, BFS, shortest paths. |
|
| 10188 | Automated Judge Script | ad hoc, simulation. |
|
| 10189 | Mine Sweeper | ad hoc. |
|
| 10190 | Divide but not quite Conquer | ad hoc, simulation, recursion. |
|
| 10191 | Longest Nap | ad hoc. |
|
| 10192 | Vacation | DP, LCS (Longest Common Subsequence). |
|
| 10193 | All You Need Is Love | number theory, gcd. |
|
| 10194 | Football | ad hoc, sorting. |
|
| 10195 | Knights of the round table | geometry, Heron's formula, radius of triangle incircle. |
|
| 10196 | Check The Check | ad hoc, simulation. |
|
| 10197 | Learning Portuguese | ad hoc, string manipulation. |
|
| 10198 | Counting | bignum, recurrences. |
|
| 10199 | Tourist Guide | graph theory, connectivity, DFS, articulation points. |
|
| 10200 | Prime Time | number theory, prefix sum. |
|
| 10201 | Adventures in Moving - Part IV | DP. |
|
| 10202 | Pairsumonious Numbers | number theory, math, sorting. |
|
| 10203 | Snow Clearing | graph theory, Euler tour. |
|
| 10205 | Stack 'em Up | ad hoc. |
|
| 10207 | The Unreal Tournament | DP, bignum, math, binomial coefficients. |
|
| 10209 | Is this Integration | geometry. |
|
| 10212 | The Last Non-zero Digit | number theory, modulo. |
|
| 10213 | How many pieces of land | bignum, Moser's circle problem, recurrences, combinatorics, binomial coefficients. |
|
| 10215 | Largest-Smallest Box | geometry, quadratic equation, calculus. |
|
| 10219 | Find the Ways! | number theory, combinatorics. |
|
| 10220 | I Love Big Numbers! | simple math, bignum, factorials. |
|
| 10221 | Satellites | geometry, circles, triangles, cosine relation. |
|
| 10222 | Decode The Mad Man | ad hoc. |
|
| 10223 | How Many Nodes? | number theory, Catalan numbers, binary trees. |
|
| 10225 | Discrete Logging | math, discrete logarithm, baby-step giant-step algorithm. |
|
| 10226 | Hardwood Species | ad hoc, data structures, trie. |
|
| 10227 | Forests | ad hoc. |
|
| 10229 | Modular Fibonacci | number theory, modular arithmetic, matrices, repeated squaring, Fibonacci numbers. |
|
| 10235 | Simply Emirp | number theory, sieve, primes. |
|
| 10236 | The Fibonacci Primes | number theory, math, gcd, Fibonacci numbers. |
|
| 10242 | Fourth Point!!! | geometry, ad hoc. |
|
| 10243 | Fire! Fire!! Fire!!! | graph theory, minimum vertex cover in a tree. |
|
| 10245 | The Closest Pair Problem | computational geometry, closest pair problem, sorting, divide and conquer. |
|
| 10246 | Asterix and Obelix | graph theory, all-pairs shortest paths, APSP, Floyd-Warshall, sorting. |
|
| 10247 | Complete Tree Labeling! | DP, recurrences, binomial coefficients, permutations, bignum. |
|
| 10249 | The Grand Dinner | greedy method (or graph theory, max-flow). |
|
| 10252 | Common Permutation | ad hoc. |
|
| 10254 | The Priest Mathematician | math, bignum, recurrences, Hanoi towers with four pegs. |
|
| 10258 | Contestant scoreboard | ad hoc. |
|
| 10259 | Hippity Hopscotch | graph theory, DAG, longest path, DP (or topological sorting). |
|
| 10260 | Soundex | ad hoc. |
|
| 10261 | Ferry Loading | DP, number split, subset sum, knapsack, pseudopolynomial. |
|
| 10263 | Railway | computational geometry, closest point on line segment. |
|
| 10267 | Graphical Editor | ad hoc, simulation. |
|
| 10268 | 498 | ad hoc, evaluating a polynomial, derivates, simple math. |
|
| 10269 | Adventure of Super Mario | graph theory, shortest paths, SSSP, Dijkstra (on a modified graph). |
|
| 10271 | Chopsticks | DP, sorting. |
|
| 10273 | Eat or not to Eat? | data structures, priority queue, simulation, simple math, gcd, lcm, periodicity. |
|
| 10275 | Guess The Number | math, logarithms, fingerprinting (or hashing), (Bignum). |
|
| 10276 | Hanoi Tower Troubles Again | graph theory, DFS, backtracking. |
|
| 10277 | Boastin' Red Socks | probability theory, searching. |
|
| 10278 | Fire Station | graph theory, shortest paths, Dijkstra, multiple souces. |
|
| 10279 | Minesweeper | ad hoc, simulation. |
|
| 10280 | Old Wine Into New Bottles | DP, graph theory, Dijkstra. |
|
| 10281 | Average Speed | ad hoc. |
|
| 10282 | Babelfish | ad hoc, hashing, dictionary problem. |
|
| 10285 | Longest Run on a Snowboard | DP. |
|
| 10286 | The Trouble with a Pentagon | geometry, sine theorem, angles. |
|
| 10293 | Word Length and Frequency | ad hoc, strings. |
|
| 10295 | Hay Points | ad hoc. |
|
| 10296 | Jogging Trails | graph theory, Chinese postman problem, all-pairs shortest paths, Floyd-Warshall, minimum cost maximum matching in general graphs, DP. |
|
| 10297 | Beavergnaw | geometry, cones, cylinders, volumes. |
|
| 10298 | Power Strings | ad hoc, string matching, string period. |
|
| 10299 | Relatives | math, number theory, totient, divisors, primes, (see also UVA 11064). |
|
| 10300 | Ecological Premium | ad hoc. |
|
| 10301 | Rings and Glue | computational geometry, circle & circle intersection, disjoint sets, union-find, graph theory, connected components. |
|
| 10302 | Summation of Polynomials | bignum, sums. |
|
| 10303 | How Many Trees | bignum, combinatorics, recurrences, Catalan numbers. |
|
| 10304 | Optimal Binary Search Tree | DP. |
|
| 10305 | Ordering Tasks | graph theory, topological sort. |
|
| 10306 | e-Coins | DP, coin change (a bit modified). |
|
| 10307 | Killing Aliens in Borg Maze | graph theory, MST, shortests paths, BFS. |
|
| 10308 | Roads in the North | graph theory, diameter of an unrooted tree, BFS. |
|
| 10309 | Turn the Lights Off | ad hoc, brute force (or math, linear algebra, solving linear equation systems). |
|
| 10310 | Dog and gopher | geometry, brute force. |
|
| 10311 | Goldbach and Euler | number theory, sieve, primes, searching, trial division. |
|
| 10312 | Expression Bracketing | combinatorics, number theory, Catalan numbers, super Catalan numbers, number of binary bracketings, number of bracketings. |
|
| 10313 | Pay the Price | DP, coin change, prefix sums. |
|
| 10315 | Poker Hands | ad hoc, ranking poker hands. |
|
| 10316 | Airline Hub | geometry, great circle distances, brute force. |
|
| 10319 | Manhattan | 2-SAT, graph theory, reachability, strongly connected components. |
|
| 10321 | Polygon Intersection | computational geometry, intersection of convex polygons, cutting polygons by a straight line. |
|
| 10323 | Factorial! You Must Be Kidding | number theory, factorials. |
|
| 10324 | Zeros and Ones | ad hoc, prefix sums. |
|
| 10325 | The Lottery | number theory, divisibility, gcd, lcm, inclusion-exclusion. |
|
| 10327 | Flip Sort | sorting, counting inversions. |
|
| 10328 | Coin Toss | bignum, combinatorics, recurrences. |
|
| 10329 | Combinatorial Expression | bignum, number theory, sieve, primes, prime factorization. |
|
| 10330 | Power Transmission | graph theory, max-flow, vertex constraints. |
|
| 10334 | Ray Through Glasses | bignum, Fibonacci numbers. |
|
| 10336 | Rank the Languages | graph theory, graph traversal, DFS, flood fill. |
|
| 10338 | Mischievous Children | math, multinomial coefficients. |
|
| 10340 | All in All | greedy (or DP, LCS). |
|
| 10341 | Solve It | math, bisection, root finding, numerical analysis. |
|
| 10342 | Always Late | graph theory, K shortest paths (K=2), Bellman-Ford (modified), Dijkstra (modified). |
|
| 10344 | 23 Out of 5 | backtracking, brute force. |
|
| 10346 | Peter's Smokes | ad hoc. |
|
| 10347 | Medians | geometry, triangle area from medians. |
|
| 10348 | Submarines | computational geometry, line and line segment intersection, point in polygon, line segment in polygon. |
|
| 10349 | Antenna Placement | graph theory, maximum cardinality bipartite matching. |
|
| 10350 | Liftless Eme | graph theory, shortest paths, SSSP, DAG shortest paths. |
|
| 10351 | Diamond | geometry, math, ellipsoid, ellipse. |
|
| 10355 | Superman | geometry, vector equation of a line, cartesian equation of sphere, quadratic equations. |
|
| 10358 | Matrix | game trees (graphs), solving game trees (graphs), DP, memoization, simple recursive games, retrograde analysis. |
|
| 10359 | Tiling | math, recurrences, big num. |
|
| 10361 | Automatic Poetry | ad hoc, string manipulation. |
|
| 10363 | Tic Tac Toe | ad hoc, 3 x 3 tic tac toe, board games, evaluating board positions. |
|
| 10365 | Blocks | ad hoc, number theory, divisors. |
|
| 10367 | Equations | equations, gcd, fractions (many, many special cases). |
|
| 10368 | Euclid's Game | ad hoc, gcd. |
|
| 10369 | Arctic Networks | graph theory, MST, Kruskal's algorithm, union-find (or binary search). |
|
| 10370 | Above Average | ad hoc. |
|
| 10374 | Election | ad hoc. |
|
| 10375 | Choose and Divide | ad hoc, math, binomial coefficients. |
|
| 10377 | Maze Traversal | ad hoc, simulation. |
|
| 10378 | Complex Numbers | math, complex numbers, De Moivre's theorem. |
|
| 10380 | Shogi Tournament | graph theory, max-flow, searching (linear/binary search). |
|
| 10382 | Watering Grass | computational geometry, greedy, interval covering, sorting. |
|
| 10385 | Duathlon | numerical analysis, ternary search. |
|
| 10387 | Billiard | geometry, math, trigonometry. |
|
| 10391 | Compound Words | hashing, hash tables, strings. |
|
| 10392 | Factoring Large Numbers | number theory, math, primes, sieve, factorization. |
|
| 10394 | Twin Primes | number theory, primes, sieve. |
|
| 10397 | Connect the Campus | graph theory, MST. |
|
| 10400 | Game Show Math | DP. |
|
| 10401 | Injured Queen Problem | DP. |
|
| 10404 | Bachet's Game | DP, games, winning/losing positions. |
|
| 10405 | Longest Common Subsequence | DP, LCS. |
|
| 10406 | Cutting Tabletops | computational geometry, convex polygons, line-line intersection, area of a polygon, vectors. |
|
| 10407 | Simple Division | number theory, remainders, gcd. |
|
| 10408 | Farey Sequences | number theory, gcd, fractions, sorting. |
|
| 10409 | Die Game | ad hoc. |
|
| 10410 | Tree Reconstruction | graph theory, trees, reconstructing tree from DFS and BFS traversal. |
|
| 10415 | Eb Alto Saxophone Player | ad hoc, simulation. |
|
| 10420 | List of Conquests | ad hoc, sorting |
|
| 10422 | Knights in Fen | graph theory, BFS, hashing. |
|
| 10424 | Love Calculator | ad hoc. |
|
| 10427 | Naughty Sleepy Boys | ad hoc. |
|
| 10432 | Polygon Inside a Circle | geometry, area of a regular convex polygon. |
|
| 10440 | Ferry Loading II | greedy. |
|
| 10443 | Rock, Scissors, Paper | ad hoc, simulation. |
|
| 10450 | World Cup Noise | math, bignum, number theory, recurrences. |
|
| 10451 | Ancient Village Sports | geometry. |
|
| 10452 | Marcus Help! | graph theory, graph traversal, DFS. |
|
| 10453 | Make Palindrome | DP, printing solution, strings, palindromes. |
|
| 10459 | The Tree Root | graph theory, diameter of an unrooted tree, center of an unrooted tree, DFS. |
|
| 10465 | Homer Simpson | DP. |
|
| 10469 | To Carry or not to Carry | ad hoc, xor. |
|
| 10473 | Simple Base Conversion | ad hoc, number base conversion (or printf). |
|
| 10474 | Where is the Marble? | ad hoc, counting sort, bucket array. |
|
| 10482 | The Candyman Can | DP, sorting, subset sum. |
|
| 10487 | Closests Sums | ad hoc, brute force. |
|
| 10489 | Boxes of Chocolates | ad hoc, number theory, modulo. |
|
| 10490 | Mr. Azad and His Son | number theory, perfect numbers, divisors, primality testing. |
|
| 10491 | Cows and Cars | probability theory, conditional probabilities, Monty Hall problem (generalized). |
|
| 10493 | Cats, with or without Hats | ad hoc, simple math, number of internal nodes and leaves in a tree with degree n. |
|
| 10494 | If We Were a Child Again | bignum, division. |
|
| 10496 | Collecting Beepers | graph theory, TSP, DP (or brute force). |
|
| 10498 | Happiness | linear programming, one-phase simplex method. |
|
| 10499 | The Land of Justice | ad hoc, math. |
|
| 10500 | Robot Maps | ad hoc, simulation, pretty-printing. |
|
| 10502 | Counting Rectangles | ad hoc. |
|
| 10505 | Montesco vs Capuleto | data structures, augmenting data structures, union-find, equivalence relations (see also 10158). |
|
| 10508 | Word Morphing | backtracking, brute force, string matching. |
|
| 10509 | R U Kidding Mr. Feynman | ad hoc, numerical approximation. |
|
| 10510 | Cactus | graph theory, strongly connected components, directed cactus graph, determining if a graph is a directed cactus, graph traversal, DFS, DFS edge classification, back edges. |
|
| 10511 | Councilling | graph theory, max-flow, vertex constraints. |
|
| 10515 | Power et al | cycle finding. |
|
| 10518 | How Many Calls? | recurrence relations, fibonacci numbers using repeated squaring, modulo (or cycle finding, Floyd's Cycle Finding Algorithm). |
|
| 10519 | Really Strange | bignum, recurrences. |
|
| 10523 | Very Easy!!! | bignum, number theory, exponentiation. |
|
| 10527 | Persistent Numbers | simple math, greedy, bignum, prime factorization, (see also UVA 993, see also SRM 424 Div 1 250). |
|
| 10530 | Guessing Game | ad hoc, simulation. |
|
| 10533 | Digit Primes | number theory, sieve. |
|
| 10534 | Wavio Sequence | DP, LIS (in O(nlogn), binary search). |
|
| 10539 | Almost Prime Numbers | number theory, divisibility, prime numbers, sieve, binary search. |
|
| 10549 | Russian Dolls | DP, printing solution. |
|
| 10550 | Combination Lock | ad hoc. |
|
| 10551 | Basic Remains | number theory, math, modulo, number base conversion. |
|
| 10553 | Treasure Map | computational geometry, angles, distance from point to line segment. |
|
| 10554 | Calories From Fat | ad hoc. |
|
| 10557 | XYZZY | graph theory, Bellman-Ford, negative (positive) cycles, reachability. |
|
| 10558 | A Brief Gerrymander | DP, printing the solution. |
|
| 10559 | Blocks | DP. |
|
| 10564 | Paths Through The Hourglass | DP, printing solution. |
|
| 10570 | Meeting with Aliens | ad hoc, minimum number of swaps, sorting, permutations, greedy. |
|
| 10573 | Geometry Paradox | geometry. |
|
| 10579 | Fibonacci Numbers | bignum, recurrences, Fibonacci numbers. |
|
| 10583 | Ubiquitous Religions | graph theory, union-find. |
|
| 10586 | Polynomial Remains | polynomials, long division, math. |
|
| 10589 | Area | ad hoc, geometry, point in circle. |
|
| 10591 | Happy Number | simple math, happy numbers, cycle finding (Floyd's cycle finding algorithm). |
|
| 10593 | Kites | DP. |
|
| 10594 | Data Flow | graph theory, min-cost max-flow. |
|
| 10596 | Morning Walk | graph theory, Euler tour, DFS, connectivity. |
|
| 10599 | Robots (II) | DP. |
|
| 10600 | ACM Contest and Blackout | graph theory, MST, second-best MST. |
|
| 10601 | Cubes | math, number of edge colorings of a cube under rotations, Burnside's lemma, orbits, abstract algebra, group theory, combinatorics, cubes, rotations, factorials, multinomial coefficients. |
|
| 10602 | Editor Nottobad | greedy. |
|
| 10603 | Fill | graph theory, shortest paths, SSSP, Dijkstra, DP. |
|
| 10604 | Chemical Reaction | DP. |
|
| 10605 | Mines for Diamonds | DP, all subsets, bitmasks, graph theory, path cover, geometry, manhattan distance, (similar to TSP). |
|
| 10606 | Opening Doors | math, perfect squares, divisors, bignum, integer square root (or binary search). |
|
| 10607 | Siege | graph theory, connected components, shortest paths, BFS. |
|
| 10608 | Friends | graph theory, union-find. |
|
| 10610 | Gopher and Hakws | graph theory, BFS, shortest paths, SSSP. |
|
| 10611 | The Playboy Chimp | ad hoc. |
|
| 10613 | Mushroom Misery | computational geometry, circles, 2D grid, counting number of grid squares inside the circles, distance from point to line segment, divide and conquer, (or sweepline algorithm). |
|
| 10614 | Dreadful Vectors | parsing, recursive descent parsing, LL(1), context-free grammars, operator precedence, operator associativity, abstract syntax tree, AST, type checking, tree traversal, simple math, vectors, scalars, cross product, dot product. |
|
| 10615 | Rooks | graph theory, minimum edge coloring of a bipartite graph, Hall's marriage theorem, maximum-cardinality bipartite matching, d-regular bipartite multigraph. |
|
| 10616 | Divisible Group Sums | DP, math, modulo. |
|
| 10617 | Again Palindromes | DP. |
|
| 10618 | Tango Tango Insurrection | DP, printing the solution, Dance Dance Revolution. |
|
| 10619 | Advanced Causal Measurements | binary search, interval covering, greedy, exponential search. |
|
| 10622 | Perfect Pth Powers | math, number theory, prime factorization, gcd. |
|
| 10623 | Thinking Backward | combinatorial geometry, arrangements, math, plane division by circles, triangles, ellipses, maximum number of regions, multivariate equations, quadratic equation in one variable. |
|
| 10624 | Super Number | math, divisibility, backtracking, precalculation. |
|
| 10625 | GNU = GNU'sNotUnix | math, linear recurrences, linear algebra, linear transformations, repeated squaring on a matrix, (or DP). |
|
| 10626 | Buying Coke | DP. |
|
| 10627 | Infinite Race | math, gcd, fractions. |
|
| 10633 | Rare Easy Problem | ad hoc, number theory, modulo, floor. |
|
| 10634 | Say NO To Memorization | math, number of terms in equation with degree n and v variables, combinatorics, binomial coefficients, combinations with repetitions, number of non-negative integer solutions of x0 + x1 + ... + x_m = k. |
|
| 10635 | Prince and Princess | DP, LIS in O(nlogn), reduction from special case of LCS to LIS. |
|
| 10637 | Coprimes | backtracking, pruning, sorting, math, number theory, partitions, coprimes, gcd. |
|
| 10642 | Can You Solve It? | ad hoc, counting, simple math. |
|
| 10643 | Facing Problem With Trees | DP, bignum, trees, number of ordered binary trees with m edges. |
|
| 10644 | Floor Tiles | geometry, tiling with L-pieces, backtracking, brute force, small cases, spotting the pattern, simple math. |
|
| 10645 | Menu | DP, printing the solution. |
|
| 10648 | Chocolate Box | DP, math, probability theory. |
|
| 10650 | Determinate Prime | math, number theory, primes, sieve. |
|
| 10651 | Pebble Solitaire | DP, bitmasks. |
|
| 10654 | The Uxuhul Voting System | DP. |
|
| 10655 | Contemplation! Algebra | math, complex numbers, linear algebra, linear transformation, linear recurrences, repeated squaring on a matrix. |
|
| 10656 | Maximum Sum II | ad hoc. |
|
| 10660 | Citizen Attention Offices | ad hoc, brute force, simple math, grids, manhattan distance. |
|
| 10661 | The Perspectographer | graph theory, vertex coloring, computing the chromatic number of a graph, NP-complete, backtracking, pruning, lower bound by finding maximum clique size. |
|
| 10662 | The Wedding | ad hoc, brute force. |
|
| 10663 | Non-Powerful Subsets | maximal sets, greedy, DP, subset sum, simple math, powers. |
|
| 10664 | Luggage | DP, subset sum. |
|
| 10665 | Diatribe against Pigeonholes | DP, sorting, printing the lexicograpically smallest solution. |
|
| 10666 | The Eurocup is here! | ad hoc, simple math, tournament tree, binary number system, number of bits, index of least significant bit. |
|
| 10667 | Largest Block | maximum 2D sum (special case, reduction, see UVA 108), DP. |
|
| 10668 | Expanding Rods | math, numerical analysis, bisection, root-finding, geometry, circles. |
|
| 10669 | Three powers | math, binary number system, bignum. |
|
| 10670 | Work Reduction | greedy. |
|
| 10672 | Marbles on a tree | graph theory, trees, simple math, subtree sizes, DFS. |
|
| 10673 | Play with Floor and Ceil | number theory, math. |
|
| 10678 | The Grazing Cow | geometry, area of an ellipsis, Pythagoras' theorem, simple math. |
|
| 10679 | I Love Strings!!! | strings, string matching, substring queries, suffix tree, suffix array, (or Aho-Corasick). |
|
| 10680 | LCM | math, lcm of the first N integers, gcd, sieve, primes, prime powers. |
|
| 10681 | Teobaldo's Trip | graph theory, reachability using k edges, adjacency matrix, repeated squaring, (or DP). |
|
| 10682 | Forro Party | graph theory, BFS. |
|
| 10683 | The decadary watch | ad hoc, simple math. |
|
| 10684 | The Jackpot | maximum consecutive 1D sum, DP. |
|
| 10685 | Nature | graph theory, DFS, connected components, finding the size of the largest connected component, union-find. |
|
| 10688 | The Poor Giant | DP. |
|
| 10689 | Yet Another Number Sequence | math, Fibonacci numbers, linear recurrences, modular arithmetic, linear algebra, linear transformations, repeated squaring on a matrix, (or Pisano period, periodicity, cycle finding). |
|
| 10690 | Expression Again | DP, subset sum, math, minimizing/maximizing a product when the sum is constant. |
|
| 10691 | Subway | computational geometry, sweepline algorithm on a circle, sorting, greedy, trigonometry. |
|
| 10693 | Traffic Volume | math, calculus, derivative, local maximum, optimization, physics, velocity. |
|
| 10694 | Combinatorial Summation | math, summations, changing the order of summation, binomial coefficients, Fibonacci numbers, partial sums, bignum. |
|
| 10696 | f91 | ad hoc, math, recursion, McCarthy 91 function. |
|
| 10697 | Firemen Barracks | computational geometry, perpendicular bisectors, line-line intersection, (floating-point precision problems). |
|
| 10698 | Football Sort | ad hoc, simulation, sorting, pretty printing. |
|
| 10699 | Count the Factors | math, number theory, sieve, primes, trial division. |
|
| 10700 | Camel Trading | greedy, math, (or backtracking, DP). |
|
| 10701 | Pre, in and post | graph theory, trees, tree traversal, reconstructing tree from preorder and inorder traversal. |
|
| 10702 | Travelling Salesman | DP, graph theory. |
|
| 10703 | Free Spots | ad hoc, simulation. |
|
| 10704 | Traffic! | graph theory, shortest paths, BFS, searching, (Rush Hour game). |
|
| 10705 | The Fun Number System | math, number base conversion. |
|
| 10706 | Number Sequence | math, binary search. |
|
| 10707 | 2-D Nim | graph theory, graph traversal, DFS, connected components, sorting, rotations, flips, canonical orderings, isomorphism. |
|
| 10710 | Chinese Shuffle | ad hoc, math, repeated squaring, modulo. |
|
| 10712 | Count the Numbers | DP. |
|
| 10714 | Colliding Ants | greedy. |
|
| 10716 | Evil Straw Warts Live | greedy. |
|
| 10717 | Mint | ad hoc, math, gcd, lcm, brute force. |
|
| 10718 | Bit Mask | ad hoc, greedy, bitmasks. |
|
| 10719 | Quotient Polynomial | simple math, polynomials, division. |
|
| 10720 | Graph Construction | graph theory, graphic sequence, Erdos-Gallai condition, (or greedy, Havel-Hakimi). |
|
| 10721 | Bar Codes | DP. |
|
| 10722 | Super Lucky Numbers | DP, bignum. |
|
| 10723 | Cyborg Genes | DP, strings, shortest common supersequence. |
|
| 10724 | Road Construction | graph theory, all-pairs shortest paths, APSP, Floyd-Warshall. |
|
| 10728 | Help! | graph theory, graph traversal, DFS, strings. |
|
| 10730 | Antiarithmetic? | ad hoc. |
|
| 10731 | Test | graph theory, strongly connected components. |
|
| 10733 | The Colored Cubes | math, number of face colorings of a cube under rotations, Burnside's lemma, orbits, abstract algebra, group theory, combinatorics, cubes, rotations. |
|
| 10735 | Euler Circuit | graph theory, Euler tour in a mixed graph, max-flow, Euler tour. |
|
| 10738 | Riemann vs. Mertens | number theory, sieve, primes. |
|
| 10739 | String to Palindrome | DP, variation of edit distance. |
|
| 10740 | Not the Best | graph theory, k'th shortest paths, single source shortest paths, SSSP, Dijkstra. |
|
| 10745 | Dominant Strings | strings, trie, sorting. |
|
| 10746 | Crime Wave - The Sequel | graph theory, minimum cost weighted bipartite matching (min-cost max-flow). |
|
| 10747 | Maximum Subsequence | math, greedy, case analysis (special cases). |
|
| 10750 | Beautiful Points | computational geometry, closest pair of points, sorting, divide and conquer. |
|
| 10755 | Garbage Heap | maximum 3D sum (similar to UVA 108), DP. |
|
| 10759 | Dice Throwing | DP, math, probability theory, fractions, rational arithmetic. |
|
| 10763 | Foreign Exchange | ad hoc, sorting. |
|
| 10766 | Organizing the Organization | graph theory, number of spanning trees of a graph, Kirchhoff's matrix tree theorem, linear algebra, matrices, Gaussian elimination, determinants, primes, fields. |
|
| 10776 | Determine the Combination | combinatorics, generating all combinations of r letters given n letters, recursion, sorting. |
|
| 10779 | Collector's Problem | graph theory, max-flow. |
|
| 10780 | Again Prime? No time. | number theory, primes, prime factorization, sieve, factorials, math. |
|
| 10783 | Odd Sum | ad hoc. |
|
| 10784 | Diagonal | combinatorics, ad hoc. |
|
| 10785 | The Mad Numerologist | ad hoc, sorting. |
|
| 10787 | Modular Equations | ad hoc, simple math, modular arithmetic. |
|
| 10789 | Prime Frequency | number theory, primes, counting, ad hoc. |
|
| 10790 | How Many Points of Intersection? | combinatorics, math, binomial coefficients. |
|
| 10791 | Minimum Sum LCM | number theory, math, gcd, lcm, primes, sieve, prime factorization. |
|
| 10793 | The Orc Attack | graph theory, all-pairs shortest paths, Floyd-Warshall. |
|
| 10799 | OOPS! They did it Again | math, arithmetic sequences, formula for an arithmetic sequence, summations, floors. |
|
| 10800 | Not That Kind of Graph | ad hoc, simulation. |
|
| 10801 | Lift Hopping | graph theory, shortest paths, SSSP, Dijkstra. |
|
| 10802 | Lex Smallest Drive | graph theory, graph traversal, DFS, cycle detection, greedy, sorting. |
|
| 10803 | Thunder Mountain | graph theory, all-pairs shortest paths, APSP, Floyd-Warshall. |
|
| 10804 | Gopher Strategy | graph theory, maximum cardinality bipartite matching, binary search (bisection). |
|
| 10805 | Cockroach Escape Networks | graph theory, minimum diameter spanning tree. |
|
| 10806 | Dijkstra, Dijkstra | graph theory, min-cost max-flow, k shortest paths (k=2, edge disjoint). |
|
| 10807 | Prim, Prim | graph theory, MST, Kruskal's algorithm, backtracking, data structures, union-find. |
|
| 10810 | Ultra Quicksort | sorting, counting inversions, merge sort. |
|
| 10812 | Beat the Spread | ad hoc. |
|
| 10814 | Simplifying Fractions | simple math, gcd, bignum. |
|
| 10815 | Andy's First Dictionary | ad hoc, sorting, string manipulation. |
|
| 10816 | Travel in the Desert | graph theory, MST, shortest paths, SSSP, Dijkstra. |
|
| 10817 | Headmaster's Headache | DP. |
|
| 10819 | Trouble of 13-Dots | DP, 0/1 knapsack (a bit modified). |
|
| 10820 | Send A Table | number theory, Euler phi/totient, recurrences, sieve. |
|
| 10826 | Hot or Cold? | DP, math, number guessing game, hotter colder. |
|
| 10827 | Maximum Sum on a Torus | maximum sum in 2D (see UVA 108), DP. |
|
| 10828 | Back to Kernighan and Ritchie | systems of linear equations, Gaussian elimination, graph theory, graph traversal, reachability. |
|
| 10830 | A New Function | number theory, summations, floors. |
|
| 10831 | Gerg's Cake | number theory, quadratic residues, Legendre Symbol. |
|
| 10842 | Traffic Flow | graph theory, MST. |
|
| 10852 | Less Prime | number theory, primes, modulo. |
|
| 10862 | Connect the Cable Wires | bignum, recurrences, number theory, Fibonacci numbers. |
|
| 10864 | The Predator | computational geometry, rectangles, planar point location, coordinate compression, graph theory, DFS. |
|
| 10878 | Decode the Tape | ad hoc, string manipulation, maps. |
|
| 10879 | Code Refactoring | math, factoring, trial division. |
|
| 10881 | Piotr's Ants | ad hoc, sorting. |
|
| 10883 | Supermean | math, binomial coefficients. |
|
| 10887 | Concatenation of Languages | hashing, hashtable. |
|
| 10891 | Game of Sum | DP, memoization, games. |
|
| 10892 | LCM Cardinality | number theory, gcd, lcm. |
|
| 10897 | Travelling Distance | geometry, great circle distances. |
|
| 10900 | So you want to be a 2n-aire? | math, probability theory (continuous), expectation, integration. |
|
| 10901 | Ferry Loading III | ad hoc, simulation. |
|
| 10902 | Pick-up sticks | computational geometry, line segment intersection. |
|
| 10903 | Rock-Paper-Scissors Tournament | ad hoc |
|
| 10905 | A Children's Game | ad hoc, sorting |
|
| 10908 | Largest Square | ad hoc. |
|
| 10909 | Lucky Numbers | data structures, BST, find element at given rank in a BST, splay tree, linear searching. |
|
| 10910 | Mark's Distribution | DP, recurrences. |
|
| 10911 | Forming Quiz Teams | DP, brute force, memoization (or graph theory, minimum weight maximal matching in general graphs). |
|
| 10912 | Simple Minded Hashing | DP. |
|
| 10913 | Walking on a Grid | DP, memoization. |
|
| 10915 | War on Weather | geometry, angles, cosine relation. |
|
| 10916 | Factstone Benchmark | ad hoc, math, logarithms. |
|
| 10917 | Walk Through the Forest | graph theory, shortest paths, SSSP, Dijkstra, DAG, counting paths in a DAG, DP. |
|
| 10918 | Tri Tiling | combinatorics, recurrences, DP. |
|
| 10919 | Preqrequisites | ad hoc. |
|
| 10920 | Spiral Tap | ad hoc, coordinate systems, simple math, (or fast simulation), (see UVA 903). |
|
| 10921 | Find the Telephone | ad hoc. |
|
| 10922 | 2 the 9s | ad hoc, number theory. |
|
| 10924 | Prime Words | number theory, sieve, primes. |
|
| 10925 | Krakovia | bignum. |
|
| 10926 | How Many Dependencies? | graph theory, DFS, DAG. |
|
| 10927 | Bright Lights | computational geometry, gradients, sorting, distances. |
|
| 10929 | You can say 11 | number theory, modular arithmetic. |
|
| 10931 | Parity | ad hoc, number base conversion. |
|
| 10935 | Throwing cards away I | ad hoc, simulation, queue. |
|
| 10938 | Flea Circus | data structures, trees, tree traversal, lowest common ancestor (LCA) queries. |
|
| 10940 | Throwing Cards Away II | recurrences, math. |
|
| 10943 | How do you add? | DP. |
|
| 10945 | Mother Bear | ad hoc, palindromes. |
|
| 10946 | You want what filled? | graph theory, flood fill, DFS (or BFS), sorting. |
|
| 10948 | The Primary Problem | number theory, primes, sieve. |
|
| 10949 | Kids in a Grid | LCS, string algorithms, Hunt-Szymanski algorithm (optimized version), (or some other fast LCS algorithm). |
|
| 10951 | Polynomial GCD | polynomials, long division, gcd, math. |
|
| 10953 | Stochastic Digit Generator | DP, math, modulo. |
|
| 10954 | Add All | greedy. |
|
| 10963 | The Swallowing Ground | ad hoc. |
|
| 10964 | Strange Planet | ad hoc, math, modulo. |
|
| 10970 | Big Chocolate | ad hoc, DP, memoization, recursion. |
|
| 10976 | Fractions Again | brute force, math. |
|
| 10977 | Enchanted Forest | graph theory, BFS, shortest paths, SSSP. |
|
| 10982 | Troublemakers | graph theory, max cut, NP-complete, approximation algorithms, randomized algorithm, (or deterministic, greedy). |
|
| 10983 | Buy one, get the rest free | graph theory, max-flow, binary search. |
|
| 10986 | Sending email | graph theory, shortest paths, Dijkstra, SSSP. |
|
| 10987 | AntiFloyd | graph theory, all-pairs shortest paths (in reverse), Floyd-Warshall. |
|
| 10989 | Bomb, Divide and Conquer | graph theory, min-cut (not s-t min-cut), Stoer-Wagner. |
|
| 10990 | Another New Function | number theory, primes, Euler totient, sieve (modified), prefix sums. |
|
| 10991 | Region | geometry, cosine relation, triangle area, area of circle sector, Heron's formula. |
|
| 10992 | The Ghost of Programmers | ad hoc, math, modulo (bignum). |
|
| 10993 | Ignoring Digits | graph theory, BFS. |
|
| 10994 | Simple Addition | recurrences, math, sums. |
|
| 11000 | Bee | number theory, recurrences, Fibonacci numbers. |
|
| 11001 | Necklace | ad hoc, brute force, maximization of a function. |
|
| 11002 | Towards Zero | graph theory, DFS, DP, memoization. |
|
| 11003 | Boxes | DP, LIS. |
|
| 11005 | Cheapest Base | number theory, base conversion, ad hoc. |
|
| 11008 | Antimatter Ray Clearcutting | DP, geometry, lines, collinearity. |
|
| 11012 | Cosmic Cabbages | math, case analysis, manhattan distance. |
|
| 11015 | 05-2 Rendezvous | graph theory, APSP, all-pairs shortests paths, Floyd-Warshall. |
|
| 11022 | String Factoring | DP, strings, border array, minimal period. |
|
| 11026 | A Grouping Problem | DP, math, elementary symmetric polynomials. |
|
| 11027 | Palindromic Permutation | math, multinomial coefficients. |
|
| 11028 | Sum of Product | math, precalculation, the dartboard sequence, permutations. |
|
| 11029 | Leading and Trailing | math, modulo, repeated squaring. |
|
| 11030 | Predator II | computational geometry, point in simple polygon. |
|
| 11032 | Function Overloading | ad hoc, binary search. |
|
| 11040 | Add Bricks in the Wall | ad hoc. |
|
| 11044 | Searching For Nessy | ad hoc, simple math. |
|
| 11045 | My T-Shirt Suits Me | graph theory, max-flow (or maximum cardinality bipartite matching). |
|
| 11048 | Automatic Correction of Misspellings | ad hoc, strings, string matching. |
|
| 11049 | Basic Wall Maze | graph theory, shortest paths, BFS. |
|
| 11051 | Dihedral Groups | ad hoc. |
|
| 11052 | Economic Phone Calls | DP, (or greedy). |
|
| 11053 | Flavius Josephus Reloaded | cycle finding (Floyd's Cycle Finding Algorithm). |
|
| 11054 | Wine Trading in Gergovia | ad hoc, greedy. |
|
| 11055 | Homogeneous Squares | ad hoc, math. |
|
| 11057 | Exact Sum | ad hoc. |
|
| 11059 | Maximum Product | ad hoc, brute force. |
|
| 11063 | B2 Sequence | ad hoc. |
|
| 11064 | Number Theory | math, number theory, totient, divisors, primes, (see also UVA 10299). |
|
| 11069 | A Graph Problem | combinatorics, recurrences. |
|
| 11079 | What's the Time? | math, lcm, periodicity, simulation, fast simulation. |
|
| 11081 | Strings | DP. |
|
| 11082 | Matrix Decompressing | graph theory, max-flow. |
|
| 11087 | Divisibility Testing | DP, math, modulo. |
|
| 11090 | Going in Cycle!! | graph theory, minimum mean-weight cycle, Karp's minimum mean-weight cycle algorithm, (or shortest paths, Bellman-Ford). |
|
| 11100 | The Trip 2007 | ad hoc, greedy, sorting, queue. |
|
| 11101 | Mall Mania | graph theory, BFS, flood fill. |
|
| 11103 | WFF 'N PROOF | binary trees, internal nodes, leaves. |
|
| 11105 | Semi-prime H-numbers | number theory, sieve, prefix sums. |
|
| 11107 | Life Forms | suffix array, strings. |
|
| 11108 | Tautology | brute force, parsing, abstract evaluation, NP-complete. |
|
| 11109 | Rinse | math, maximising a product. |
|
| 11110 | Equidivisions | graph theory, flood fill, DFS. |
|
| 11111 | Generalized Matrioshkas | ad hoc, stack. |
|
| 11115 | Uncle Jack | bignum. |
|
| 11118 | Prisoners Boxes and Pieces of Paper | probability theory, permutations, cycles. |
|
| 11121 | Base -2 | math, number base conversion, negative bases. |
|
| 11122 | Tri Tri | computational geometry, 2D triangle-triangle intersection. |
|
| 11125 | Arrange Some Marbles | DP. |
|
| 11126 | Relaxed Golf | DP. |
|
| 11127 | Triple-Free Binary Strings | backtracking. |
|
| 11129 | An Antiarithmetic Permutation | divide and conquer, math. |
|
| 11133 | Eigensequences | DP, math. |
|
| 11137 | Ingenuous Cubrency | DP, subset sum, coin change. |
|
| 11138 | Nuts 'n' Bolts | graph theory, maximum cardinality bipartite matching. |
|
| 11149 | Power of Matrix | matrices, matrix multiplication, repeated squaring (of matrices), DP. |
|
| 11150 | Cola | ad hoc. |
|
| 11151 | Longest Palindrome | DP, strings. |
|
| 11152 | Colourful Flowers | geometry, circles, Heron's formula, incircle, circumcircle, |
|
| 11153 | Museums | DP, TSP, bitmasks, graph theory, APSP, all-pairs shortest paths, Floyd-Warshall. |
|
| 11155 | Be Efficient | ad hoc, number theory. |
|
| 11156 | Continuous Drawing | computational geometry, line segments, lattice points, gcd, graph theory, Chinese postman problem, all-pairs shortest paths, Floyd-Warshall, minimum cost maximum matchings in general graphs, DP. |
|
| 11157 | Dynamic Frog | greedy, sorting. |
|
| 11158 | Elegant Permuted Sum | greedy, sorting, simple math, (or DP). |
|
| 11159 | Factors and Multiples | graph theory, maximum cardinality bipartite matching, maximum independent set in a bipartite graph, simple math, divisibility. |
|
| 11161 | Help My Brother | bignum, Fibonacci Numbers. |
|
| 11162 | Independent Attacking Zones | DP, simple math, triangles, circles. |
|
| 11167 | Monkeys in the Emei Mountain | graph theory, max-flow. |
|
| 11170 | Cos(NA) | De Moivre's formula, Chebyshev polynomials, math. |
|
| 11171 | SMS | DP, printing the solution, strings, trie. |
|
| 11172 | Relational Operators | ad hoc. |
|
| 11174 | Stand in a Line | number of topological sorts of a forest, linear extensions, graph theory, math, factorials, binomial coefficients, modular inverses (modulo a prime). |
|
| 11176 | Winning Streak | DP, math, probability theory. |
|
| 11180 | Base i-1 | math, complex numbers, division, complex bases, number base conversion. |
|
| 11183 | Teen Girl Squad | graph theory, directed minimum spanning tree, minimum cost arborescence, Chu-Liu-Edmonds algorithm. |
|
| 11185 | Ternary | ad hoc, number base conversion. |
|
| 11191 | Perfect Square | number theory, primes, square numbers, math. |
|
| 11192 | Group Reverse | ad hoc. |
|
| 11200 | Sapitaur's Labyrinth | graph theory, reachability, flood-fill, BFS, mazes. |
|
| 11201 | The Problem with the Crazy Linguist | backtracking, brute force, ad hoc. |
|
| 11202 | The Least Possible Effort | graph theory, Knight's tour, math, counting symmetries, rotations, flips. |
|
| 11203 | Can You Decide it for ME? | ad hoc. |
|
| 11204 | Musical Instruments | ad hoc. |
|
| 11205 | The Broken Pedometer | bit masks, brute force. |
|
| 11207 | The Easiest Way | ad hoc, simple math, geometry, squares. |
|
| 11218 | KTV | brute force, backtracking, ad hoc. |
|
| 11219 | How old are you? | ad hoc. |
|
| 11220 | Decoding the Message | ad hoc. |
|
| 11221 | Magic Square Palindromes | ad hoc. |
|
| 11222 | Only I did it! | ad hoc. |
|
| 11223 | dah, dah, dah! | ad hoc. |
|
| 11224 | Let's Swim | ad hoc, sorting. |
|
| 11225 | Tarot Scores | ad hoc. |
|
| 11226 | Reaching the fix-point | number theory, sieve (modified). |
|
| 11227 | The Silver Bullet | ad hoc, geometry, straight lines, gradients, slopes. |
|
| 11228 | Transportation System | graph theory, MST. |
|
| 11230 | Annoying Painting Tool | greedy, simulation. |
|
| 11231 | Black and white painting | ad hoc, counting, sums, floor, ceiling. |
|
| 11232 | Cylinder | geometry, math, cylinders, volume of a cylinder. |
|
| 11233 | Deli Deli | ad hoc, string manipulation. |
|
| 11234 | Expressions | trees, postorder, level order, queues, stacks. |
|
| 11235 | Frequent Values | data structures, Range Maximum Query, computational geometry, 1D range searching (augmented to get Range Max Query). |
|
| 11236 | Grocery Store | ad hoc, brute force, pruning, no input. |
|
| 11237 | Halloween Treats | number theory, pigeonhole principle, modulo. |
|
| 11238 | Innumerous Bowling Games | DP, memoization. |
|
| 11239 | Open Source | ad hoc, sorting, sets. |
|
| 11240 | Antimonotonicity | greedy, number of runs in a sequence (or DP). |
|
| 11241 | Humidex | ad hoc. |
|
| 11242 | Tour De France | ad hoc, sorting. |
|
| 11243 | Texas Trip | computational geometry, smallest enclosing square, ternary search, rotations, rotation matrices. |
|
| 11244 | Counting Stars | ad hoc. |
|
| 11245 | Anti-Arithmetic Sequence | math, number theory, modulo, primes, number base conversion. |
|
| 11246 | K-Multiple Free Set | greedy, ad hoc. |
|
| 11247 | Income Tax Hazard | ad hoc. |
|
| 11254 | Consecutive Integers | number theory, divisors, Gauss sum, brute force. |
|
| 11255 | Necklace | math, Burnside's lemma, orbits, abstract algebra, group theory, combinatorics, necklaces, rotations, gcd, binomial coefficients. |
|
| 11256 | Repetitive Multiple | math, number theory, gcd, lcm. |
|
| 11258 | String Partition | DP. |
|
| 11259 | Coin Changing Again | DP, inclusion-exclusion principle (for queries). |
|
| 11260 | Odd Root Sum | math, summations. |
|
| 11261 | Bishops | ad hoc, games, chess, chess board, bishops, counting number of threathened squares, diagonals. |
|
| 11262 | Weird Fence | graph theory, maximum cardinality bipartite matching, binary search. |
|
| 11264 | Coin Collector | greedy. |
|
| 11269 | Setting Problems | greedy, sorting, scheduling algorithms. |
|
| 11270 | Tiling Dominoes | combinatorics, advanced math (google!). |
|
| 11273 | Warping of N Dimensional Space | linear algebra, linear transformations, number theory, gcd, Euler phi, sieve. |
|
| 11275 | 3D Triangles | computational geometry, 3D triangle intersection. |
|
| 11277 | Cyclic Polygons | computational geometry, binary search, Heron's formula, triangulation, arc lengths. |
|
| 11278 | One-Handed Typist | ad hoc. |
|
| 11279 | Keyboard Comparison | ad hoc. |
|
| 11280 | Flying to Fredericton | graph theory, shortest paths, SSSP, Bellman-Ford. |
|
| 11281 | Triangular Pegs in Round Holes | geometry, minimal bounding circle for triangles, circumcircle, obtuse angles. |
|
| 11282 | Mixing Invitations | combinatorics, binomial coefficients, derangements. |
|
| 11283 | Playing Boggle | graph theory, DFS. |
|
| 11284 | Shopping Trip | graph theory, DP, TSP, Floyd-Warshall, all-pairs shortest paths, APSP, memoization. |
|
| 11285 | Exchange Rates | DP. |
|
| 11286 | Conformity | ad hoc. |
|
| 11287 | Pseudoprime Numbers | number theory, primality testing, trial division, repeated squaring. |
|
| 11291 | Smeech | ad hoc, parsing, stacks. |
|
| 11292 | Dragon of Loowater | ad hoc, greedy. |
|
| 11294 | Wedding | 2-SAT. |
|
| 11296 | Counting Solutions of an Integer Equation | ad hoc, math, floors. |
|
| 11297 | Census | data structures, four-sided range queries, 2D range minimum/maximum queries, 2D segment tree (2D interval tree, range tree or similar), geometric data structures, augmenting data structures. |
|
| 11301 | Great Wall of China | graph theory, min-cost max-flow. |
|
| 11307 | Alternative Arborecsence | graph theory, trees, DP. |
|
| 11308 | Bankrupt Banker | ad hoc. |
|
| 11309 | Counting Chaos | ad hoc. |
|
| 11310 | Delivery Debacle | math, recurrences. |
|
| 11311 | Exclusively Edible | DP. |
|
| 11312 | Flipping Frustation | number theory, extended GCD. |
|
| 11313 | Gourmet Games | ad hoc. |
|
| 11314 | Hardly Hard | geometry, calculus of several variables, partial derivatives, minimization. |
|
| 11319 | Stupid Sequence | polynomial interpolation, Gaussian elimination, systems of linear equations. |
|
| 11321 | Sort! Sort!! and Sort! | ad hoc, sorting. |
|
| 11323 | Satisfying Constraints | graph theory, DFS, math. |
|
| 11324 | The Largest Clique | graph theory, strongly connected components, DP, DAG, longest path. |
|
| 11325 | This Means War | backtracking, brute force, greedy. |
|
| 11326 | Laser Pointer | geometry, trigonometry. |
|
| 11327 | Enumerating Rational Numbers | number theory, gcd, Euler totient, sieve. |
|
| 11329 | Curious Fleas | graph theory, shortest paths, BFS, bitmasks. |
|
| 11330 | Andy's Shoes | permutations, cycles, puzzles, greedy. |
|
| 11331 | The Joys of Farming | graph theory, 2-coloring, DFS, subset sum, knapsack, DP. |
|
| 11332 | Summing Digits | ad hoc. |
|
| 11335 | Discrete Pursuit | math, gauss sum. |
|
| 11336 | DRM | graph theory, graph traversal, DFS. |
|
| 11338 | Minefield | geometry, sorting, graph theory, shortest paths, Dijkstra. |
|
| 11340 | Newspaper | ad hoc. |
|
| 11341 | Term Strategy | DP. |
|
| 11342 | Three-Square | ad hoc, brute force. |
|
| 11343 | Isolated Segments | computational geometry, line segment intersection. |
|
| 11344 | The Huge One | ad hoc, number theory, modulo. |
|
| 11345 | Rectangles | geometry, ad hoc. |
|
| 11346 | Probability | math, probability theory, integration, continuous probability distribution. |
|
| 11347 | Multifactorials | number theory, primes, prime factorization. |
|
| 11348 | Exhibition | ad hoc. |
|
| 11349 | Symmetric Matrix | ad hoc. |
|
| 11350 | Stern-Brocot Tree | ad hoc, number theory. |
|
| 11351 | Last Man Standing | Josephus problem. |
|
| 11352 | Crazy King | graph theory, BFS. |
|
| 11353 | A Different Kind of Sorting | number theory, sieve, primes, sorting. |
|
| 11354 | Bond | data structures, graph theory, bottleneck edge queries in a static graph, minimum spanning tree, Kruskal's algorithm, union-find tree (using only union by rank or union by size), lowest common ancestor (LCA). |
|
| 11355 | Cool Points | computational geometry, sweeping, sorting by polar angle. |
|
| 11356 | Dates | ad hoc. |
|
| 11357 | Ensuring Truth | ad hoc. |
|
| 11358 | Faster Processing Facility | graph theory, max-flow (like UVA 11167). |
|
| 11359 | Guards, Imbecile Guards | graph theory, BFS, cycle finding. |
|
| 11360 | Have Fun With Matrices | ad hoc, simulation. |
|
| 11361 | Investigating Div-Sum Property | DP, number theory, modulo. |
|
| 11362 | Phone List | strings, sorting. |
|
| 11363 | Cuckoo Hashing | ad hoc, cycle finding, cuckoo hashing. |
|
| 11364 | Optimal Parking | ad hoc. |
|
| 11365 | Copying DNA | graph theory, BFS, bitmasks, precalculation (optimization). |
|
| 11367 | Full Tank | graph theory, shortest paths, SSSP, Dijkstra (with a heap). |
|
| 11368 | Nested Dolls | greedy, sorting, (or Dilworth's theorem, LIS in O(nlogn), DP). |
|
| 11369 | Shopaholic | greedy, sorting. |
|
| 11370 | Moogle | DP. |
|
| 11371 | Number Theory for Newbies | ad hoc. |
|
| 11372 | Arranging a Contest | DP. |
|
| 11373 | Happy Birthday | geometry, angles, sorting, circle sector area, triangle area, line-circle intersection, line-line intersection. |
|
| 11374 | Airport Express | graph theory, shortest paths, SSSP, Dijkstra. |
|
| 11375 | Matches | DP, bignum. |
|
| 11377 | Airport Setup | graph theory, shortest paths, BFS. |
|
| 11378 | Bey Battle | computational geometry, closest pair of points (using a different distance function), sorting. |
|
| 11380 | Down Went the Titanic | graph theory, max-flow. |
|
| 11381 | Elegant Strings | graph theory, minimum cost weighted bipartite matching (min-cost max-flow). |
|
| 11383 | Golden Tiger Claw | Kuhn-Munkres (Hungarian) algorithm (byproduct of this algorithm), weighted maximum cardinality bipartite matching. |
|
| 11384 | Help is needed for Dexter | ad hoc, math, recurrences. |
|
| 11385 | Da Vinci Code | ad hoc, simulation |
|
| 11386 | Triples | ad hoc, sorting, hashing. |
|
| 11387 | The 3-Regular Graph | graph theory, ad hoc. |
|
| 11388 | GCD LCM | number theory, gcd, lcm. |
|
| 11389 | The Bus Driver Problem | ad hoc, sorting. |
|
| 11390 | The Sultan's Feast | backtracking, (graph theory, strongly connected components). |
|
| 11391 | Blobs in the Board | DP. |
|
| 11392 | Binary*3 Type Multiple | math, number theory, modulo. |
|
| 11393 | Tri-Isomorpishm | graph theory, ad hoc. |
|
| 11394 | Digit Blocks | DP. |
|
| 11395 | Sigma Function | number theory. |
|
| 11396 | Claw Decomposition | graph theory, claws, testing if a graph is bipartite, DFS. |
|
| 11398 | The Base-1 Number System | ad hoc. |
|
| 11400 | Lighting System Design | DP. |
|
| 11401 | Triangle Counting | geometry, triangles, math. |
|
| 11402 | Ahoy, Pirates! | data structures. |
|
| 11403 | Binary Multiplication | ad hoc. |
|
| 11404 | Palindromic Subsequence | DP, strings, printing the solution, lexicographically smallest solution. |
|
| 11405 | Can U Win? | graph theory, BFS, TSP. |
|
| 11407 | Squares | ad hoc, brute force, math. |
|
| 11408 | Count DePrimes | number theory, sieve, math, prefix sums. |
|
| 11410 | LAEncoding | ad hoc, simple math, number base conversion. |
|
| 11411 | MiniMice | number theory, sieve, primes, number of divisors, sorting, greedy. |
|
| 11412 | Dig the Holes | ad hoc, brute force. |
|
| 11413 | Fill The Containers | binary search, greedy. |
|
| 11414 | Dream | graph theory, graphic sequence, Erdos-Gallai condition, (or greedy, Havel-Hakimi). |
|
| 11415 | Count The Factorials | number theory, sieve, primes, factorials, binary search. |
|
| 11417 | GCD | number theory, summations, gcd. |
|
| 11418 | Clever Naming Patterns | graph theory, maximum cardinality bipartite matching. |
|
| 11419 | SAM I AM | graph theory, minimum vertex cover in a bipartite graph, maximum-cardinality bipartite matching, König's theorem. |
|
| 11420 | Chest of Drawers | DP. |
|
| 11421 | Arranging Cards | DP. |
|
| 11423 | Cache Simulator | data structures, binary indexed tree, Fenwick tree. |
|
| 11424 | GCD Extreme I | number theory, Euler totient, sieve, summations, gcd. |
|
| 11426 | GCD Extreme II | number theory, Euler totient, sieve, summations, gcd. |
|
| 11427 | Expect the Expected | DP, math, probability theory. |
|
| 11428 | Cubes | number theory, math, brute force. |
|
| 11430 | ETS Problem Setting | math, binomial coefficents. |
|
| 11432 | Busy Programmer | DP. |
|
| 11436 | Cubes - Extreme | number theory, math, divisors, quadratic equations. |
|
| 11437 | Triangle Fun | geometry, triangles. |
|
| 11438 | Integer Transmission | DP, bignum. |
|
| 11439 | Maximizing the ICPC | graph theory, maximum cardinality matching in general graphs (nonbipartite), Edmond's Blossom Algorithm, binary search. |
|
| 11440 | Help Mr. Tomisu | number theory, math, primes, sieve, Euler totient, modular inverses. |
|
| 11441 | Encoding/Decoding | DP. |
|
| 11444 | Sum | math, summations, interchanging the order of summation, binomial theorem. |
|
| 11446 | Where's The Back Button? | graph theory, cycles, (see TopCoder SRM 184 Div 1 1000, editorial). |
|
| 11447 | Reservoir Logs | computational geometry, area of 2D polygon. |
|
| 11448 | Who Said Crisis? | bignum, subtraction. |
|
| 11450 | Wedding Shopping | DP. |
|
| 11452 | Dancing the Cheeky Cheeky | ad hoc, strings, string period. |
|
| 11455 | Behold My Quadrange | ad hoc, geometry. |
|
| 11456 | Trainsorting | LIS (longest increasing subsequence), LDS (longest decreasing subsequence), combination of a LIS and LDS. |
|
| 11457 | Classified | graph theory, finding LCA in a DAG, queries, data structures, lattices, cryptography, Dynamic Biba integrity model. |
|
| 11461 | Square Numbers | ad hoc, simple math. |
|
| 11462 | Age Sort | sorting. |
|
| 11463 | Commandos | graph theory, shortest paths, BFS. |
|
| 11464 | Even Parity | ad hoc, brute force (on the first row). |
|
| 11465 | Count the Polygons | splitting set in two, generating subsets, binary search, math (geometry, polygons), (or backtracking, pruning). |
|
| 11466 | Largest Prime Divisor | number theory, math, primes, sieve, divisors, trial division. |
|
| 11470 | Square Sums | ad hoc. |
|
| 11471 | Arrange the Tiles | DP. |
|
| 11472 | Beautiful Numbers | DP. |
|
| 11473 | Campus Roads | computational geometry, perimeter of polygon, simple math, vectors. |
|
| 11474 | Dying Tree | ad hoc, graph theory, DFS (or union-find). |
|
| 11475 | Extend to Palindromes | hashing, strings, palindromes (or Knuth-Morris-Pratt, KMP algorithm). |
|
| 11478 | Halum | graph theory, minimum mean-weight cycle, Karp's minimum mean-weight cycle algorithm. |
|
| 11479 | Is this the easiest problem? | geometry, triangles, simple math. |
|
| 11480 | Jimmy's Balls | ad hoc, math. |
|
| 11481 | Arrange the Numbers | math, binomial coefficients, DP, recurrences, derangements. |
|
| 11482 | Building a Triangular Museum | ad hoc, simulation. |
|
| 11483 | Code Creator | ad hoc. |
|
| 11485 | Extreme Discrete Simulation | DP. |
|
| 11489 | Integer Game | ad hoc, simple math, modular arithmetic. |
|
| 11491 | Erasing and Winning | greedy. |
|
| 11492 | Babel | graph theory, shortest paths, SSSP, Dijkstra. |
|
| 11493 | The Club Ballroom | ad hoc, greedy, simple math. |
|
| 11494 | Queen | ad hoc. |
|
| 11495 | Bubbles and Buckets | sorting, counting inversions, merge sort. |
|
| 11496 | Musical Loop | ad hoc. |
|
| 11497 | Set | ad hoc. |
|
| 11498 | Division of Nlogonia | ad hoc. |
|
| 11499 | Longest Increasing Subsequence | ad hoc. |
|
| 11500 | Vampires | math, probability theory, (or DP). |
|
| 11502 | Rocket Stages | DP, simple physics, math, calculus, integration. |
|
| 11503 | Virtual Friends | graph theory, connected components, data structures, union-find. |
|
| 11504 | Dominos | graph theory, strongly connected components, DAG. |
|
| 11505 | Logo | ad hoc, simulation, simple math, cosine, sine. |
|
| 11506 | Angry Programmer | graph theory, max-flow, max-flow min-cut theorem, vertex capacities. |
|
| 11507 | Bender B. Rodriguez Problem | ad hoc, simulation, permutations, geometry. |
|
| 11508 | Life on Mars | ad hoc. |
|
| 11511 | Frieze Patterns | ad hoc, cycle finding. |
|
| 11512 | GATTACA | strings, repetitions, substrings, hashing, (or suffix arrays, LCP). |
|
| 11513 | 9 Puzzle | graph theory, shortest paths, BFS (from the goal state), printing the path. |
|
| 11514 | Batman | DP. |
|
| 11515 | Cranes | DP (or brute force), circle-circle intersection, circle area. |
|
| 11516 | WiFi | binary search, greedy, interval covering. |
|
| 11517 | Exact Change | DP, coin change. |
|
| 11518 | Dominos 2 | graph theory, graph traversal, DFS. |
|
| 11519 | Logo 2 | ad hoc, simulation, simple math, cosine, sine. |
|
| 11520 | Fill the Square | greedy. |
|
| 11522 | Pyramid Number | math, Egyptian fractions, Egyptian number, strictly Egyptian number (A051882 on OEIS). |
|
| 11523 | Recycling | DP (see Topcoder SRM 240 Div 1 900). |
|
| 11524 | In-Circle | geometry, math, binary search, circles, in-circle, triangles, triangle area, Heron's formula. |
|
| 11525 | Permutation | math, permutations, factoradics, factorial number system, data structures, finding an element at a given rank, BST, binary search trees. |
|
| 11526 | H(n) | simple math, floors, sums, square root. |
|
| 11530 | SMS Typing | ad hoc, simulation. |
|
| 11532 | Simple Adjacency Maximization | DP, (or greedy). |
|
| 11534 | Say Goodbye to Tic-Tac-Toe | combinatorial game theory, composite games, Sprague-Grundy theorem, grundy numbers, impartial games, nim. |
|
| 11535 | Set of Marbles | gray code, reflected binary code, binary numeral system. |
|
| 11536 | Smallest Sub-Array | ad hoc, binary search, data structures, arrays. |
|
| 11537 | Secret Problemsetter's Union | ad hoc, simulation, data structures, arrays. |
|
| 11538 | Chess Queen | math, summations, closed form, number of non-attacking position of two queens on a m x n chessboard. |
|
| 11539 | Another Word Game | DP, strings, hashing. |
|
| 11540 | Sultan's Chandelier | math, Burnside's lemma, orbits, abstract algebra, group theory, combinatorics, rotations, gcd, primes, inverses, DP, graph theory, trees, tree isomorphism. |
|
| 11541 | Decoding | ad hoc, strings, run-length encoding. |
|
| 11542 | Square | math, linear algebra, subspaces, dimension, gaussian elimination over the field F_2, rank of a matrix, primes, sieve. |
|
| 11544 | Recruiter's Problem | graph theory, max-flow, reusing the flow, searching, (or min-cost max-flow, Bignum). |
|
| 11545 | Avoiding Jungle in the Dark | graph theory, shortest paths, BFS. |
|
| 11547 | Automatic Answer | ad hoc, simulation, simple math. |
|
| 11548 | Blackboard Bonanza | ad hoc, brute force, strings. |
|
| 11549 | Calculator Conundrum | ad hoc, simple math, cycle finding (Floyd's cycle finding algorithm). |
|
| 11550 | Demanding Dilemma | graph theory, incidence matrix, verifying correctness of an incidence matrix, detecting multiple edges between vertices. |
|
| 11551 | Experienced Endeavour | linear algebra, linear transformations, matrices, matrix multiplication, repeated squaring (of matrices), modular arithmetic. |
|
| 11552 | Fewest Flops | DP, strings. |
|
| 11553 | Grid Game | DP, bitmasks. |
|
| 11554 | Hapless Hedonism | math, recurrences, number of triangles possible using sticks of length 1,2,...,n. |
|
| 11555 | Aspen Avenue | DP, sorting, greedy. |
|
| 11556 | Best Compression Ever | ad hoc, simple math. |
|
| 11557 | Code Theft | strings, longest common substring, hashing, rolling hash, (or suffix tree). |
|
| 11558 | Dinner | graph theory, branch and bound, backtracking, brute force. |
|
| 11559 | Event Planning | ad hoc. |
|
| 11560 | Fixing the Bugs | DP, greedy, math, probability theory, expectation. |
|
| 11561 | Getting Gold | graph theory, graph traversal, DFS. |
|
| 11562 | Hard Evidence | computational geometry, maximal viewing angle of a convex polygon from a circle, sweepline on a circle, math, trigonometry, angles, ternary search. |
|
| 11563 | Introspective Caching | greedy, caching, optimal caching strategy, data structures, priority queue, BST. |
|
| 11564 | Just A Few More Triangles | number of Pythagorean triples mod n, modular arithmetic, Fast Fourier Transform (FFT) (will get TLE), multiplicative function, number theory, prime factorization, OEIS (A062775). |
|
| 11565 | Simple Equations | ad hoc, simple math, divisors. |
|
| 11567 | Moliu Number Generator | ad hoc, brute force, recursion. |
|
| 11569 | Lovely Hint | DP. |
|
| 11572 | Unique Snowflakes | ad hoc, longest substring with no duplicate characters, (or divide and conquer, coordinate compression). |
|
| 11573 | Ocean Currents | graph theory, shortest paths, BFS (0/1 weights), deque. |
|
| 11574 | Colliding Traffic | ad hoc, simple math, quadratic equations, angles, trigonometry. |
|
| 11576 | Scrolling Sign | ad hoc, string manipulation, prefix, suffix. |
|
| 11577 | Letter Frequency | ad hoc. |
|
| 11578 | Situp Benches | DP, printing the solution. |
|
| 11579 | Triangle Trouble | geometry, math, triangle area, Heron's formula, equilateral triangles, sorting. |
|
| 11581 | Grid Successors | ad hoc, cycle detection. |
|
| 11582 | Colossal Fibonacci Numbers! | math, Fibonacci numbers, cycle detection, Pisano period, repeated squaring. |
|
| 11583 | Alien DNA | greedy, string manipulation, set intersection. |
|
| 11584 | Partitioning By Palindromes | DP. |
|
| 11585 | Nurikabe | ad hoc, simulation, games, nurikabe, solution verification, graph theory, DFS, flood fill. |
|
| 11586 | Train Tracks | DP. |
|
| 11587 | Brick Game | DP, games, winning/losition positions, reduction to SAT, backtracking. |
|
| 11588 | Image Coding | ad hoc. |
|
| 11590 | Prefix Lookup | strings, trie, DP. |
|
| 11594 | All Pairs Maximum Flow | graph theory, maximum flow, all-pairs maximum flow, max-flow min-cut theorem, Gomory-Hu tree of minimum cuts (cut trees). |
|
| 11596 | Convex Orthogonal Polygon | geometry, convex orthogonal polygons, bounding box, simple math, quadratic equations, divisors. |
|
| 11597 | Spanning Subtree | graph theory, maximum number of edge-disjoint spanning trees in a complete graph. |
|
| 11598 | Optimal Segments | DP, printing the solution, finding the lexicographically smallest solution. |
|
| 11600 | Masud Rana | graph theory, spanning trees, complete graph, random walks, math, probability theory, DP, keeping track of the connected components. |
|
| 11601 | Avoiding Overlaps | ad hoc, data structures, bitsets, geometry, rectangle-rectangle intersection, fast I/O. |
|
| 11602 | SMS for Blinds | backtracking, brute force, sorting, pruning. |
|
| 11603 | It's all about the Bandwidth | graph theory, maximum spanning tree, DFS, bottleneck edge queries, all-pairs maximum flow, max-flow min-cut theorem, Gomory-Hu tree of minimum cuts (cut trees). |
|
| 11604 | General Sultan | strings, prefix, graph theory, reachability, DFS. |
|
| 11605 | Lights inside a 3D Grid | math, probability theory, expected value, 0-1 indicator random variables, linear algebra, linear transformations, repeated squaring on a matrix, independence of dimensions, (or eigenvalues, eigenvectors, diagonalization, doubly stochastic matrix). |
|
| 11606 | Atoms | ad hoc, simulation, manhattan distance, BFS, games, checking if a game state is reachable. |
|
| 11608 | No Problem! | ad hoc, simulation. |
|
| 11609 | Teams | math, summations, binomial coefficients, repeated squaring. |
|
| 11610 | Reverse Prime | math, primes, sieve, data structures, binary indexed tree, Fenwick tree, dynamic cumulative sum, binary search. |
|
| 11611 | Colored Tiles | DP, bitmasks, tiling, grids. |
|
| 11612 | Sultan and Khairun Shundori | computational geometry, connecting a set of points with straight lines without crossings, collinearity, left/right turn, sorting by polar angle, sweepline on a circle. |
|
| 11613 | Acme Corporation | graph theory, max-cost flow, reduction to max-cost max-flow, (or discrete ternary search). |
|
| 11614 | Etruscan Warriors Never Play Chess | simple math, summations, sum of first n integers, quadratic equation. |
|
| 11615 | Family Tree | ad hoc, simple math, complete binary trees. |
|
| 11616 | Roman Numerals | ad hoc, conversion from roman numerals to decimal (and vice versa). |
|
| 11617 | An Odd Love | DP. |
|
| 11618 | The Amazing Triangle Counting Machine | graph theory, counting triangles. |
|
| 11619 | Spam! (or not) | simple math, probability theory, Bayesian spam filtering (see Wikipedia). |
|
| 11620 | City of Egocentrics | ad hoc, simple math, grids, prefix sums on rows, columns, and diagonals. |
|
| 11621 | Small Factors | ad hoc, brute force, simple math. |
|
| 11623 | Tic Tac Toe | ad hoc, N x N tic tac toe, board games, evaluating board positions. |
|
| 11624 | Fire! | graph theory, BFS, multiple sources, shortest paths. |
|
| 11625 | Nice Prefixes | strings, prefix, DP, linear algebra, linear transformations, repeated squaring on a matrix. |
|
| 11626 | Convex Hull | computational geometry, convex hull, sorting by polar angle. |
|
| 11627 | Slalom | sorting, binary search, simple math. |
|
| 11628 | Another Lottery | ad hoc, simple math, probability theory, fractions, gcd. |
|
| 11629 | Ballot Evaluation | ad hoc, simulation, simple math. |
|
| 11631 | Dark Roads | graph theory, MST. |
|
| 11632 | Elias Gamma Coding | DP, binary codes. |
|
| 11633 | Food Portion Size | ad hoc, brute force, simple math, fractions, gcd. |
|
| 11634 | Generate Random Numbers | ad hoc, simple math, cycle finding. |
|
| 11635 | Hotel Booking | graph theory, single source shortest paths, SSSP, Dijkstra (with a heap). |
|
| 11636 | Hello World | ad hoc, simple math, binary expansion, most significant bit. |
|
| 11637 | Garbage Remembering Exam | math, probability theory, expectation. |
|
| 11638 | Temperature Monitoring | ad hoc, simulation, bitmasks. |
|
| 11639 | Guard the Land | ad hoc, geometry, rectangle-rectangle intersection. |
|
| 11641 | Looking for a New Place | ad hoc, simple math, polyminoes, bounding box, geometry, brute force. |
|
| 11642 | Bangladesh Premier League | graph theory, max-flow, min-cut. |
|
| 11643 | Knight Tour | graph theory, BFS, shortest paths, TSP, DP, knight tour. |
|
| 11644 | Pyragrid | ad hoc, geometry, counting triangles, graph theory. |
|
| 11645 | Bits | ad hoc, simple math, recurrences, Bignum. |
|
| 11646 | Athletics Track | math, binary search, plane geometry, rectangle, circle, circular sector, chord. |
|
| 11647 | Judgment Day | graph theory, min-cost circulation, min-cost max-flow. |
|
| 11648 | Divide The Land | math, binary search, plane geometry, area of trapezium, median of trapezoid. |
|
| 11649 | Home! Sweet Home! | sorting, greedy, partial orders, data structures, BST. |
|
| 11650 | Mirror Clock | ad hoc, simple math, analogue clock, reflection. |
|
| 11651 | Krypton Number System | math, number bases, graph theory, number of paths of a fixed length, linear algebra, matrix multiplication, repeated squaring. |
|
| 11653 | Stick Makes Gold | sweepline in 1D, sorting, math, sums, Gauss sum, sum of squares, sum of cubes. |
|
| 11654 | Arithmetic Subsequence | DP, number of subsequences that are arithmetic progressions. |
|
| 11655 | Water Land | graph theory, DAG, DP, number of paths from s to t, DFS, reachability. |
|
| 11658 | Best Coalitions | DP, subset sum. |
|
| 11659 | Informants | backtracking. |
|
| 11660 | Look-and-Say sequences | ad hoc, brute force, string manipulation, math, look-and-say sequence. |
|
| 11661 | Burger Time? | ad hoc, simulation. |
|
| 11664 | Langton's Ant | ad hoc, simulation, bignum, number base conversion, cellular automata, Langton's ant, 2D Turing Machine. |
|
| 11665 | Chinese Ink | computational geometry, simple polygons, polygon intersection, graph theory, DFS, connected components. |
|
| 11666 | Logarithms | simple math, logarithms, brute force. |
|
| 11677 | Alarm Clock | ad hoc, simulation. |
|
| 11678 | Cards' Exchange | ad hoc, set intersection. |
|
| 11679 | Sub-Prime | ad hoc, simulation. |
|
| 11680 | Dragster | DP, math, probability theory, trees, graph theory, topological sorting. |
|
| 11683 | Laser Sculpture | ad hoc. |
|
| 11686 | Pick up Sticks | graph theory, topological sorting, DAG, detecting cycles. |
|
| 11687 | Digits | ad hoc, simulation. |
|
| 11688 | Rotate to root | binary search trees, rotations, move-to-root, computing height of tree after rotation to root for all nodes, recursion. |
|
| 11689 | Soda Surpler | ad hoc, simulation, simple math. |
|
| 11690 | Money Matters | graph theory, graph traversal, DFS, connected components. |
|
| 11691 | Allergy Test | DP. |
|
| 11693 | Speedy Escape | graph theory, shortest paths, SSSP, Dijkstra, binary search, (or MST, greedy, Prim's algorithm). |
|
| 11695 | Flight Planning | graph theory, trees, diameter of a tree, center of a tree, graph traversal, DFS. |
|
| 11696 | Beacons | computational geometry, sweepline by distance, sorting, distance, angles, circles, tangents, trigonometry, data structures, interval data structure, merging intervals, graph theory, DFS, connected components. |
|
| 11697 | Playfair Cipher | ad hoc, simulation, playfair cipher. |
|
| 11698 | Code Permutations | DP, math, permutations, order of a permutation, gcd, lcm, divisors, binomial coefficients, factorial. |
|
| 11699 | Rooks | ad hoc, all subsets, bitmasks, chessboard, rooks, covering squares on a chessboard. |
|
| 11700 | Pipes | DP, bitmasks. |
|
| 11701 | Cantor | simple math, Cantor set, base 3, converting from decimal fraction to ternary. |
|
| 11702 | Meltdown | computational geometry, simple polygons, ternary search, distance from point to line segment. |
|
| 11703 | sqrt log sin | ad hoc, simulation, simple math. |
|
| 11704 | Caper Pizza | computational geometry, angles, sweepline on a circle, sorting. |
|
| 11705 | Grasshopper | graph theory, shortest paths, BFS. |
|
| 11706 | Party Night | graph theory, "clique", testing if a graph is bipartite, 2-colorability, odd cycles, DFS. |
|
| 11707 | Pachinko | computational geometry, line segments, graph theory, reachability. |
|
| 11708 | Lexicographical Ranking | DP, simple math, binary search. |
|
| 11709 | Trust Groups | graph theory, strongly connected components. |
|
| 11710 | Expensive Subway | graph theory, MST. |
|
| 11711 | Turing | ad hoc, simulation, turing machine. |
|
| 11712 | Gnirut | ad hoc, simulation, turing machine. |
|
| 11713 | Abstract Names | ad hoc, simulation, string manipulation. |
|
| 11714 | Blind Sorting | comparison model, finding smallest and second smallest elements with the minimum number of comparisons, tournament tree, lower bound, decision tree. |
|
| 11715 | Car | physics, kinematics formulas, equations, simple math. |
|
| 11716 | Digital Fortress | ad hoc, simulation, string manipulation, encryption. |
|
| 11717 | Energy Saving Microcontroller | ad hoc, simulation. |
|
| 11718 | Fantasy of Summation | summations, simple math, repeated squaring. |
|
| 11719 | Gridland Airports | graph theory, number of spanning trees of a complete bipartite graph, Kirchhoff's matrix tree theorem, linear algebra, matrices, determinants, math, repeated squaring. |
|
| 11720 | How Many Ways | math, number of partitions of n into k distinct parts, number of partitions of n into parts whose greatest part is k, graph theory, adjacency matrix, number of paths of a fixed length, matrix multiplication, repeated squaring on matrices, linear algebra. |
|
| 11721 | Instant View of Big Bang | graph theory, detecting negative weight cycles, Bellman-Ford, shortest paths, SSSP, strongly connected components, DAG, DP. |
|
| 11722 | Joining With Friend | math, continuous probability theory, meeting probabilities, shape of coincidence, integration, area under curves, intervals, case analysis. |
|
| 11723 | Numbering Roads | ad hoc, simple math. |
|
| 11724 | Evaluate the Expression | greedy, graph theory, DAG, topological sorting, DFS, parsing, recursive descent parsing, operator precedence grammar. |
|
| 11725 | Colorful Board | DP, bitmasks, profile DP. |
|
| 11727 | Cost Cutting | ad hoc. |
|
| 11728 | Alternate Task | precalculation, math, number theory, divisors, sums of divisors. |
|
| 11729 | Commando War | greedy, sorting, scheduling algorithms. |
|
| 11730 | Number Transformation | graph theory, shortest paths, BFS, number theory, primes, prime factorization. |
|
| 11732 | "strcmp()" Anyone? | strings, trie, strcmp, number of comparisons, simple math, fast I/O. |
|
| 11733 | Airports | graph theory, MST, Kruskal's algorithm, union-find. |
|
| 11734 | Big Number of Teams Will Solve This | ad hoc, string manipulation. |
|
| 11736 | Debugging Ram | ad hoc, simulation. |
|
| 11737 | Extreme Primitive Society | ad hoc, simple math. |
|
| 11742 | Social Constraints | ad hoc, brute force. |
|
| 11743 | Credit Check | ad hoc, string manipulation. |
|
| 11744 | Parallel Carry Adder | ad hoc, simulation, simple math. |
|
| 11745 | Slitherlink | ad hoc, games, logic games, slitherlink, verifying if a solution is valid, graph theory, DFS, cycles. |
|
| 11747 | Heavy Cycle Edges | graph theory, MST, heaviest edge on a cycle. |
|
| 11748 | Rigging Elections | graph theory, DFS, reachability. |
|
| 11749 | Poor Trade Advisor | simple math, graph theory, DFS, connected components. |
|
| 11751 | Installing Diagnostic Software | simple math, greedy, binary number system, sorting. |
|
| 11752 | The Super Powers | ad hoc, simple math, square root, sorting, no input. |
|
| 11753 | Creating Palindrome | DP, palindromes, minimum number of insertions needed to make a string palindromic. |
|
| 11755 | Table Tennis | DP, math, probability theory, table tennis, cycles, Gaussian elimination. |
|
| 11757 | Winger Trial | graph theory, max-flow, min-cut, max-flow min-cut theorem, vertex capacities, geometry, circles, circle-circle intersection. |
|
| 11758 | Left Right | combinatorial game theory, nim, Bogus Nim, Moore's Nim, DP, binomial coefficients, repeated squaring. |
|
| 11759 | IBM Fencing | computational geometry, sorting, area, perimeter, point in convex polygon, graph theory, connected components. |
|
| 11760 | Brother Arif, please feed us! | ad hoc. |
|
| 11762 | Race to 1 | DP, math, probability theory, primes, sieve. |
|
| 11764 | Jumping Mario | ad hoc. |
|
| 11765 | Component Placement | graph theory, minimum cut, maximum flow, max-flow min-cut theorem. |
|
| 11766 | Racing Car Computer | DP. |
|
| 11768 | Lattice Point or Not | geometry, lattice points, number of lattice points on a line segment, math, gcd, linear diophantine equations, extended gcd, Bezout's identity. |
|
| 11769 | All Souls Night | computational geometry, 3D convex hull, surface area, point in plane, area of 3D triangle, linear algebra, math. |
|
| 11770 | Lighting Away | graph theory, strongly connected components, DAG, number of sources. |
|
| 11780 | Miles 2 Km | ad hoc, simple math, fibonacci numbers, brute force, DP, precalculation. |
|
| 11782 | Optimal Cut | DP, trees, graph theory. |
|
| 11783 | Nails | computational geometry, line segment intersection. |
|
| 11784 | Escape | ad hoc, simple math, geometry, rectangles, distance on the perimeter of a rectangle. |
|
| 11785 | Hypercube | ad hoc, graph theory, Hamming cube, hypercube graph, checking if a graph is a Hamming cube. |
|
| 11786 | Global Raining at Bididibus | ad hoc, water flow. |
|
| 11787 | Numeral Hieroglyphs | ad hoc, simple math. |
|
| 11790 | Murcia's Skyline | DP, weighted LIS. |
|
| 11792 | Krochanska is Here! | graph theory, shortest paths, BFS. |
|
| 11793 | Electoral Districts | ad hoc, backtracking, precalculation. |
|
| 11804 | Argentina | ad hoc, brute force, bactracking. |
|
| 11805 | Bafana Bafana | ad hoc, simple math. |
|
| 11806 | Cheerleaders | math, binomial coefficients, inclusion-exclusion, (or DP). |
|
| 11808 | Ensuring Victory | parsing, recursive descent parsing, operator precedence grammar, parse tree, math, calculus, differentiation, evaluating arithmetic expressions, fractions, gcd. |
|
| 11809 | Floating-Point Numbers | math, floating point numbers, mantissa, exponent, logarithms. |
|
| 11812 | Innovative Procession Management | graph theory, shortest paths, SSSP, Dijkstra, shortest path DAG, reconstructing the path. |
|
| 11813 | Shopping | graph theory, Dijkstra, shortest paths, SSSP, DP, TSP. |
|
| 11815 | Ideas | graph theory, graph traversal, BFS, queue. |
|
| 11816 | HST | ad hoc, simulation, simple math. |
|
| 11817 | Tunnelling The Earth | geometry, spherical coordinate system, cartesian coordinate system, coordinate system conversion, longitude, latitude, great circle distance. |
|
| 11818 | Game - Mouse and Cheese | DP, bitmasks, all subsets, winning/losing positions, games, graph theory, graph traversal, reachability, DFS. |
|
| 11821 | High-Precision Number | ad hoc, simple math, bignum, bigdecimal, addition, subtraction, formatting numbers. |
|
| 11825 | Hackers' Crackdown | DP, bitmasks, all subsets, iterating over all subsets of a set. |
|
| 11827 | Maximum GCD | ad hoc, brute force, simple math, gcd. |
|
| 11987 | Almost Union Find | data structures, union-find, augmenting data structures. |
|