Problem Classification on Spanish Archive

Arithmetic
NumberNameComments (highlight to reveal hints)
107 The Cat in the Hat  
113 Power of Cryptography Floating-point works
128 Software CRC Modular arithmetic
153 Permalex  
202 Repeating Decimals  
256 Quirksome Squares Quadratic equation
264 Count on Cantor Figure out which diagonal the number is on first
275 Expanding Fractions  
300 Maya Calendar  
332 Rational Numbers from Repeating Fractions Watch out for j = 0.
343 What Base Is This? Despite what is indicated, the minimum base to consider is 2, not 1.
355 The Bases Are Loaded  
362 18,000 Seconds Remaining Watch out for rounding errors. Use integer arithmetic.
369 Combinations  
377 Cowculations These are numbers in base 4 in disguise.
389 Basically Speaking  
446 Kibbles "n" Bits "n" Bits "n" Bits  
474 Heads/Tails Probability Do it incrementally
530 Binomial Showdown Cancel common factors as early as possible.
533 Equation Solver  
538 Balancing Bank Accounts  
561 Jackpot Just count the number of times each character occurs on each wheel, and sum appropriately.
575 Skew Binary  
594 One Little, Two Little, Three Little Endians  
619 Numerically Speaking  
636 Squares (III)  
651 Deck Harmonic series
684 Integral Determinant Use fraction-free Gaussian elimination
701 The Archeologists' Dilemma Write the unknown number in base 10, take log (base 10) on both sides of the equation and solve for the exponent.
763 Fibinary Numbers  
807 Towers of Powers  
846 Steps Answer the reverse problem: if I have k steps how far can I go?
893 Y3K Problem Advance by 1 year as much as possible first.
913 Joana and the Odd Numbers  
941 Permutations Work out one character at a time.
10014 Simple calculations Formulate a linear system of equations for the unknowns, and note that the resulting system is sparse.
10018 Reverse and Add  
10025 The ? 1 ? 2 ? ... ? n = k problem What is the smallest possible n where the equation has a chance to be true? Also, flipping a sign always changes the sum by an even amount.
10035 Primary Arithmetic  
10079 Pizza Cutting  
10083 Division Observe what happens on long division. Watch out for division by 0, and optimize when a == b.
10093 An Easy Problem! Note that the input string can be very long...reduce modulo N-1 whenever possible in calculations.
10109 Solving Systems of Linear Equations Write your own fractions with long long.
10114 Loansome Car Buyer Watch out for the "0 months" case.
10137 The Trip  
10161 Ant on a Chessboard Figure out which "level" it is on first.
10170 The Hotel with Infinite Rooms Quadratic equation
10176 Ocean Deep ! - Make it shallow !! Reduce modulo p as soon as possible
10182 Bee Maja Figure out which "ring" it is on, and then walk along the ring.
10190 Divide, But Not Quite Conquer!  
10202 Pairsumonious Numbers If you can guess the smallest number, can you get the rest?
10229 Modular Fibonacci How do you use matrices to compute Fibonacci numbers quickly?
10268 498-bis  
10309 Turn the Lights Off Treat this as a system of linear equations modulo 2, with variables representing whether to press a switch or not.
10323 Factorial! You Must be Kidding!!! Stupid question. You have to know that they want n! to be infinity if n is odd and negative, and -infinity if n is even and negative.
10346 Peter's Smokes There is a "closed form" formula.
10378 Complex Numbers Use polar coordinates
10427 Naugthy Sleepy Boys  
10442 Basic Simple base conversion and checking, but remember that the base can itself be specified in the alternate format.
10473 Simple Base Conversion Easiest to make use of built-in conversion routines (e.g. scanf() and printf())
10489 Boxes of Chocolates Do reduction as you compute
10512 A Day in Math-land Find a quadratic equation for Y^2 where coefficients are expressions of P and Q.
10551 Basic Remains  
10555 Dead Fraction Watch out for repeating fractions
10586 Polynomial Remains  
10625 GNU = GNU'sNotUnix If you encode the frequencies as a vector, then the application of a rule is simply a matrix multiplication.
10633 Rare Easy Problem  
10642 Can You Solve It?  
10655 Contemplation - Algebra Look for recurrence, and then a fast way to evaluate it
10681 Teobaldo's Trip Reachability in exactly k step is equivalent to the k-th matrix power (boolean "multiplication") of the adjacency matrix.
10683 The decadary watch Use integer arithmetic
10689 Yet another Number Sequence Use the matrix formulation and do fast matrix exponentiation.
10693 Traffic Volume Look at how long it takes between one car arriving at a particular point and the next car.
10700 Camel trading There is an O(n^3) algorithm, but there is also an O(n) algorithm. Observe that (a+b)*c > a+b*c.
10719 Quotient Polynomial  
10773 Back to Intermediate Math  
10784 Diagonal Solve the quadratic inequality
10812 Beat the Spread!  
10814 Simplifying Fractions  
10870 Recurrences Express the recurrence as a matrix and use fast exponentiation.
10916 Factsone Benchmark Compare log2 of the values instead of the values themselves.
10929 You can say 11  
10931 Parity  
10951 Polynomial GCD Euclidean algorithm with polynomial division
10976 Fractions Again?! Just search for x and solve for y.
11001 Necklace Just try them all
11024 Circular Lock Solve system of equations
11040 Add bricks in the wall  
11042 Complex, difficult and complicated Just do brute force
11150 Cola You have to borrow at most one bottle
11185 Ternary  
11219 How old are you?  
11231 Black and white painting It's easier to count odd and even rows separately.
11287 Pseudoprime Numbers  
11289 Friend or Foe? Look up something called the "Perceptron Algorithm". Or use linear programming and simplex algorithm.
11313 Gourmet Games Try to do it in "one line"
11356 Dates Standard date calculations
11371 Number Theory for Newbie Sort the digits to get a and b (watch out for leading 0's). Beware that there may be overflow for a.
11401 Triangle Counting There is a closed form formula obtained by looking at the number of triangles that can be obtained with fixed longest and 2nd longest sides.
11417 GCD  
11526 H(n) Figure out how many values of i have n/i equal to a certain value to quickly group terms in the sum together.
11549 Calculator Conundrum Use a table or a set to keep track of what has been seen so far. There will be a cycle eventually.
11551 Experienced Endeavour Express each step as a linear transformation by a matrix multiplication. Now use fast matrix exponentiation to get the answer.
11554 Hapless Hedonism Try to figure out a triple summation, and from there figure out a closed form formula.
11582 Colossal Fibonacci Numbers! Fibonacci numbers are completely determined by the last two elements and they must repeat in n^2 steps. Compute the cycle length and use that to reduce a^b.
11614 Etruscan Warriors Never Play Chess Solve the quadratic inequality.
11615 Family Tree  
11616 Roman Numerals  
11636 Hello World! The fastest way is to double as much as possible.
11677 Alarm Clock  
11723 Numbering Roads  
11805 Bafana Bafana Just use modular arithmetic.
11808 Ensuring Victory  
11809 Floating-Point Numbers Try all possible values of M and E, and compare the values after logarithm is taken. Take the one that gives the closest logarithm.
11847 Cut the Silver Bar Think about the number in binary.
11866 Triangle Look for a closed-form formula.
11947 Cancer or Scorpio Straightforward date calculations
11955 Binomial Theorem Be careful about overflow.
12019 Doom's Day Algorithm Just use a date class
12028 A Gift from the Setter Sort the numbers. How does it help to have the partial sums available?
12045 Fun with Strings Express number of a's and b's as a vector and use a matrix to model how it changes every step. Solve for the original number of a's and b's.
12060 All Integer Average  
12136 Schedule of a Married Man  
12293 Box Game One can prove by induction that the only starting values in which Alice loses is when n is a power of 2 minus 1.
12342 Tax Calculator Use integer calculations.
12438 February 29 Can be done in constant time
12485 Perfect Choir You want them to end on the average of the notes. Why?
12602 Nice Licence Plates  
12609 Sequential Thinking For every N, if N is not divisible by 4 you only have to add one extra digit. You can figure out the length of the digits for all 1-digit N, 2-digit N, etc. Once you figured out which chunk you are in, youc an skip ahead to k-digit N. Within all the k-digit N's, you can easily figure out which group of 4 N's it must involve, and then you can just step through them.
12636 Disguised Giveaway Very similar to "Pairsumonious Numbers".
12761 Blue Chips Express this as a recurrence and use matrix power to compute the answer quickly.

Backtracking
NumberNameComments (highlight to reveal hints)
148 Anagram checker  
193 Graph Coloring Look for largest independent set
229 Scanner To speed things up, look for lines which needs to be either completely filled or completely empty. Make sure that all sensor readings are satisfied.
301 Transportation  
307 Sticks Try to make sure that you do not search the same configuration for a stick if it has already failed for a different stick.
331 Mapping the Swaps  
529 Addition Chains Start from a chain of length 1 and extend chains in all possible ways until n is reached. Need to prune efficiently.
539 The Settlers of Catan Try each starting vertex and go as far as you can
574 Sum It Up Just try all possibilities.
646 The Gourmet Club Just try all the permutations and prune as soon as possible.
751 Triangle War Prune as soon as a winner is found
843 Crypt Kicker Search one word at a time (instead of one letter) to speed up
861 Little Bishops You can precompute. Also, note that the black squares and the white squares can be handled separately to reduce search time.
993 Product of digits  
10111 Find the Winning Move Look up alpha-beta pruning to make the search fast enough.
10160 Servicing stations Dominating set, NP-hard
10496 Collecting Beepers Just try all permutations
10503 The dominoes solitaire Just try all permutations and prune as quickly as possible. The end pieces are not allowed to rotate, but the other ones are.
10637 Coprimes  
10638 The Trip Search through all ways of distributing extra pennies, and for each one, find the best way to achieve this.
10937 Blackbeard the Pirate  
11195 Another n-Queen Problem Standard n-queens approach: represent the column index of the queens in each row as a permutation. Generate all permutations incrementally and prune as soon as possible.
11323 Satisfying Constraints This is almost like asking whether a graph is 2-colorable

Big Number
NumberNameComments (highlight to reveal hints)
288 Arithmetic Operations With Large Integers Ignore the formatting in the sample output and follow what the description says.
324 Factorial Frequencies  
424 Integer Inquiry  
465 Overflow  
495 Fibonacci Freeze  
619 Numerically Speaking  
623 500!  
748 Exponentiation Do it exactly with large integers and figure out the number of decimal places.
787 Maximum Sub-sequence Product  
10007 Count the Trees Catalan numbers, need big numbers
10023 Square root See my big number implementation
10069 Distinct Subsequences Build a table so that entry at (i,j) is the number of subsequences of Z[1..j] in X[1..i]
10070 Leap Year or Not Leap Year and ... The year can be huge
10106 Product  
10157 Expressions Break up a string into two parts with smaller parameters.
10183 How many Fibs?  
10198 Counting Need big numbers
10220 I Love Big Numbers! You can precompute.
10247 Complete Tree Labeling Look for a recurrence that reduces the depth.
10254 The Priest Mathematician  
10303 How Many Trees? Catalan numbers
10359 Tiling  
10494 If We Were a Child Again  
10519 !! Really Strange !! Look at the planar graph where vertices are intersection points connected by circular arcs. Apply Euler's formula.
10523 Very Easy !!!  
10541 Stripe Build a table indexed by length and the number of numbers to place
10579 Fibonacci Numbers  
10814 Simplifying Fractions  
10862 Connect the Cable Wires Look for a linear recurrence
10925 Krakovia  
11059 Maximum Product  
11344 The Huge One  
11448 Who said crisis? The description isn't very clear---the largest number can be (10^100)^100.
11821 High-Precision Number Find the one with the most decimal places and shift all numbers by that many digits to convert to integer arithmetic.
11879 Multiple of 17  

Combinatorics
NumberNameComments (highlight to reveal hints)
135 No Rectangles Symmetric Balanced Incomplete Block Design
239 Tempus et mobilius. Time and motion Simulate for 12 hours and study the resulting permutation with cycle decomposition.
441 Lotto  
485 Pascal's Triangle of Death  
491 Tile Topology Do a Google search on "polyominoes" and hardcode the answers in
900 Brick Wall Patterns Fibonacci numbers, watch out for overflow
991 Safe Salutations Look for a recurrence and recognize that these are the Catalan numbers
10007 Count the Trees Catalan numbers, need big numbers
10105 Polynomial coefficients Multinomial coefficients
10128 Queue Place the tallest person and reduce to subproblems. The subproblems can be precomputed.
10219 Find the ways! Remember that log of a product is the sum of logs.
10223 How many nodes? Catalan numbers
10247 Complete Tree Labeling Look for a recurrence that reduces the depth.
10303 How Many Trees? Catalan numbers
10338 Mischievous Children Standard permutation question.
10450 World Cup Noise Find a recurrence relation
10634 Say NO to Memorization Find a recurrence relation
10790 How Many Points of Intersection? Each intersection point is formed by two lines that are diagonals of a trapezoid
10910 Marks Distribution Binomial coefficients
10943 How do you add? Binomial coefficients
11330 Andy's Shoes This has something to do with cycle decomposition
11806 Cheerleaders It's easier to count the number of assignments that do not cover at least one side. Use inclusion-exclusion principle.
12024 Hats Look up derangements. There is a recursive formula to compute that.
12298 Super Poker II Represent the number of cards of each rank as a generating function for each suit. The answer can be read off from the coefficients of the product of the generating functions. Subquadratic polynomial multiplication is needed.
12492 Rubik Cycle Look at each cell individually, and it must cycle back to the original spot in at most 48 moves. The answer is the LCM of the cycle lengths of each cell.

Data Structure
NumberNameComments (highlight to reveal hints)
115 Climbing Trees trees
136 Ugly Numbers Priority queue
261 The Window Property Use a set to keep track of substrings
443 Humble Numbers Almost the same as Ugly Numbers
484 The Department of Redundancy Department Use a map
496 Simply Subsets Sets
501 Black Box Use two heaps
625 Compression Map
698 Index Note: output a blank line after every case, and repeated terms in the list should be displayed multiple times in the index.
944 Happy Numbers See 10591 but with some memoization.
978 Lemmings Battle! Use a priority queue to keep track of each team.
1131 Square dance Union-Find
1136 Help R2-D2! Use a segment tree to keep track of range maximum to easily find first index that work.
1203 Argus Use a priority queue to keep track of the next reporting times of each request.
10107 What is the Median? Use two heaps
10125 Sumsets Use the meet-in-the-middle strategy
10126 Zipf's Law Use a map, or sorting, or anything else.
10282 Babelfish Use a map
10420 List of Conquests Just use a map
10583 Ubiquitous Religions Union-find
10591 Happy Number Use a set to keep track of numbers that have already appeared.
10608 Friends Union find
10728 Help!  
10815 Andy's First Dictionary Use a set
10895 Matrix Transpose Store as an array of coordinate-element pairs and process after sorting.
11035 Card Hands Look at each hand backwards and build a tree.
11062 Andy's Second Dictionary  
11111 Generalized Matrioshkas Use a stack to keep track of the nesting and the size of the directly nested toys inside so far.
11136 Hoax or what  
11234 Expressions Use a stack to build a tree, then do BFS.
11239 Open Source  
11402 Ahoy, Pirates! Use a segment tree. Beware that M > 100.
11503 Virtual Friends Union-find
11525 Permutation Use a Fenwick tree to dynamically handle the rank of each remaining element.
11610 Reverse Prime Use a sieve to generate the primes, and then use two Fenwick trees to keep track of the cumulative sums (divisors and count) in the range.
11678 Cards' Exchange Use two sets and compute intersections.
11995 I Can Guess the Data Structure! Just simulate all three types and check.
12238 Ants Colony Least common ancestor
12356 Army Buddies Use a "link" structure to refer to previous and next buddies, similar to a linked list. Caution: using C++ I/O will cause it to run too long.

Dynamic Programming
NumberNameComments (highlight to reveal hints)
103 Stacking Boxes Longest increasing subsequence
104 Arbitrage  
108 Maximum Sum Maximum sum subvector
111 History Grading Longest common subsequence
116 Unidirectional TSP  
147 Dollars Standard coin problem
164 String Computer The online judge doesn't accept all valid solutions. Break ties by using insert last.
180 Eeny Meeny The unsafe positions can be computed with dynamic programming. Note that they are only interested in positions < L/2 where L is the lower estimate.
222 Budget Travel Min cost to reach destination from each station
231 Testing the CATCHER Longest increasing subsequence
233 Package Pricing There are no bounds on the number of bulbs required, but it turns out to be small enough to use a dynamic programming approach.
242 Stamps and Envelope Size  
323 Jury Compromise Have a 3D table indexed by the number of people considered so far, the size of the subset formed, and the difference of the set.
348 Optimal Array Multiplication Sequence Compute the best sequence for each product Ai...Aj
357 Let Me Count The Ways Build a table for the number of ways to make a certain amount with coins of value no bigger than a certain coin.
366 Cutting Up Remember the best cuts for m x n with at most L layers.
436 Arbitrage (II)  
452 Project Scheduling  
473 Raucous Rockers An O(n*m*t) algorithm is sufficient. Incrementally process the songs, and for each total minutes used, record the largest number of songs that we can record in that amount of time.
481 What Goes Up Longest increasing subsequence
497 Strategic Defense Initiative Longest increasing subsequence
507 Jill Rides Again Largest subvector sum
526 String Distance and Transform Process Standard string distance problem.
531 Compromise Longest common subsequence
562 Dividing Coins Keep track of all the sums you can form.
580 Critical Mass Keep track of the number of configurations of different height and top blocks.
585 Triangles  
590 Always on the run The states are the number of flights taken and the city at the end.
607 Scheduling Lectures Build a table indexed by number of topics considered and number of minutes left in last lecture.
624 CD Subset sum
662 Fast Food Consider the minimum distance sum for the first n stations using k depots as n and k increase.
674 Coin Change Standard problem, use 2-D array on max denomination allowed and total sum
757 Gone Fishing Build a table indexed by lake and time
825 Walking on the Safe Side Compute the number of paths to each reachable intersection.
836 Largest Submatrix For each starting/ending column pair, compute a boolean array whose entry indicate if that row has 1's in every column in between. Look for largest contiguous sequence in this array.
847 A multiplication game Note that all numbers that can be formed have only prime factors 2, 3, 5, 7, and the sum of exponents cannot be more than 32. There cannot be that many distinct states.
910 TV game The states are the number of moves made and where we are starting the game from.
926 Walking Around Wisely Compute the number of ways to get to each point.
967 Circular Use cumulative sums to speed up the search.
986 How Many? Count the number of paths you can get to each location with r peaks and last move being up/down.
990 Diving for Gold 0-1 Knapsack problem. Remember the maximum profit achievable using t minutes and the first n objects.
1062 Containers How is this related to longest increasing subsequence?
1110 Pyramids The standard knapsack approach would require too much memory. Instead, it can be checked (?) that any possible case requires at most 6 different pyramids. You can compute for a given sum and a given number of pyramids, what is the minimum largest pyramid you need to form that sum (if it exists).
10003 Cutting Sticks Look for all the ways to make the first cut, and solve the subproblems.
10032 Tug of War Try to keep track of which subset size can make which sum out of the first few people.
10036 Divisibility Look at congruence classes mod K
10049 Self-describing Sequence Consider an inverse table such that g[k] is the smallest n such that f[n] = k
10051 Tower of Cubes Longest Increasing Subsequence
10066 The Twin Towers Longest common subsequence
10069 Distinct Subsequences Build a table so that entry at (i,j) is the number of subsequences of Z[1..j] in X[1..i]
10074 Take the Land Try to look at the longest empty line starting in each row, and process that in the other dimension.
10081 Tight Words Look at the percentage of strings of length i ending with digit j
10100 Longest Match Horrible problem statement. Longest common subsequence, digits are letters too, and last line not terminated by '\n'
10130 SuperSale Each person in the family can be solved independently. Use an array indexed by total weight to determine the maximum value that can be achieved for the weight (0-1 knapsack)
10131 Is Bigger Smarter? Sort the list in decreasing order by one attribute, then look for longest increasing subsequence in the other.
10149 Yahtzee Look at subsets of categories chosen so far, as well as the sum so far (up to 64)
10157 Expressions Break up a string into two parts with smaller parameters.
10192 Vacation Longest common subsequence.
10198 Counting Need big numbers
10243 Fire! Fire!! Fire!!! The states are (root of the tree, whether the parent has an exit).
10271 Chopsticks Store in a table the minimum badness choosing k pairs from the biggest n sticks.
10285 Longest Run on a Snowboard  
10304 Optimal Binary Search Tree Use the solutions to subproblems which are indexed by the start and end symbol (correspond to a subtree). The complexity is O(n^3).
10306 e-Coins Build a table indexed by the sum in each coordinate.
10324 Zeros and Ones Compute a cumulative sum and use that to answer each query in O(1) time.
10334 Ray Through Glasses Remove the ray segment before the first bounce. What does the remaining ray look like?
10337 Flight Planner Compute the best cost to get to every distance, altitude pair.
10350 Liftless EME Work out the minimum time to each ladder from the bottom.
10359 Tiling  
10360 Rat Attack Note that the sum of population in a square can be computed in constant time if you have computed the cumulative sum of the rectangle from (0,0) to (x,y) for all (x,y).
10364 Square An approach similar to 307 can be used to prune the search space. Or we can use dynamic programming where the states are the subset of sticks left and how many sides are left.
10400 Game Show Math Remember which intermediate results are possible for the first k numbers.
10401 Injured Queen Problem Work on one column at a time and see how many configurations there can be if a queen is placed at a certain cell and to its left.
10404 Bachet's Game  
10405 Longest Common Subsequence  
10440 Ferry Loading II Find the best way to transport the first k cars for the DP approach. For the greedy approach, it is always best to take as many cars as possible for the last ferry.
10450 World Cup Noise Find a recurrence relation
10453 Make Palindrome Work from outside in.
10465 Homer Simpson Standard knapsack type DP
10482 The Candyman Can Keep track of the triples that we can get after distributing each additional candy. There are not that many possible triples, especially if the triple is sorted.
10502 Counting Rectangles Figure out the answer for one row. Compress the matrix into O(n^2) rows where each row represent the block from row i to row j.
10534 Wavio Sequence Longest increasing/decreasing subsequence.
10541 Stripe Build a table indexed by length and the number of numbers to place
10549 Russian Dolls Build a table indexed by which dolls are at the top of each "pile"
10558 A Brief Gerrymander  
10581 Partitioning for fun and profit  
10616 Divisible Group Sums Store the number of ways for each residue mod D.
10626 Buying Coke The number of $1 coins is related to the number of other coins, the total amount of cash to start with, and the number of cokes bought so far.
10634 Say NO to Memorization Find a recurrence relation
10635 Prince and Princess Transform longest common subsequence to longest increasing subsequence.
10651 Pebble Solitaire There are at most 2^12 states to consider.
10664 Luggage Subset sum to see if a subset can sum up to half the total
10684 The jackpot Maximum subvector sum...watch out for bets that are 0 despite what the problem description says!
10702 Travelling Salesman The states are the end city of the trip so far and how many trips so far.
10715 Cat  
10721 Bar Codes For each m, remember the number of bar codes for a particular pair of n and k and recurse.
10759 Dice Throwing Use a table to remember the number of ways a sum can be formed using k dice.
10817 Headmaster's Headache Remember how many times each subject (up to 2) is covered, and decide for each teacher whether to hire or not.
10819 Trouble of 13-Dots Standard knapsack with minor trick to see how much money you can use. Remember that the refund is based on how much money you spent.
10827 Maximum sum on a torus Similar to problem 108, but the rectangles can wrap around. Extend the grid once in one dimension, and for the other dimension compute the maximum contiguous array sum of the elements as well as their negatives. The best chunk is either the maximum contiguous sum, or the total minus the minimum contiguous sum.
10862 Connect the Cable Wires Look for a linear recurrence
10891 Game of Sum Remember the best score for each subarray.
10898 Combo Deal Probably easier to use memoization
10913 Walking on a Grid The states are the location, the number of negative numbers allowed, and whether we are allowed to move left/right from the current location.
10918 Tri Tiling Look for a recurrence
10930 A-Sequence Make sure you check all the conditions. As you process the elements, keep track of all the sums that can be formed (up to 1000).
10934 Dropping water balloons Given n ballons and t trials, how tall of a building can you measure?
10940 Throwing cards away II Look at what happens after one iteration. Reduce to a smaller problem.
11000 Bee Find recurrence relations for number of male and female bees
11022 String Factoring Find the best weight for the substring starting at position i and ending at position j
11038 How Many O's? Try to break down the problem by reducing the number of digits in each call.
11069 A Graph Problem  
11133 Eigensequence Count the number of eigensequences with a particular ending element
11135 Gopher that walks and swims  
11137 Ingenuous Cubrency  
11151 Longest Palindrome Remember the answer for all substrings.
11176 Winning Streak Build a table of the probability of playing n games and having winning streak no longer than k games. Find a recursion that considers a winning streak of various lengths in the first few games.
11181 Probability/Given Compute the probability of all possible subsets, and divide that into the probability of all possible subsets with each shopper chosen.
11284 Shopping Trip There is a O(n^2 2^n) algorithm for travelling salesman where the states are (set of visited stores, last store to visit). Beware that there may be multiple edges between stores.
11285 Exchange Rates Keep track of the maximum US and Canadian dollars you can have after each day.
11288 Carpool For each subset of people, find the best solution. Recurse by removing a subset of up to 5 people.
11307 Alternative Arborescence Note that you may have to use more than two colours. The states in dynamic programming are the minimum sum for a tree rooted at i with colour j. Look up chromatic sums on trees to see that you do not need more than log_2(n) colours.
11310 Delivery Debacle  
11328 Drawing Straws at the Office Figure out a recurrence and use memoization
11331 The Joys of Farming 2-coloring + dynamic programming
11391 Blobs in the Board The states are the dimensions of the grid, as well as the positions of the blobs (as a binary number).
11407 Squares  
11450 Wedding shopping Just a table indexed by item and total spent
11456 Trainsorting Longest increasing/decreasing subsequence.
11472 Beautiful Numbers The states are subset of digits used, the length, and the starting digit. Remember not to count the numbers with leading 0's.
11517 Exact Change Build a table for each possible sum to see the minimum number of bills needed for that sum.
11552 Fewest Flops Compute the answers for the first few chunks for all possible last character. Try to extend the answers to one more chunk.
11578 Situp Benches At each timeslot the two benches can be in one of 25 configurations. Determine the minimum cost to get to each configuration.
11584 Partitioning by Palindromes There are two levels of dynamic programming here. First involves determining whether a substring is a palindrome. The second part involves determining if the optimal partitioning for the first k characters.
11703 sqrt log sin Just memorize results.
11762 Race to 1  
11766 Racing Car Computer For each group of identical readings, you can determine the maximum number of readings that can be correct. Find the subset of nonoverlapping positions (implied by the readings) whose correct readings sum to a maximum.
11790 Murcia's Skyline Standard O(n^2) longest increasing subsequence algorithm can be modified for this problem.
11832 Account Book For each amount, keep track of how you can get to the amount from the individual transactions incrementally.
11851 Celebrity Split Look for all possible sums for the first half of the values, then do the same for the second half, and try to match them up.
11932 Net Profit Remember which nodes have been exhausted.
11957 Checkers Figure out the number of paths to the top from each square, working from the top.
12294 RPG battles It's always best to drink the stronger potion as soon as possible, but we may wish to wait until we drink the doubling potions. The states in the table are the number of battles fought, the power level after that battle, and how many doubling potions are unused. Note that we never have to use more than 7 doubling potions because of the bounds.
12297 Super Poker Find a recurrence for number of ways to form sum n using k items, and use fast matrix exponentiation to compute
12484 Cards Consider the maximum score for each segment of increasing lengths.
12486 Space Elevator Count the number of floors with n digit starting with digit d.
12627 Erratic Expansion Look at what happens in the top half and the bottom half, use memoization to speed things up.

Game Theory
NumberNameComments (highlight to reveal hints)
10111 Find the Winning Move Look up alpha-beta pruning to make the search fast enough.
11311 Exclusively Edible Transform this problem into a game of nim with 4 heaps.
11489 Integer Game We only have to know the digit sum and the number of digits mod 3. After the first move, we can only remove digits which are multiple of 3.
11840 Tic-tac-toe Each move reduces the size of a nim heap, or break a nim heap into two.
11927 Games are Important This is a sum of nim games.

Geometry
NumberNameComments (highlight to reveal hints)
109 SCUD Busters Polygon computations
121 Pipe Fitters  
132 Bumpy Objects  
137 Polygons Polygon intersection
143 Orchard Trees Scanline (watch out for same point given multiple times!)
149 Forests Look at trees from closest and keep a list of blocked angles
184 Laser Lines  
190 Circle Through Three Points  
191 Intersection  
194 Triangle Apply all the rules until none can be applied any more.
218 Moth Eradication Convex hull
223 Classifying Lots in a Subdivision Construct a graph and traverse each lot by picking the lowest left vertex and always making the most counterclockwise turn.
270 Lining Up O(N^3) is too slow. Can you do O(N^2 log N)?
273 Jack Straws  
295 Fatman Use binary search, and expand the obstacles to see if a point can pass through.
316 Stars Fix two points in the constellation and two points in the map, and see if you can rotate & scale the constellation to the map
356 Square Pegs And Round Holes Just loop through each cell and count.
361 Cops and Robbers It has something to do with convex hulls. Watch out for the cases when the number of cops or robbers is less than 3.
376 More Triangles ... THE AMBIGUOUS CASE Sine and cosine laws (watch out for theta = 0!)
378 Intersecting Lines  
438 The Circumference of the Circle  
453 Intersecting Circles  
460 Overlapping Rectangles The important points are either one of the original vertices or an intersection of two edges.
476 Points in Figures: Rectangles  
477 Points in Figures: Rectangles and Circles  
478 Points in Figures: Rectangles, Circles, and Triangles  
535 Globetrotter Great circle distance
569 Horse Shoe Scoring Tricky circle analysis, just be careful
578 Polygon Puzzler Project all points onto the plane as 2D coordinates, and use standard 2D area of polygon routines.
579 ClockHands  
587 There's treasure everywhere!  
609 Metal Cutting Try all permutation of cuts
634 Polygon  
681 Convex Hull Finding NOTE: the statement that n <= 512 and that there are no colinear points are both violated in the judge's input!
737 Gleaming the Cubes Intersect one cube at a time with the current intersection. It is sufficient to intersect each dimension individually.
754 Treasure Hunt How quick is your solution? Come talk to me.
800 Crystal Clear The online judge is wrong! It accepts only programs that produce no output.
802 Lead or Gold This problem can be reduced to a 2D convex hull problem.
805 Polygon Intersections The online judge is wrong! It accepts only programs that produce no output.
811 The Fortified Forest Try all possible subsets, and see if the convex hull of the remaining trees can be surrounded.
819 Gifts Large and Small Consider only the convex hull. Smallest rectangle must have a side common with the hull. For largest one, just try rotations of the rectangle (about 100000 steps from 0 to PI/2 is enough).
833 Water Falls Line intersection
866 Intersecting Line Segments  
920 Sunny Mountain  
1060 Collecting Luggage Use binary search on time to check if we can reach the luggage at a particular time. To check that, construct a visibility graph.
1106 Machine Works Each machine introduces a line, and at each point you can determine what is the maximum amount of money available by looking at the highest point among all the lines. This in turns become an incremental convex hull algorithm that can be done in O(n log n) time.
10002 Center of Masses Triangulation and weighted averages
10005 Packing polygons If it is possible, we can always move the circle so that it touches two of the points. Use this to get an O(n^3) algorithm.
10012 How Big Is It? Try all possible permutations, and don't forget to check that the circle doesn't overlap with every circle (not just the previous one)
10043 Chainsaw Massacre There are only O(n^2) rectangles that one must examine: only those whose sides touches a tree or the boundary, and not containing other trees need to be examined.
10065 Useless Tile Packers Convex hull, area of polygon
10075 Airlines Great circle, all pairs shortest path. Round every distance calculation (pairwise and during Floyd's algorithm) to nearest integer.
10078 The Art Gallery Orientation analysis
10088 Trees on My Island Use Pick's theorem. The number of lattice points on the boundary can be computed using GCD.
10089 Repackaging You can solve this problem the same way as Lead or Gold (802), but there may be faster ways.
10112 Myacm Triangles  
10136 Chocolate Chip Cookies For each pair of points, there are potentially two cookies to check.
10195 The Knights of The Round Table Look up "incircle".
10209 Is This Integration  
10215 The Largest/Smallest Box... Write the volume as a function of x, and differentiate to get the minimum/maximum value.
10221 Satellites Cosine law, circle
10224 Return of the Jedi All the places to travel are either around the tree (circle) or a common tangent to two circles. Build a graph with the interesting points and compute shortest path.
10228 Star not a Tree? Minimize the function by gradient descent.
10233 Dermuba Triangle  
10242 Fourth Point !!  
10263 Railway Just projection of point to line.
10283 The Kissing Circles Look at the regular polygon formed by the centres of the smaller circles.
10286 Trouble with a Pentagon Look at one of the triangles formed by the square and the pentagon, apply sine law.
10297 Beavergnaw  
10301 Rings and Glue  
10310 Dog and Gopher Use integer arithmetic. Also, the gopher escapes when both can reach a hole at the same time.
10321 Polygon Intersection Intersection points include vertices that are inside the other polygon. You will also need to remove duplicates intersection points.
10347 Medians Search for "triangle medians"
10387 Billiard Extend the table and work on one straight line.
10432 Polygon Inside A Circle Trigonometry
10439 Temple of Dune The three given points and all other vertices pass through the same circle.
10451 Ancient Village Sports  
10456 Intelligent Cats Can you do it if it's a triangle and one of the points is a vertex? How do you reduce it to a triangle?
10499 The Land of Justice Watch out for N = 1.
10519 !! Really Strange !! Look at the planar graph where vertices are intersection points connected by circular arcs. Apply Euler's formula.
10553 Treasure Map  
10556 Biometrics  
10566 Crossed Ladders Find one equation that relates x, y, c, and w together and solve.
10573 Geometry Paradox  
10577 Bounding box  
10585 Center of symmetry Where must the center of symmetry be?
10589 Area  
10652 Board Wrapping Convex hull
10668 Expanding Rods Find the right equations and solve
10678 The Grazing Cow Area of an ellipse
10713 Map You can always do it in at most 2 legs
10902 Pick-up Sticks  
10915 War on Weather Find the distance of the center of the earth (by projection) to the line of sight, and see if it is farther than the radius of the earth.
10936 Land surveyor's job  
10991 Region Look at the triangle formed by the centres.
11068 An Easy Task Just solve the system of equations
11130 Billiard bounces  
11152 Colourful Flowers Look up the relationship between side lengths and the radii of incircle and circumscribed circle. Use Heron's formula.
11207 The easiest way The four squares must align with the edges of the big piece of paper for optimality.
11227 The silver bullet Converting to integers first will avoid floating-point computations
11232 Cylinder Remember to consider both ways of rolling up the sides.
11265 The Sultan's Problem Each successive line divides the current polygon into two parts, and you need to keep one of them.
11289 Friend or Foe? Look up something called the "Perceptron Algorithm". Or use linear programming and simplex algorithm.
11314 Hardly Hard The shortest "long" way from A to B is a straightline if you reflect the point along the two axes.
11326 Laser Pointer Just extend the hallway and let the beam run straight
11343 Isolated Segments Standard line segment intersection.
11447 Reservoir Logs  
11479 Is this the easiest problem? Watch out for negative sides
11507 Bender B. Rodriguez Problem Just work out all the cases.
11519 Logo 2 Handle the FD and BK cases by calculations, and LT and RT by search.
11579 Triangle Trouble If the longest side is fixed, then the next two longest sides maximizes the area.
11626 Convex Hull  
11646 Athletics Track Do a binary search on the width.
11684 MC part deux The triangles are nodes in a graph, and we want to do DFS from the root to extend the stakes that we know.
11746 Finding the Transmitter Again Write the equations. It will either be an intersection of two circles, one circle and one line, or two lines.
11769 All Souls Night 3-d convex hull. Use brute force and try all possible triples of points.
11800 Determine the Shape Careful case analysis.
11817 Tunnelling the Earth Great circle, spherical coordinates
11834 Elevator If it is possible at all, then it must be possible to have the two circles at opposite corners.
11836 Star War Consider all vertex-faces distance and edge-edge distances
11909 Soya Milk Note that there are two cases, depending on how far you have tipped the container.
11928 The Busy Dog This is the "winding number": just count the number of times the dog crosses the positive x-axis and in which direction.
12483 Tobaggan of Marbles Compute the distance of each end point to the wall and the slope below it, and take the minimum.
12603 Bouncing Bowling Ball Just simulate the bounces, and remember that the centre of the ball does not reach the boundary.

Graph
NumberNameComments (highlight to reveal hints)
117 The Postal Worker Rings Once Eulerian tour/Chinese Postman
125 Numbering Paths Floyd's
157 Route Finding Shortest path
186 Trip Routing Floyd's algorithm
192 Synchronous Design Cycle detection, and then propagate delay.
193 Graph Coloring Look for largest independent set
200 Rare Order Transitive closure/topological sort
247 Calling Circles Transitive closure and equivalence relation
259 Software Allocation Use maximum flow, with the source node connecting to the computer nodes, the job nodes connecting to the sink node, and an edge from a computer to a job if the job can be assigned to that computer.
260 Il Gioco dell'X Connectivity check
273 Jack Straws  
280 Vertex Just use Floyd's algorithm
295 Fatman Use binary search, and expand the obstacles to see if a point can pass through.
308 Tin Cutter You can do this by floodfill but the "bitmap" is too large. Luckily the number of "interesting" coordinates is small so you can compress the range.
314 Robot Construct a graph where each node is (location,direction).
315 Network Articulation points
318 Domino Effect Shortest paths
321 The New Villa BFS on a graph with nodes as (location, state of lights)
334 Identifying Concurrent Events Transitive closure. You need to print an extra space after every pair to get it accepted.
336 A Node Too Far Shortest path
341 Non-Stop Travel Shortest path
352 The Seasonal War Connected components. Diagonal cells are adjacent too.
383 Shipping Routes Shortest path
423 MPI Maelstrom Shortest path with Floyd's algorithm
437 The Tower of Babylon Construct an acyclic directed graph of the blocks (and orientation), look for longest path
439 Knight Moves BFS
459 Graph Connectivity  
469 Wetlands of Florida Simple flood fill
532 Dungeon Master  
534 Frogger Think about a variant of Kruskal's algorithm.
544 Heavy Cargo A variant of Kruskal's algorithm
558 Wormholes  
563 Crimewave Set this up as a network flow with node capacities.
567 Risk All-pairs shortest paths
572 Oil Deposits Connectivity
590 Always on the run The states are the number of flights taken and the city at the end.
599 The Forrest for the Trees Use DFS.
610 Street Directions How is this related to biconnected components?
615 Is It A Tree?  
626 Ecosystem Just brute force it...it is assumed that a species does not consume itself.
627 The Net Shortest path with BFS
657 The die is cast Use flood-fill to label the dice, and then use flood-fill to count the dots.
670 The Dog Task Maximum cardinality bipartite matching
715 Substitution Cipher Use transitive closure to decide the "rank" of a symbol. Note that some message can be decrypted even if the completely substitution table cannot be determined.
718 Skyscraper Floors Linear diophantine equations and graph
753 A Plug for UNIX Transitive closure, maximum bipartite matching
762 We Ship Cheap BFS
784 Maze Exploration Flood fill
793 Network Connections Union-find
796 Critical Links Biconnected components
818 Cutting Chains Try all possible subsets of links to open, and see if the remaining links form a number of "line components". Make sure that there are enough open links to chain components together.
820 Internet Bandwidth Network flow
821 Page Hopping All pairs shortest path
869 Airline Comparison Compute transitive closure and compare.
872 Ordering Topological sort
908 Re-connecting Computer Sites Use Kruskal's algorithm, ignore the M edges.
925 No more prerequisites, please! Apply topological sort, and elminate indirect prerequisites one course at a time in the right order.
928 Eternal Truths BFS, represent states as (location, step mod 3).
929 Number Maze Dijkstra, but standard priority queue is not fast enough. Use the fact that the weights are < 10, and use 10 queues indexed by distance mod 10.
988 Many Paths, One Destination Use DFS
1060 Collecting Luggage Use binary search on time to check if we can reach the luggage at a particular time. To check that, construct a visibility graph.
10000 Longest Paths Use DFS
10004 Bicoloring DFS
10009 All Roads Lead Where? Find least common ancestor in a tree
10034 Freckles Minimum spanning tree
10047 The Monocycle BFS on a graph whose nodes are (location,direction,colour)
10048 Audiophobia Variation of Kruskal's algorithm
10054 The Necklace Euler tour
10075 Airlines Great circle, all pairs shortest path. Round every distance calculation (pairwise and during Floyd's algorithm) to nearest integer.
10080 Gopher II Maximum cardinality bipartite matching
10092 The Problem with the Problem Setter Transform this problem into a network flow problem.
10099 The Tourist Guide Use a variation of Kruskal's algorthm or Floyd's algorithm
10129 Play on Words If each letter is a vertex, we are looking for directed Eulerian paths/cycles.
10150 Doublets Breadth-first search, but how to construct the graph efficiently?
10171 Meeting Prof. Miguel... Shortest path, beware that there are self loops, and multiple roads connecting pairs
10199 Tourist Guide Find articulation points. Watch out for disconnected graphs: each component needs to be handled individually.
10203 Snow Clearing This directed graph is Eulerian.
10224 Return of the Jedi All the places to travel are either around the tree (circle) or a common tangent to two circles. Build a graph with the interesting points and compute shortest path.
10296 Jogging Trails Chinese Postman Problem
10301 Rings and Glue  
10305 Ordering Tasks Topological sort
10307 Killing Aliens in Borg Maze Compute distances between all pairs of interesting points, and compute the MST.
10308 Roads in the North Use two DFS.
10330 Power Transmission Network flow with both vertex and edge capacities.
10336 Rank the Languages Standard flood fill
10349 Antenna Placement If we overlay a checker board on the grid, adjacent cells have different colours. Form a bipartite graph with each side having the same colour, and add edges between adjacent points of interest. Then we want to find a maximum matching that so that each edge in the matching can be covered by one ellipse. The leftover points will have to be covered by themselves.
10369 Arctic Network Think about a variation of Kruskal's algorithm.
10397 Connect the Campus Variation of minimum spanning tree
10441 Catenyms Eulerian path/cycle.
10457 Magic Car If you fix the minimum speed, use binary search to search for the smallest maximum speed.
10480 Sabotage Use maximum flow algorithm. To find the cut, all vertices reachable from the source in the residual network are in one group, the rest are in the other. Ignore any vertices that do not receive any flow.
10511 Councilling Maximum flow
10557 XYZZY Use Bellman-Ford algorithm to find negative cycles.
10594 Data Flow Min cost max flow. Remember that the edges are bidirectional.
10596 Morning Walk Eulerian cycle detection.
10600 ACM Contest and Blackout Minimum spanning tree. To find the 2nd best tree, delete each of the edges in the MST and re-run the MST algorithm. The smallest such MST is the 2nd best tree.
10603 Fill Use Dijkstra's algorithm to explore the states.
10621 Jack and Jill The vertices are actually pairs consisting of the coordinates of Jack and Jill. Use priority-first search to explore from the start until the destination is reached.
10653 Bombs! NO they are Mines!! BFS
10661 The Perspectographer This is graph coloring. Try coloring the nodes in sequence, and for each one try all possible colors. It may help to look for the largest clique first.
10672 Marbles on a tree Do it with DFS
10681 Teobaldo's Trip Reachability in exactly k step is equivalent to the k-th matrix power (boolean "multiplication") of the adjacency matrix.
10702 Travelling Salesman The states are the end city of the trip so far and how many trips so far.
10720 Graph Construction Look up Erdos-Gallai theorem
10729 Treequivalence If you remember which node you come from as you traverse the tree, you can fix the orientation.
10731 Test Transitive closure
10746 Crime Wave - The Sequel Use the Hungarian algorithm to solve the minimum weighted bipartite matching problem. Beware of precision problems.
10801 Lift Hopping Dijkstra's algorithm on a graph whose nodes are (elevator,floor) pairs.
10803 Thunder Mountain Floyd's
10804 Gopher Strategy Combine binary search with bipartite matching.
10806 Dijkstra, Dijkstra. Set it up as a minimum cost maximum flow problem.
10816 Travel in Dessert Use Kruskal variation to find lowest temperature, then find shortest path.
10842 Traffic Flow Think about a modification of Kruskal's algorithm
10888 Warehouse This is minimum weight bipartite matching. Use the Hungarian algorithm.
10917 A Walk Through the Forest Use Dijkstra from the destination to determine which path can be taken. The subgraph is a DAG and you can use dynamic programming to compute the final answer.
10937 Blackbeard the Pirate  
10938 Flea circus  
10959 The Party, Part I shortest paths, use BFS
10983 Buy one, get the rest binary search for the minimum cost, and solve each instance with network flow (nodes are city-day pairs).
10986 Sending email Dijkstra algorithm
11015 05-2 Rendezvous Floyd's algorithm
11045 My T-shirt suits me Bipartite matching
11047 The Scrooge Co Problem Note that the cost from a location to itself may not always be 0, and even if the start and end locations are the same you still have to print at least two locations in the path.
11060 Beverages Topological sort
11080 Place the Guards Bicoloring. Beware that graph is not necessarily connected.
11094 Continents Connected components. Beware that the input can contain any two letters.
11101 Mall Mania This is BFS...how?
11110 Equidivision Connected components. Beware that some lines may not have n coordinates, and some coordinates may be repeated.
11138 Nuts and Bolts Bipartite matching
11159 Factors and Multiples Form a bipartite graph. Konig's theorem says that the minimum vertex cover has the same size as the maximum matching. Watch out for 0's in A and B.
11228 Transportation system Minimum spanning tree variation.
11262 Weird Fence Use binary search for the answer, and check with bipartite matching.
11280 Flying to Fredericton Use Bellman-Ford algorithm to compute the shortest distance with increasing number of stops.
11284 Shopping Trip There is a O(n^2 2^n) algorithm for travelling salesman where the states are (set of visited stores, last store to visit). Beware that there may be multiple edges between stores.
11288 Carpool For each subset of people, find the best solution. Recurse by removing a subset of up to 5 people.
11294 Wedding This is 2-SAT where each person is a variable and the value is true if the person sits on the same side as the bride.
11307 Alternative Arborescence Note that you may have to use more than two colours. The states in dynamic programming are the minimum sum for a tree rooted at i with colour j. Look up chromatic sums on trees to see that you do not need more than log_2(n) colours.
11324 The Largest Clique Look at strongly connected components and form a new directed graph with the SCC as the vertices
11331 The Joys of Farming 2-coloring + dynamic programming
11367 Full Tank? Dijkstra algorithm on graph whose nodes are (city,fuel)
11387 The 3-Regular Graph  
11396 Claw Decomposition The centres of the claws can be coloured in one way, while the ends can be coloured in another.
11405 Can U Win? Construct a graph between all passible cells, find all-pairs shortest distance, and try all permutations of enemy pawns.
11419 SAM I AM Form a bipartite graph and look for a minimum vertex cover. Apply Konig's theorem.
11439 Maximizing the ICPC Use binary search on the answer, ans use maximum matching to check.
11463 Commandos Find the vertex such that the distance from source to it and then to destination is greatest. That is the bottleneck.
11487 Gathering Food Use BFS on a graph whose nodes are (location,next food to gather). The number of paths to reach a certain point can be maintained while doing BFS.
11492 Babel Modified Dijkstra algorithm.
11504 Dominos Use a sparse representation of graph. Find strongly connected components and then use topological sort.
11506 Angry Programmer Max flow/min cut with vertex and edge capacities.
11518 Dominos 2 DFS
11550 Demanding Dilemma Make sure you check everything, including that the number of edges is really m.
11585 Nurikabe Connectivity checks
11586 Train Tracks Count MM and FF pieces.
11624 Fire! Use BFS from the fires to see how fast fire spread to each cell, then use BFS from Joe and use only those cells whose distance to fire is less than distance to Joe.
11631 Dark roads Minimum spanning tree.
11635 Hotel booking Use Dijkstra from each hotel (and the source/destination) to determine reachability between hotels, and then compute the shortest path in the reachability graph.
11684 MC part deux The triangles are nodes in a graph, and we want to do DFS from the root to extend the stakes that we know.
11685 Moveable maze Use BFS. The states are location, orientation of current square, and how many "free rotations" you have: the number of moves previously that skipped a rotation.
11686 Pick up sticks Use topological sort.
11695 Flight Planning Delete each edge in turn and compute the diameters of the two subgraphs. The best edge to add to connect the two subgraphs is to connect the centres.
11709 Trust groups Strongly connected components.
11721 Instant View of Big Bang First compute the strongly connected components. From each component, run Bellman-Ford algorithm to detect negative cycle in that component (it is sufficient to run it once per component). Then do a DFS on each node of the SCC tree to see which component we can start in.
11730 Number Transformation Use BFS to search.
11733 Airports Use Kruskal's algorithm
11745 Slitherlink  
11747 Heavy Cycle Edges Kruskal's algorithm
11748 Rigging Elections Use DFS to see if everyone else is beatable.
11749 Poor Trade Advisor Keep only edges of maximum weight.
11765 Component Placement Set this up as a minimum cut problem and then solve with maximum flow. The source and sink represent the top and bottom layer.
11770 Lighting Away Use topological sort on the strongly connected component graph
11813 Shopping Try all permutations, use Dijkstra's algorithm to compute shortest paths from/to each store.
11838 Come and Go Strongly connected components.
11857 Driving Range Modified Kruskal algorithm.
11902 Dominator Determine which vertices are reachable after a vertex is removed.
11930 Rectangles This is 2-SAT: if the two diagonals in a rectangle represent true and false assignments, then the choice of one diagonal implies that an intersecting diagonal cannot be chosen. Use a strongly connected component algorithm to solve 2-SAT.
11931 Maze Escape BFS on a state graph.
11953 Battleships Connected components
12295 Optimal Symmetric Paths "Fold" the grid along the antidiagonal and find the shortest path to the antidiagonal. Modify Dijkstra algorithm to also count the number of shortest paths.
12489 Combating cancer Find centres of the trees. Compute signatures for each tree using the centres as roots, and compare the signatures. Try to relabel the signatures to unique integers to speed things up.
12607 Amazing Maze BFS on state graph where a state remembers the location, the time (mod 4), and the subset of treasures collected so far.
12768 Inspired Procrastination Negate the edge weights and use Bellman-Ford to find the shortest path.

Greedy
NumberNameComments (highlight to reveal hints)
166 Making Change Use greedy to figure out the number of coins needed (with limited or infinite supply) for each amount, search through all the different ways of overpaying.
410 Station Balance The best way is to pair up the smallest with the largest, next smallest with next largest, etc. Insert dummy 0's to force S = 2*C.
1079 A Careful Approach Use binary search on the maximum gap. To test whether a gap is okay, try all possible landing order and then use a greedy approach to schedule the landing.
10020 Minimal coverage Start from the left end, find the segment that can cover the left end and extend furthest to the right. Repeat.
10037 Bridge What do you do with the two fastest people?
10249 The Grand Dinner You can assign each team to the tables with the most remaining seats, and repeat. You can also solve this by maximum flow.
10276 Hanoi Tower Troubles Again! For some reason you can always try to put in the leftmost possible peg.
10440 Ferry Loading II Find the best way to transport the first k cars for the DP approach. For the greedy approach, it is always best to take as many cars as possible for the last ferry.
10670 Work Reduction At each step decide which way is better
10954 Add All It is always best to add the next two smallest numbers. Why?
11157 Dynamic Frog Note that there is never any reason to use two consecutive small stones in the same direction, and big stones should be used whenever possible. Just keep a sorted list of stones with duplicated entries for the big stones. Look at the maximum distance between consecutive odd stones and the maximum distance between consecutive even stones. The two ends can be treated as big stones.
11240 Antimonotonicity Keep going as far down as possible, then going as far up as possible, etc.
11292 Dragon of Loowater For each dragon, it is good enough to find the shortest remaining knight that can kill it.
11389 The Bus Driver Problem It's best to match the shortest morning route with the longest afternoon route.
11583 Alien DNA Cut only when the segment no longer has any letter in common in all base sets.
11751 Installing Diagnostic Software Look at vertices from largest to smallest.
11900 Boiled Eggs You should always choose the lighter eggs.
12490 Integral For each interval you can find the minimum and maximum area achievable. Work forward and assign the smallest value possible so that the min and max area achievable from this point encloses the target. If f(0)+f(N) is odd then there is no solution.
12760 Arcurve's Big Project If you can finish the job without training anyone, just finish the job. Otherwise train people as early as you can.

Mathematics
NumberNameComments (highlight to reveal hints)
1026 The Solar System Work out the area swept, use binary search to look for the position.

Miscellaneous
NumberNameComments (highlight to reveal hints)
254 Towers of Hanoi Try to find the largest power of 2 less than n, and then move a whole stack of disks at the same time
679 Dropping Balls You can process each value of I in O(D) steps
711 Dividing Up I used integer programmingi to solve this. Apparently it can be solved with 0-1 knapsack with some clever reductions.
956 The Minimum Slot Machine Finite state automata minimization.
10666 The Eurocup is Here! Look at the bit pattern of the numbers
11012 Cosmic Cabbages Note that the expression for Mahattan distance has 3 absolute values. There are 8 different ways to assign signs to each of the absolute values. For each way, you can find the optimal value in linear time.
11134 Fabled Rooks Look at row and column independently, use a greedy algorithm for each.
11235 Frequent Values One way to do it is to preprocess the data by dividing it into sqrt(n) chunks of size sqrt(n). For each query we only need to do O(sqrt(n)) work. It is not the fastest method, but it is fast enough here. You can also build a binary tree and divide each segement into two halves at each step. Finally, you can also use RMQ if you convert each entry into the count of the entry.

Number Theory
NumberNameComments (highlight to reveal hints)
106 Fermat vs Pythagoras Pythagorean Triples
160 Factors and Factorials  
294 Divisors Use a sieve approach
374 Big Mod Remember to reduce mod m as soon as possible.
382 Perfection  
406 Prime Cut Primality testing: 1 is prime for this problem!
408 Uniform Generator Use GCD somehow
516 Prime Land  
543 Goldbach's Conjecture primality testing
568 Just the Facts Look at prime factorization of N!
583 Prime Factors Standard integer factorization
686 Goldbach's Conjecture (II) Just brute force
718 Skyscraper Floors Linear diophantine equations and graph
756 Biorhythms You can just search for it. But the smarter way is to use the Chinese Remainder Theorem
834 Continued Fractions Use the Euclidean algorithm.
884 Factorial Factors  
967 Circular Use cumulative sums to speed up the search.
10006 Carmichael Numbers Look up properties of these numbers
10042 Smith Numbers  
10090 Marbles It's a linear diophantine equation. Use extended Euclidean algorithm.
10104 Euclid Problem Extended Euclidean algorithm
10110 Light, more light Count number of factors (odd/even)...or pefect squares
10127 Ones Look at the values of 11...1 mod n. How many different ones can there be?
10139 Factovisors Look at the prime factorization of both sides
10140 Prime Distance Generate all primes under a threshold (e.g. 1000000) with a sieve, and then use another sieve to find the primes in range.
10162 Last Digit The sequence i^i mod 10 cycles after a while, so does the sum of them.
10168 Summation of Four Primes Make use of Goldbach's conjecture: every even number greater than or equal to four can be written as a sum of two primes.
10179 Irreducible Basic Fractions Euler phi function
10193 All You Need Is Love It's just a GCD calculation.
10200 Prime Time Basic primality test.
10212 The Last Non-zero Digit. Make use of the formula to compute the number of times a prime divides into factorials, and handle primes 2 and 5 separately.
10225 Discrete Logging Consider L in base "sqrt(P)". Search for the two digits sequentially with a meet-in-the-middle strategy.|
10235 Simply Emirp  
10299 Relatives Euler phi function
10311 Goldbach and Euler Use a sieve to generate a list of primes, and then check.
10392 Factoring Large Numbers Trial division should be fast enough.
10394 Twin Primes Use a seive
10407 Simple division Consider the differences
10408 Farey sequences Knuth v. 1 1.3.2 exercises 18 and 19 (or do brute force search)
10490 Mr. Azad and his Son!!!!! Look at the formula and determine its divisors.
10515 Power et al. We only need to work on the last digit, and we can process one digit of n at a time.
10533 Digit Primes Generate a list of digit primes by brute force, and use binary search on this list.
10539 Almost Prime Number Generate a list of all prime powers by brute force, then use binary search on this list.
10606 Opening Doors What does this have to do with perfect squares?
10622 Perfect P-th Powers Factor and look at the gcd of exponents. Watch out for negative numbers!
10673 Play with Floor and Ceil Linear Diophantine equation
10680 LCM Look at prime powers
10692 Huge Mod Look up Euler phi function. Watch out for bases that are not relatively prime to the modulus. Can also do it by brute force.
10699 Count the factors  
10717 Mint Look at the LCMs
10738 Riemann vs Mertens Use a sieve to compute mu(N) for all N.
10789 Prime Frequency  
10820 Send a Table Use the Euler Phi function
10852 Less Prime  
10856 Recover Factorial Use a sieve to count factors, and then binary search.
10871 Primed Subsequence Use a sieve for primality checking for "small enough" numbers. Large numbers have to be checked by trial division. Check all subsequences in O(n^2) time.
10879 Code Refactoring Just factor
10892 LCM Cardinality Prime factorization
10924 Prime Words Beware: according to their definition, 1 is prime.
10948 The primary problem  
11064 Number Theory Look at prime factorization
11312 Flipping Frustration Solve the linear diophantine equation. But there are some more constraints.|
11327 Enumerating Rational Numbers Use the Euler Phi function to figure out how many fractions there are with a certain denominator. How do you use this information?
11347 Multifactorials Count the number of times each prime divides into the multifactorials. This can be done by brute force.
11388 GCD LCM  
11408 Count DePrimes Use a sieve and count the number of DePrimes from 2 to k.
11424 GCD - Extreme (I) Express the difference between successive terms as a sum of euler phi's, and compute that quickly with a sieve.
11426 GCD - Extreme (II) Similar to 11424, but precompute G[n] at regular intervals (hardcoded) and sum from there.
11466 Largest Prime Divisor Use a sieve to generate all primes up to 10 million to help speed up factoring. Beware that input may have negative integers.
11476 Factoring Large Integers Use Millar-Rabin primality test and Pollard's rho factoring algorithm
11610 Reverse Prime Use a sieve to generate the primes, and then use two Fenwick trees to keep track of the cumulative sums (divisors and count) in the range.
11728 Alternate Task Brute force is sufficient here since we do not have to consider integers >= 1000.
11730 Number Transformation Use BFS to search.
11768 Lattice Point or Not Express the points in y = m*x+b. They must be divisible by 10.
11827 Maximum GCD  
11889 Benefit Look at the prime factorization.
11916 Emoogle Grid If there are no blocked cells, the problem reduces to a discrete log problem. This can be extended to the case of blocked cells as well.
12493 Stars Use the Euler Phi function.

Parsing
NumberNameComments (highlight to reveal hints)
134 Loglan-A Logical Language  
171 Car Trialling  
198 Peter's Calculator  
271 Simply Syntax Recursion and even dynamic programming is too slow. Try working from the end and count the number of correct sentences from the end.
293 Bits The only trick is that tokens may be separated by any number of whitespace characters, including 0.
384 Slurpys  
442 Matrix Chain Multiplication  
533 Equation Solver  
622 Grammar Evaluation Standard infix parsing
673 Parentheses Balance  
727 Equation Standard infix to postfix conversion
10058 Jimmi's Riddles Standard recursive parsing.
10442 Basic Simple base conversion and checking, but remember that the base can itself be specified in the alternate format.
11070 The Good Old Times  
11117 Little Quilt  
11808 Ensuring Victory  
12606 Evaluating Logic Expressions Standard parsing with a non-standard evaluation function

Permutations
NumberNameComments (highlight to reveal hints)
146 ID Codes Next permutation
299 Train Swapping Look up "inversions"
306 Cipher Look at how each element gets permuted in n steps. There will be a cycle. Use modular arithmetic to reduce. (K can be large.)
10730 Antiarithmetic? Consider the inverse of the permutation. Can be done in about n^2/4 time

Probability
NumberNameComments (highlight to reveal hints)
542 France '98 For each team, compute the probability of it reaching round j.
557 Burger It's probably easier to compute the complement of the event.
10056 What is the Probability Geometric distribution
10491 Cows and Cars  
10900 So you want to be a 2^n-aire? Look for a recurrence.
11176 Winning Streak Build a table of the probability of playing n games and having winning streak no longer than k games. Find a recursion that considers a winning streak of various lengths in the first few games.
11181 Probability/Given Compute the probability of all possible subsets, and divide that into the probability of all possible subsets with each shopper chosen.
11762 Race to 1  
12487 Midnight Cowboy Only nodes on the path from B to C matters (assuming A is on that path). For each node on the path, compute the probability of heading toward a hotel and the probability of heading back toward A. Combine these at each node with a geometric series.

Recursion
NumberNameComments (highlight to reveal hints)
110 Meta-Loopless Sorts  
112 Tree Summing  
122 Trees on the level  
155 All Squares  
183 Bit Maps  
297 Quadtrees Expand the image and count. Could be faster if we process the trees without expanding unnecessarily, but the images are small enough
384 Slurpys  
536 Tree Recovery  
606 Keeps Going and Going and ... Detect cycles not involving zips to reduce the indices
620 Cellular Structure  
621 Secret Research  
699 The Falling Leaves  
712 S-Trees Basically a binary search.
729 The Hamming Distance Problem Just generate all N choose H combinations.
752 Unscrambling Images Use the test image to give an inverse mapping
806 Spatial Structures  
839 Not so Mobile Process recursively.
10098 Generating Fast, Sorted Permutation Standard problem
10245 The Closest Pair Problem Standard divide and conquer problem.
10562 Undraw the Trees  
10609 Fractal  
10669 Three Powers Find the largest element first, need big numbers
10701 Pre, in and post Same as 536
10810 Ultra-QuickSort Count inversions quickly by modifying merge sort. Watch for overflow.
10821 Constructing BST Find the smallest number that can be the root, and recurse.
10854 Number of Paths Parse the program and count the leaves in the parse tree. Beware of "independent units".
11129 An antiarithmetic permutation Work on the odd and even numbers separately and combine
11131 Close Relatives You can do it with at most two lists
11297 Census Build a quadtree.
11688 Rotate to root This can be done in one DFS pass by first computing the heights of the subtrees rooted at each node. As you traverse to a node, remember how many left and right rotations needed to be done to propagate that node to the rooot, as well as the heights of all other branches not on this path.
12487 Midnight Cowboy Only nodes on the path from B to C matters (assuming A is on that path). For each node on the path, compute the probability of heading toward a hotel and the probability of heading back toward A. Combine these at each node with a geometric series.
12489 Combating cancer Find centres of the trees. Compute signatures for each tree using the centres as roots, and compare the signatures. Try to relabel the signatures to unique integers to speed things up.
12627 Erratic Expansion Look at what happens in the top half and the bottom half, use memoization to speed things up.

Search
NumberNameComments (highlight to reveal hints)
102 Ecological Bin Packing Small search space
124 Following Orders Try all permutations
138 Street Numbers Precomputation (can also be done quickly online)
140 Bandwidth  
152 Tree's a Crowd Just brute force
154 Recycling  
167 The Sultan's Successors Just check all possible permutations (indicating the column position for each row)
195 Anagram Generate all permutations
216 Getting in Line Try all permutations
253 Cube painting Figure out how to do the rotations
291 The House of Santa Claus  
295 Fatman Use binary search, and expand the obstacles to see if a point can pass through.
296 Safebreaker Just try all possibilities and check
305 Joseph You can precompute the answers offline.
386 Perfect Cubes Just brute force
387 A Puzzling Problem  
435 Block Voting Look at all majority subsets and remove members
455 Periodic Strings  
524 Prime Ring Problem Try all permutations on a circle with early cut-off.
560 Magic Do a priority-first search with a priority queue, until we get the first non-offending number.
571 Jugs BFS on a graph of vertices of the form (A,B)
608 Counterfeit Dollar There are only 24 possibilities.
609 Metal Cutting Try all permutation of cuts
616 Coconuts, Revisited Use the fact that if there are n people then the number of coconuts at the beginning must be at least n^n-n+1 to obtain a small range of n to search for.
639 Don't Get Rooked There are not that many possibilities.
714 Copying Books Do binary search on the time, and then use greedy algorithm to see if the time is possible.
725 Division Try all denominators and look for corresponding numerators
750 8 Queens Chess Problem Try all permutations
811 The Fortified Forest Try all possible subsets, and see if the convex hull of the remaining trees can be surrounded.
817 According to Bartjens Try all possible ways of inserting operators and check each one.
818 Cutting Chains Try all possible subsets of links to open, and see if the remaining links form a number of "line components". Make sure that there are enough open links to chain components together.
850 Crypt Kicker II  
1026 The Solar System Work out the area swept, use binary search to look for the position.
1060 Collecting Luggage Use binary search on time to check if we can reach the luggage at a particular time. To check that, construct a visibility graph.
1061 Consanguine Calculation Just try all possible allele combinations.
1079 A Careful Approach Use binary search on the maximum gap. To test whether a gap is okay, try all possible landing order and then use a greedy approach to schedule the landing.
1080 My Bad Just try all possible gate & error combinations and see if there is a unique one consistent with observations.
10012 How Big Is It? Try all possible permutations, and don't forget to check that the circle doesn't overlap with every circle (not just the previous one)
10067 Playing with Wheels Use BFS
10132 File Fragmentation There should not be that many possibilities.
10181 15-Puzzle Problem Use A* search, and use the heuristic function being the sum of the manhattan distances of each tile to its resting place.
10298 Power Strings Try all possible exponents: they must divide the length
10341 Solve It The function is strictly decreasing in the interval...use bisection.
10344 23 out of 5 Just brute force
10360 Rat Attack Note that the sum of population in a square can be computed in constant time if you have computed the cumulative sum of the rectangle from (0,0) to (x,y) for all (x,y).
10364 Square An approach similar to 307 can be used to prune the search space. Or we can use dynamic programming where the states are the subset of sticks left and how many sides are left.
10365 Blocks  
10487 Closest Sums Use binary search
10582 ASCII Labyrinth  
10611 The Playboy Chimp Use binary search
10660 Citizen attention offices Just try all possible 25 choose 5 ways of placing the offices.
10671 Grid Speed At each intersection and time, remember the best fuel consumption. Need pruning and optimization to get it fast enough.
10706 Number Sequence Build a table containing the number of digits up to Sk, and search in this table.
10911 Forming Quiz Teams Try all possible matching
10941 Word adjustment We only have to worry about what is "sticking out", and there are not too many possible strings that can stick out.
10976 Fractions Again?! Just search for x and solve for y.
11048 Automatic Correction of Misspellings Look at the lengths to reduce the number of tests to do.
11085 Back to the 8-Queens Just generate all possible solutions to the 8-queens problem and compare.
11163 Jaguar King This is similar to a 15-puzzle in which the king is the blank, and the board is 4 x (N/4). Solve it using iterative deepening A* search.
11212 Editing a Book Note that we only have to consider moving a chunk of text forward, because moving backward is equivalent to another chunk moving forward. Do a bidirectional search: run BFS from the goal backwards for a few steps to build up a list of possible configurations from the goal. Then search forward from the initial state until one of these configurations is found in the list.
11218 KTV  
11270 Tiling Dominoes Perhaps precomputation is the way to go?
11283 Playing Boggle  
11325 This Means War! Do you know how to do it if you know when the ties are? Now try all the different "schedules" for ties.
11329 Curious Fleas Do a BFS. The only trick is the representation of the states
11405 Can U Win? Construct a graph between all passible cells, find all-pairs shortest distance, and try all permutations of enemy pawns.
11413 Fill the Containers Use binary search on the maximum container size, and use a greedy algorithm to see if a certain size works.
11428 Cubes Search for y until sqrt(N) (see factorization of x^3-y^3.
11439 Maximizing the ICPC Use binary search on the answer, ans use maximum matching to check.
11501 Laurel Creek Use BFS on a graph of states. Each state specifies the current configuration of the logs, the location of the person, and the log (if any) being carried.
11515 Cranes Just try all possible 2^15 subsets to see what is possible.
11516 WiFi Given a maximum distance allowed, we can determine whether it is possible to satisfy the distance with the number of access points with a greedy algorithm. Do binary search on the maximum distance allowed.
11548 Blackboard Bonanza Just try all pairs of strings and all possible offsets.
11553 Grid Game You only have to decide which column Bob is going to cross out for each row. Notice that Alice's sequence of choices do not really matter, since Bob can rearrange his choices to arrive at the same outcome.
11576 Scrolling Sign Just search to find the longest suffix of the previous word that matches the prefix of the current word.
11728 Alternate Task Brute force is sufficient here since we do not have to consider integers >= 1000.
11742 Social Constraints  
11761 Super Heronian Triangle Use the fact that 4*A*R = a*b*c to search quickly for possible side lengths. Look at the prime factorization.
11804 Argentina Just try all combinations.
11809 Floating-Point Numbers Try all possible values of M and E, and compare the values after logarithm is taken. Take the one that gives the closest logarithm.
12247 Jollo Try all possible cards, and for each card, try all possible ways of playing
12291 Polyomino Composer The upperleft squares must correspond to each other.
12326 Yummy Triangular Pizza Try all possible tiling, or cheat with the online encyclopedia of integer sequence A006534.
12491 Words Use BFS on a graph which indicates the current suffix (and which set it came from) that is "sticking out". There are not that many possible nodes.
12636 Disguised Giveaway Very similar to "Pairsumonious Numbers".

Simulation
NumberNameComments (highlight to reveal hints)
100 The 3n+1 problem  
101 The Blocks Problem  
114 Simulation Wizardry  
118 Mutant Flatworld Explorers  
127 "Accordian" Patience  
130 Roman Roulette Josephus variation
133 The Dole Queue Josephus variation
139 Telephone Tangles Make sure you check all the rules, and put extra spaces in each field (more than what they indicate)
141 The Spot Game  
142 Mouse Clicks  
144 Student Grants  
145 Gondwanaland Telecom  
151 Power Crisis Josephus variation
161 Traffic Lights  
162 Beggar My Neighbour  
168 Theseus and the Minotaur  
170 Clock Patience  
178 Shuffling Patience  
187 Transaction Processing  
196 Spreadsheet Evaluate recursively if needed
227 Puzzle Watch out for invalid commands
239 Tempus et mobilius. Time and motion Simulate for 12 hours and study the resulting permutation with cycle decomposition.
246 10-20-30 The only trick is to determine a draw...
337 Interpreting Control Sequences  
403 Postscript Just do it.
467 Synching Signals Similar to 161
517 Word  
556 Amazing  
570 Stats  
573 The Snail  
584 Bowling  
611 Parallel Deadlock  
637 Booklet Printing  
661 Blowing Fuses  
694 The Collatz Sequence  
700 Date Bugs  
706 LC-Display  
741 Burrows Wheeler Decoder  
758 The Same Game Just do it
804 Petri Net Simulation  
978 Lemmings Battle! Use a priority queue to keep track of each team.
1066 Water Tanks Work from left to right. Figure out how much water is needed in each tank to balance the pressure from previous tank.
10015 Joseph's Cousin Precompute the answers.
10033 Interpreter  
10050 Hartals  
10114 Loansome Car Buyer Watch out for the "0 months" case.
10116 Robot Motion  
10142 Australian Voting  
10172 The Lonesome Cargo Distributor  
10194 Football (aka Soccer)  
10205 Stack 'em Up  
10258 Contest Scoreboard  
10377 Maze Traversal  
10409 Die Game  
10443 Rock, Scissors, Paper  
10507 Waking up brain  
10552 Genealogical Research  
10587 Mayor's posters Process the posters backward
10588 Queueing at the doctors  
10646 What is the Card?  
10813 Traditional BINGO  
10901 Ferry Loading III  
10939 Ants, Aphids and a Ladybug  
11034 Ferry Loading IV  
11053 Flavius Josephus Reloaded Simulate until you find a cycle.
11079 What's the Time? Simulate it for 2 * LCM of the periods. Then try to figure out how many periods it takes and search in the last one.
11136 Hoax or what  
11459 Snakes and Ladders  
11505 Logo  
11507 Bender B. Rodriguez Problem Just work out all the cases.
11634 Generate random numbers  
11687 Digits  
11831 Sticker Collector Robot  
12290 Counting Game Just do it. It cannot go on for more than 80000 steps.
12492 Rubik Cycle Look at each cell individually, and it must cycle back to the original spot in at most 48 moves. The answer is the LCM of the cycle lengths of each cell.
12608 Garbage Collection  

Sorting
NumberNameComments (highlight to reveal hints)
123 Searching Quickly  
612 DNA Sorting  
755 487-3279 You may want to represent the phone numbers as ints.
837 Light and Transparencies Sort the end points and process
855 Lunch in Grid City Compute the median. Watch out when the number of points is even.
10026 Shoemaker's Problem Sorting by ratios (of what?)
10041 Vito's family Median
10152 ShellSort  
10327 Flip Sort Just count inversions.
10474 Where is the Marble? Use radix sorting
10508 Word Morphing Look at the Hamming distance of an intermediate word from the start.
10763 Foreign Exchange Represent the graph as a list of pairs.
10905 Children's Game  
11057 Exact Sum  
11369 Shopaholic  
11495 Bubbles and Buckets Use a mergesort like algorithm to count inversions
11849 CD Do a merge-sort like marching algorithm to count.
11858 Frosh Week Divide-and-conquer like merge sort to count inversions.
11925 Generating Permutations This is basically bubble sort.
11991 Easy Problem from Rujia Liu? Represent each element as (value, index), sort the pairs, and work from there.
12488 Start Grid Look for inversions.

Straightforward
NumberNameComments (highlight to reveal hints)
105 The Skyline Problem Scanning possible coordinates
119 Greedy Gift Givers  
120 Stacks of Flapjacks  
126 The Errant Physicist Polynomial
131 The Psychic Poker Player Tedious
150 Double Time Just count the days carefully
156 Ananagrams  
158 Calendar  
159 Word Crosses  
169 Xenosemantics  
175 Keywords  
188 Perfect Hash  
201 Squares  
209 Triangular Vertices  
213 Message Decoding  
232 Crossword Answers  
245 Uncompress  
263 Number Chains  
272 TeX Quotes  
277 Cabinets  
278 Chess No need to search: there are closed form formulas for all cases.
311 Packets Tedious...just try to pack the largest ones first and analyze it one case at a time.
320 Border  
325 Identifying Legal Pascal Real Constants  
326 Extrapolation Using a Difference Table Keep only the last row
333 Recognizing Good ISBNs  
340 Master-Mind Hints  
344 Roman Digititis  
350 Pseudo-Random Numbers  
353 Pesky Palindromes  
371 Ackermann Functions  
392 Polynomial Showdown  
394 Mapmaker  
400 Unix ls  
401 Palindromes It is easier to reverse and/or mirror the string and then compare.
409 Excuses, Excuses!  
412 Pi  
413 Up and Down Sequences Note: they want as "length" the number of transitions in the sequence instead of the number of elements.
414 Machined Surfaces  
416 LED Test  
417 Word Index Just generate all of them by brute force.
422 Word-Search Wonder  
440 Eeny Meeny Moo Josephus variation
444 Encoder and Decoder Watch out for reversing numbers with trailing 0's
445 Marvelous Mazes  
448 OOPS!  
450 Little Black Book  
458 The Decoder  
462 Bridge Hand Evaluator  
466 Mirror,Mirror  
482 Permutation Arrays  
483 Word Scramble  
486 English-Number Translator Be careful about phrases like "one hundred thousand"
488 Triangle Wave Despite what the problem statement says, print a new line even after the last wave.
489 Hangman Judge  
490 Rotating Sentences Watch out for sentences of different lengths.
492 Pig-Latin  
494 Kindergarten Counting Game  
498 Polly the Polynomial  
499 What's the Frequency, Kenneth?  
514 Rails At each step either push one on the stack or pop one on the stack. It should be easy to figure out which one or when we get stuck.
537 Artificial Intelligence  
541 Error Correction  
551 Nesting a Bunch of Bracket  
554 Caesar Cypher Watch out for trailing spaces...remove them to get accepted rather than presentation error.
555 Bridge Hands  
576 Haiku Review  
581 Word Search Wonder You may want to remember the starting locations for every letter so you don't have to search through everything.
591 Box of Bricks Just figure out the difference between the original and desired state for each stack.
613 Numbers That Count  
628 Passwords  
630 Anagrams (II)  
640 Self Numbers  
641 Do the Untwist  
642 Word Amalgamation Standard anagram problem, compute a signature based on character counts (or sort characters)
644 Immediate Decodability brute force is fast enough
696 How Many Knights There are closed form formulas. Watch out for cases with fewer than 3 rows/columns.
713 Adding Reversed Numbers  
739 Soundex Indexing  
740 Baudot Data Communication Code  
756 Biorhythms You can just search for it. But the smarter way is to use the Chinese Remainder Theorem
803 Page Selection By Keyword Matching The online judge is wrong! It accepts only programs that produce no output.
815 Flooded! Watch out for the case when everything is under water.
856 The Vigenere Cipher  
895 Word Problem  
902 Password Search  
957 Popes Scan through while maintaining a range of Y years.
10008 What's Cryptanalysis?  
10010 Where's Waldorf  
10013 Super long sums  
10019 Funny Encryption Method  
10038 Jolly Jumpers  
10055 Hashmat the brave warrior Can it be any easier?
10062 Tell me the frequencies!  
10071 Back to High School Physics Area under a curve
10077 The Stern-Brocot Number System  
10082 WERTYU  
10101 Bangla Numbers  
10102 The path in the colored field  
10115 Automatic Editing  
10141 Request for Proposal  
10188 Automated Judge Script  
10189 Minesweeper  
10191 Longest Nap It's probably easiest to have a bitmap of whether each minute is busy or not.
10196 Check the Check  
10222 Decode the Mad man  
10226 Hardwood Species  
10227 Forests  
10252 Common Permutation Watch out for blank lines
10260 Soundex  
10267 Graphical Editor Floodfill and other stuff
10281 Average Speed  
10284 Chessboard in FEN  
10293 Word Length and Frequency  
10295 Hay Points  
10300 Ecological Premium  
10302 Summation of Polynomials  
10315 Poker Hands  
10361 Automatic Poetry  
10363 Tic Tac Toe You can either do some analysis, or generate all possible games and search in the list.
10370 Above Average  
10393 The One-Handed Typist  
10415 Eb Alto Saxophone Player Shift the complexity to data
10424 Love Calculator  
10452 Marcus, help!  
10469 To Carry or not to Carry What bit operation is equivalent to addition with carry?
10509 R U Kidding Mr. Feynman!  
10528 Major Scales  
10530 Guessing Game  
10550 Combination Lock  
10554 Calories from Fat  
10584 Text Formalization  
10656 Maximum Sum (II) Watch out for all 0's
10696 f91  
10703 Free spots Just brute force
10714 Ants  
10783 Odd Sum  
10800 Not That Kind of Graph Be careful that there can be more Fs than Rs.
10851 2D Hieroglyphs decoder  
10878 Decode the tape  
10894 Save Hridoy Use the sample output for copy and pasting to make life easier.
10896 Known Plaintext Attack  
10903 Rock-Paper-Scissors Tournament  
10919 Prerequisites?  
10921 Find the Telephone  
10922 2 the 9s  
10928 My Dear Neighbours  
10935 Throwing cards away I  
10942 Can of Beans  
10945 Mother Bear  
10946 You want what filled? Connectivity is defined in the four directions, not 8.
10963 The Swallowing Ground Just watch out for y1 < y2. In those cases say "no".
10970 Big Chocolate  
11044 Searching for Nessy  
11056 Formula 1  
11063 B2-Sequence  
11078 Open Credit System  
11100 The Trip, 2007 Figure out the number of chains first
11121 Base -2 Be careful with negative numbers
11132 Dice from pennies  
11172 Relational Operator  
11192 Group Reverse  
11203 Can you decide it for ME? How is this related to addition of integers?
11205 The Broken Pedometer  
11220 Decoding the message  
11221 Magic square palindromes  
11222 Only I did it!  
11223 O: dah dah dah!  
11230 Annoying painting tool  
11233 Deli Deli  
11242 Tour de France  
11244 Counting Stars  
11286 Conformity  
11308 Bankrupt Banker  
11309 Counting Chaos  
11332 Summing Digits  
11340 Newspaper Watch out for overflow, and space as a paid character
11364 Parking  
11385 Da Vinci Code Watch out when the string is longer than the code.
11452 Dancing the Cheeky-Cheeky  
11455 Behold my quadrangle  
11461 Square Numbers Build a table of number of squares from 0 to n
11462 Age Sort Use radix sort
11470 Square Sums  
11498 Division of Nlogonia  
11508 Life on Mars?  
11530 SMS Typing  
11541 Decoding  
11547 Automatic Answer  
11559 Event Planning  
11577 Letter Frequency  
11581 Grid Successors It is asking you to generate a sequence of grids and see when the cycle starts.
11588 Image Coding  
11629 Ballot evaluation  
11727 Cost Cutting  
11743 Credit Check  
11744 Parallel Carry Adder  
11764 Jumping Mario  
11799 Horror Dash  
11816 HST Watch out for overflow.
11850 Alaska  
11852 Knight's Trip There is a formula for this.
11854 Egypt  
11875 Brick Game  
11878 Homework Checker  
11926 Multitasking Just use a bit map, but stop checking as soon as there is a conflict.
11933 Splitting Numbers  
11934 Magic Formula  
11935 Through the Desert  
11988 Broken Keyboard (a.k.a. Beiju Text) Use a list of characters.
12085 Mobile Casanova  
12250 Language Detection Just do it
12289 One-Two-Three  
12345 Dynamic len(set(a[L:R])) There is only one case and a high time limit, so O(nm) algorithm is sufficient. Use a boolean array to keep track of which numbers appear in the range being queried, and try to initialize it only once for all queries.
12482 Short Story Competition  
12605 Ripple Effect Just follow the rules.
12764 Exercising Emoticons  

String
NumberNameComments (highlight to reveal hints)
129 Krypton Factor  
454 Anagrams Just compute a signature for each string and compare every pair.
719 Glass Beads Use a suffix array
760 DNA Sequencing You can use dynamic programming or suffix arrays to get the longest common substring.
1223 Editor Use a suffix array to find longest repeated substring.
1227 The longest constant gene Use a suffix array on the concatenated string (with separators), and look at a "sliding window" on the suffix array that includes all the original strings and take the minimum of LCP values. You will need to have a data structure to maintain a queue (for the window) of values and be able to take the minimum easily.
1254 Top 10 Use a suffix array. It's too slow to sort the output with the specified criteria each time. It's faster to sort the dictionary first, and then only sort the indices for each query.
10340 All in All  
10526 Intellectual Property Use a suffix array.
10679 I love Strings !!! Use a suffix array
10716 Evil Straw Warts Live Do it greedily from outside in
11048 Automatic Correction of Misspellings Look at the lengths to reduce the number of tests to do.
11107 Life Forms Use a suffix array
11475 Extend to Palindrome Take the reverse of the string, and search for the longest prefix of the reverse that appears as a suffix of the original string. The KMP string searching algorithm can be modified to do this in O(n) time.
11512 GATTACA Use a suffix array
11837 Musical Plagiarism Look at "strings" of differences, and then do a fast string matching algorithm.
11855 Buzzwords You can look at all pairs of substrings with hashing, or you can use a suffix array.
12604 Caesar Cipher Compute the differences between each character if you want to avoid trying all shifts. Use KMP to find substrings.