Match Editorial

		MATCH EDITORIAL LINKS:
	Room 1 Review Archive   Rookie Review Discuss this match   Problem Set Want to write a feature?   Lessons Learned

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.

The Problems

Median 

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

• return the middle value if the size of the input is odd
• else return the rounded mean of the two middle values

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 n as n / 2 and (n - 1) / 2, using integer division, then one will get the same number twice for odd-length lists and the middle two values for even-length elements. If two values are the same, then the mean of the two is also the same, and so the same logic conveniently works for all cases.

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 n / 2 and n / 2 + 1 instead of n / 2 and (n - 1) / 2 which works for both odd- and even-length inputs).

Hiring 

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.

The number of unique triples formed from a set of n applicants is C(n, 3) = n * (n - 1) * (n - 2) = O(n3). Since the maximum value of n specified by the problem is 50, brute-force iteration of all the triples is sufficient.

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 loop:

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.

Super3 

Summary Algorithm

The algorithm consists of computing round(1000 * odds), where odds is your odds of winning. Rather than bothering with floating point arithmetic, however, we will decompose odds into a numerator and a denominator. The numerator is the number of possible drawings that result in a win for the person, and the denominator is the number of possible drawings. The result can then be computed by (10000 * numWays / possibleDrawings + 5) / 10 without any loss of precision. What we are doing with this operation is employing fixed point arithmetic, shifting our value to the left by one decimal digit so that we can emulate rounding with integers.

The trick to computing possibleDrawings is to maintain a boolean array used[position][digit], which indicates whether digit has been used in position. Then, for each value of position, we compute the sum of digits that have not been used in that position. We then take the product of these three sums to get possibleDrawings

We then need to compute numWays. The method for this is to iterate through all the purchased numbers, being careful to skip any that we have already processed. We can then check each of its digits and see if any have been used by querying our used array. If none of its digits have been used in their respective positions, then that particular purchase represents one possible way to win.

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.

Big2 

Summary

This was also a combinatorical problem, in the sense that the problem consisted of counting combinations that meet certain criteria.

Due 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.

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 loops, e.g.:

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 depth-first 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.

1. Flush - This is the easiest. Compare the suit of each of the last four elements to the suit of the first element. If any do not match, the hand is not a flush.
2. Four of a kind - Generate an array of length 13, each index of which represents a unique card value (e.g. 0 for 2, 8 for T, 12 for A). If the maximum value in this array is 4, then the hand has four of a kind.
3. Full House - Using the same array as before, determine if there is a value of 3. If so, determine that there is also a value of 2, or, alternatively, that there are no values of 1. If both tests pass, then the hand is a full house.

4. Straight - There are two ways of checking for a straight. One can either sort the subset (and note that by sorting the original hand one can generate subsets such that they are already sorted), or one can use the same array as for checking for four of a kind and full house.

   If using the former method, one has to deal with the special case of an ace if it is in the subset. If the ace is mapped to the highest integer value, check the last element of the subset. If it is an ace, and the first element of the subset is a 2, shift the subset to the right by one and place the ace at the beginning. The logic is similar if one is mapping an ace to the lowest value instead. Then check the last four cards in the subset and verify that the rank of each is the successor of the card before it in the subset. If all of these cards pass that test, then the subset represents a straight.

   If the latter method is used, one must iterate through each value of 1 in the array. For each such value, determine if each of the next four values is also one (wrapping around using % 13 on the index). If such a sequence is found, then the subset is a straight.

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.

The arbitrary nature of poker hands made it easy for people to make minor, non-obvious mistakes. Fence-post 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.

Shared 

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 4! = 24 orderings of the processes, simulating the lifetime of all the processes for each iteration.

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:

1. Process all terminating processes
2. Process all processes that are releasing a lock this time slice
3. Process all processes that are requesting a lock this time slice
4. Increment the instruction counter of any non-terminated processes that are not stuck waiting on a lock

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:

1. Process all terminating processes - We don't really have to do anything, just mark the process as terminated.

2. Process lock releases - Here we just remove the mappings from the appropriate maps for each releasing process.

3. Process lock requests - This is the complicated part. We iterate through each process that is making a request in order of precedence, from highest to lowest. For each such process, we first have to determine if any process of higher priority currently holds a lock that excludes this process from obtaining the lock it is requesting. If the request is for a read lock, this consists of finding any process of higher priority that holds a write lock on the same address. If the request is a write lock, this consists of finding any process of higher priority that holds either a read lock or a write lock on the same address.

   We then look for processes of lower precedence that are holding locks that would exclude this process from obtaining the lock. For each such lock, we remove it, "rolling back" the process that held it when we do so. If our process is requesting a read lock, we roll back any process of lower precedence that is holding a write lock on the same address back to the point where it obtained that lock. This rolling back process consists of setting the process's instruction counter to that associated with the lock that it just lost, and then removing all locks it holds with an instruction counter higher than that. If our process is requesting a write lock, we roll back any process of lower precedence that is holding a read or write lock on the same address. If such a process holds both read and write locks, we roll back to the lock that occurred earlier (has the lower precedence counter).

4. Incrementing instruction counters - We incremnt a process's instruction counter if one of the following holds for this time slice:

   • The process's current instruction is NOOP
   • The process's current instruction is a lock release
   • The process's current instruction is a lock request that succeeds

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.