May 30, 2002 Match summary For the most part, the problems for this match were easier than usually. Many consisted of simply iterating through possible combinations of fixed size, returning the best one or the total count. The exception was the Division 1 Level 3 problem, Shared, which only four people solved. This was the only problem written by Soli, while all the other problems were written by Perlaze. Statistics
The Problems
Author:
Perlaze
Used as: Division 2, Level 1 Reference implementation: leelin in Room 33 Implementation This is the sort of problem that many Division 2 coders would probably classify as a "typing exercise." The description basically gives the solution away: sort the input, then
With some careful thought, one can generalize this so that it doesn't matter if the size of the input
is even or odd. If one defines the middle two elements of a list of length
The most common mistake by far was incorrect calculation of the mean.
Many coders computed the mean between the two numbers immediately above the median, rather
than the numbers immediately below and above the median (e.g.,
indices of
Author:
Perlaze
Used as: Division 2, Level 2 Reference implementation: Jeffa in Room 29 Summary The solution to this problem is to iterate through each unique, possible triple, and select the one that is best under the ordering on triples defined by the problem. Algorithm
The number of unique triples formed from
a set of
The key to solving problems of this nature is having code ready for iterating through combinations
of elements in a set. Since we are generating only combinations of size 3, we can actually do this
with a simple for(int i = 0; i < len  2; i++) for(int j = i + 1; j < len  1; j++) for(int k = j + 1; k < len; k++) In general, one could also implement a recursive implementation that can find combinations of any size. However this is implemented, for each combination it is easy to pick the combination that yields the highest average exam score without exceeding the salary cap.
Author:
Perlaze
Used as: Division 1, Level 1 Reference implementation: malpt in Room 1 Summary Algorithm
The algorithm consists of computing
The trick to computing
We then need to compute The most common error was incorrectly handling duplicate purchases, even though there was a sample test case that would have made such a mistake glaringly obvious to those that tested with it. Obviously quite a few people rushed through the problem without testing or reading it thoroughly.
Author:
Perlaze
Used as: Division 1, Level 2 Used as: Division 2, Level 3 Reference implementation: reid in Room 1 Summary This was also a combinatorical problem, in the sense that the problem consisted of counting combinations that meet certain criteria. AlgorithmDue to the nature of the input, a brute force solution is all that is needed. We iterate through each possible subset of the hand that is of size 5, and count how many of these subsets constitute "poker hands." The number of possible subsets of size 5 is C(13, 5) = 13! / (5!8!) = 1287, which is within reach of even an incredibly slow implementation. Implementation
There are two tasks that the program must do. The first is constructing subsets of size five from the input,
without repeating any subsets (and recall that subset equality is independent of element order). This is a common
operation in any contest, and every coder should have code readily available either on their computer or in their
head to perform this operation. As with the Super3 problem, it is reasonable
to build a nested structure of five for(int i = 0; i < 9; i++) for(int j = i + 1; j < 10; j++) for(int k = j + 1; k < 11; k++) for(int l = k + 1; l < 12; l++) for(int m = l + 1; m < 13; m++) { ... } Or, one can use recursion in conjunction with a boolean array (similar to a depthfirst search), which is more useful in the general case. The second task is determining whether a particular subset constitutes a poker hand. The problem statement attempts to mislead you by bringing up the subject of straight flushes, but since a straight flush is defined as a hand that meets two criteria that each individually would qualify a hand as a poker hand, we can completely ignore it. It's easiest to take the remaining types of poker hands one at a time.
If a subset matches any one of these types of poker hands, we can increment our count of poker hands and immediately move on to the next subset. MistakesThe arbitrary nature of poker hands made it easy for people to make minor, nonobvious mistakes. Fencepost errors are easy to make in this situation, and the dual nature of aces caused a lot of people to write incorrect code for checking for straights.
Author:
Soli
Used as: Division 1, Level 3 Reference implementation: ZorbaTHut in Room 1 Implementation This monstrosity by Soli defeated most programmers in Division 1. Of 261 contestants, only 10 were even able to submit it, and only four of these submissions were actually correct.
The problem in itself is not all that difficult. The problem statement lays out a set of rules
governing how a simulation of the execution of four concurrent processes occurs. The problem
is to find the ordering of precedences for the four processes that gives the best turnaround time,
and return the turnaround time. Since there are exactly four processes, the general form of the
solution is to iterate through each of the The hard part is implementing the simulation. As with any simulation, the key is to organize one's thoughts and code in such a manner that it reflects the simplest interpretation of the rules in a correct manner. In this case, the simulation should iterate through each time slice. For each time slice, process the processes that are still executing in the following manner:
We will represent the set of locks held by a process as a mapping between the address of the lock and the value of what the instruction counter was when the process obtained the lock. We use separate maps for the read and write locks. For each of the above tasks:
And so we repeat this until every process has terminated. The number of time steps it takes to reach this point is the turnaround time for this particular permutation of precedences. By doing this for all 24 precedences, we can obtain the minimum turnaround time. 
