Number | Name | Comments (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. |
Number | Name | Comments (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 |
Number | Name | Comments (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 |
Number | Name | Comments (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. |
Number | Name | Comments (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. |
Number | Name | Comments (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. |
Number | Name | Comments (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. |
Number | Name | Comments (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. |
Number | Name | Comments (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. |
Number | Name | Comments (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. |
Number | Name | Comments (highlight to reveal hints) |
---|---|---|
1026 | The Solar System | Work out the area swept, use binary search to look for the position. |
Number | Name | Comments (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 | Name | Comments (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. |
Number | Name | Comments (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 |
Number | Name | Comments (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 |
Number | Name | Comments (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. |
Number | Name | Comments (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. |
Number | Name | Comments (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". |
Number | Name | Comments (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 |
Number | Name | Comments (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. |
Number | Name | Comments (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 |
Number | Name | Comments (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. |