ACM Programming Competition Tricks

<=
 
  1. Numbers That Don't Change
  2. Redundancy Checking
  3. Metric Spaces
  4. Unlimited, Non-Decreasing Metric Spaces
  5. Sorting Algorithms
 

Please note, your mileage may vary.

First of all, this goal isn't about teaching you how to write three lines of java in one line of perl. These are just tips to try and help you characterise the problem better so that you can use a simplier solution. Before you read any tricks you should already know the basics - you must know what a depth-first search is, that in a minimisation problem you can use Integer.MAX_VALUE as a seed (and vice versa for maximisation and Integer.MIN_VALUE), etc... These tricks are really nothing more than 'reminders' for the reader in case, in the heady heat of the moment, you forget about those simple choices that actually make things go faster (as opposed to the 'cosmetic' ones that don't change a thing).

By the way, you also need to know what 'pruning' means, and that the sooner you do it the better! As my debating teacher used to say: "Prune Trunks, Not Branches".


Trick 1 - Numbers That Don't Change (a.k.a. Offline vs Online).

Many questions involve some mathematical calculation that does not actually change based on the input. For example, calculating the 'crossover' values in 2002-Q2 was something that you would probably need to work out the function for caculating them, but didn't need to run that function in the actual test. Alternatively, you might be given a set of problems but with some global parameters for the whole file which you can calculate just once. Remember, every line you can get out of the loop is one-line closer to getting rid of the loop!


Trick 2 - Redundancy Checking (a.k.a. List The People That Work For Bob).

This is a HashMap technique for searching problems. Many problems require you to accumulate a history of some set of objects and keep a count of how many you have seen (such as, 'a person may not vote for the same candidate twice'). In this case, the first impulse is to create a n^2 loop - for each element in the list check to see if it is in the list again. Some problems may also prohibit you from sorting, otherwise you could sort the list and shave some time from that number, but the reality is you are wasting time! Remember, a HashMap has both an O(1) 'add' and an O(1) search! For example, in 2003-heat1-Q1 a person's vote is disqualified if they voted for the same candidate more than once. Rather than have a n^2 (admittidly small) loop, we use a HashMap and ask whether or not that vote has already appeared. In 2002-Q4 we have to keep track of which employees work for each other, but we are *not* given the employees in order! In this case, we can sort 'as we go' using a HashMap, rather than having to read them all in, sort them, then work out the employment tree!


Trick 3 - Metric Spaces (a.k.a. If It Doesn't Matter Who Wins Why Do We Keep Score).

This is a pruning technique for searching problems. This is a HashMap technique for searching problems. What the heck is a metric space? Well, mathematically it basically refers to any set of objects for which you can tell the 'distance' between any two objects, d(x,y), and for which the 'triangle inequality' holds, d(x,z) <= d(x,y) + d(y,z). In problem solving, it generally refers to the fact that there is some way to assign a 'number'* to each solution so that you can ask the question: 'is solution A as good as solution B'? Typically this takes the form of money or distance, but it applies to any problem where you can work out a 'score'. This is a good thing, since it tends to imply that you can compare two solutions simply by comparing their score rather than having to perform an n-degree piece by piece test. It also tends to mean (but not always) that two partial solutions from different choices that have the same score are generally equally valid (and so you tend to throw one away ;). If this is the case, you can prune your space by storing each partial solution in a HashMap, indexed by its score. That way, when you come across another solution with the same score, you can decide to 'throw' one away and more importantly, if the two solutions are equally branching**, you don't need to search beyond the second one because you will get the same results as from the first. Even better, as in 2003-heat1-Q3, you often just throw the second copy away since having 'found' it later it will probably be 'longer' and so not a better solution.

By the way, if this sounds familiar, it's because it is! This is the long description of when you can use the A* pruning technique (don't follow a branch that will give you the same answers as a branch you have already followed).

* :: I used the term 'number' as a general notion of anything which is discrete and partially ordered. If the score is *any* discrete quantity this works, so integers, characters, strings (and doubles on a computer ;) can all be used for a metric space test. In fact, any hashCode object can be used to eliminate any identically-scoring equally-branching** solutions. Notice that this means if you can produce a unique string representation for your object then you can simply use that String to hash your sample space.

** :: What the heck is 'equally-branching', 'generation' or 'length'? Basically, when you are comparing two partial solutions you need to be sure that they represent the same set of possible final solutions. This means that they have to all be able to make the same choices in the future, otherwise one of the solutions could suddenly change direction (and get *worse*). a good way to think about it is an algorithm for trying to escape from a desert in the smallest possible moves. Two solutions with the score '2 moves' are *not* equally branching if one of them went [start,east,east] and the other went [start,west,west]! But two solutions with different scores but from the same square *are* equally branching because from this point they can now make the same decisions. In cases where two partial solutions have the same score, but one of them has *strictly* more choices than the other one you generally eliminate the smaller option, since it will never 'do' anything the other one couldn't have done anyway (this highlights one of the founding principles of why we almost always use breadth-first searches instead of depth-first ones). So, in the desert case the better metric is actually the position you are in, and the solution with the least number of moves is the one kept since, by assuming you 'die' at some finite number of steps, the solution fewer moves can do everything the other solution can *and more*. This approach then automatically prevents you from walking in circles because longer paths will be discarded in favour of the shorter ones (since they both reach the same square eventually anyway).


Trick 4 - Unlimited, Non-Decreasing Metric Spaces (a.k.a. You Never Get A Second Chance To Make A First Impression).

This is a pruning technique for searching problems. This is an even stronger improvement than the previous trick. In an 'unlimited' scenario, the goal of the scenario is to produce the 'highest'* possible value you can get, rather than trying to get the answer closest to some number X (this makes a huge difference). In a 'non-decreasing' scenario, the problem is constructed in such a way that, given a partial solution, any set of choices you make after that point *cannot* make the answer worse than it already is. For example, in 2002-Q5 we are presented with a sequence of yes/no choices that will affect our 'lolly score', but also affect how long we have to wait to 'play again'. However, once we have collected a certain number of lollies we can never have them 'taken away' (although there may be another solution which gives more lollies). Why is this important? Because for most cases it means that given any number of partial solutions which have reached the same 'time' we can immediately eliminate all but the best solution, because the weaker solution(s) will never be able to overtake the better solution. Why? Because any choice they could make after now, the 'best' solution could make too! This effectively reduces the size we have to search from a^n down to a*n (where a is the degree of the choice and n is the number of choices). In 2002-Q5 and in 2002-Q4, we only needed to ask the questions once at each point, because for each possibile outcome there will always be one 'best' answer.

By the way, if this sounds familiar, it's because it is! This is the long description of when you can use the Mini-Max pruning technique (the *only* branch I want to follow is the one with the best score). The problem of 'local min/max's is circumvented by the requirement that solutions you pruned must have been completely contained in some other branch you followed (or pruned) - which is clearly the hard part in the Real World(tm).

* :: I used the term 'highest' to convey the general idea that you aren't aiming for a given target, but are simply just trying to play the 'best' game ever played. This mostly occurs in games where you are trying to score the most points you can (rather than games where you must make X tricks), but also applies to games where you are trying to get '0'. In this case, you simply think of the value you are trying to maximise as: (Integer.MAX_VALUE - score). Clearly, the closer to zero you get the better your answer, and any path that gets you to the same place in fewer turns is obviously always going to be closer to zero than a path that took three trips around the block!


Trick 5 - Sorting Algorithms.

I'm just providing a copy of these algorithms so you don't have to hunt it down. You should replace the class of the list with your class that implements "compareTo" properly.

Sorting.java

Updated 23 / 9 / 2003