Match Editorial

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

The Problems

This problem consists of decomposing integers into their decimal digits and composing integers from decimal digits. In general there are two approaches. The first uses the division and modulus operators to extract the digits one at a time, and then uses multiplication and addition to rebuild the new integer. The second approach converts an integer to its string representation so that string operations can be used, and then converts the resulting string back to an integer.

For the first approach, one can remove the ones digit from an input number and append it to an output number. The ones digit is obtained by computing the input number modulo 10 (using the % operator), after which the input number is shifted to the right in base 10 by one (by dividing by 10 using integral division). A digit is appended to the output number by shifting the output number to the left in base 10 (by multiplying by 10) and adding the digit. A good example of this approach is InsaneParadox's implementation.

For the second approach, simply convert the integer to a decimal string representation using whatever facility one's language provides. In Java, this would be String buf = new StringBuffer(x). In C++, this would be char buf[16]; sprintf(buf, "%d", x);. Then perform a reverse operation on the string (provided by the string representation in each language) and convert it back to an integer. In Java this is Integer.parseInt(buf.toString()) and in C++ this is atoi(buf). A good example of this approach is Sleeve's implementation.

The first step is to sort all the referenced times chronologically. This could be done by putting them all in some sort of array and sorting it, or constructing a boolean array of length 1001 that represents which times were referenced in the input.

Next, initialize a counter to zero and iterate through the referenced times. For each time, increment the counter and then skip any of the times following it that are within 15 minutes (inclusive) of that time. Once all referenced times have been processed in this fashion, the counter will hold the appropriate value to return.

This is a neat little problem that initially requires some thinking. However, a little thought eventually leads to a very trivial and compact solution.

The solution to this problem consists of two parts. The first is computing the smallest power of two that is greater than or equal to the number of coders (which we will call n). This part is easy. We initialize a counter to 1 and left-shift it by 1 (using the << operator) while it is less than n (the left-shift is equivalent to multiplication by 2). Let us call this number z, giving twice the number of coders we will have in the next round.

The second part is a little trickier. Basically, we want to find the values x and y, such that the following hold:

The value x represents the number of coders that compete in the first round, and the value y represents the number of coders that are given byes. We get (1) from the constraint that n coders must be decomposed into x competitors and y bystanders in the first round. We get (2) from the constraint that x /2 and y coders will remain in the second round, and our target number of coders in the second round is z /2. By subtracting (2) from (1) , we get

We can now use (1) to solve for y:

We know z and n, and we can now see that finding y is absolutely trivial. It is now just a matter of using a stable sorting algorithm to sort the coders and return the handles of the first y. If y = 0, we return the fact that no byes are needed.

The key to understanding this problem is to frame it as a linear algebra problem. Each molecule can be represented as a vector by arbitrarily assigning rows uniquely to each of the elements. We are given vectors x, y, and z, and we are asked to determine whether a unique set of constants a, b, and c exists that satisfies the equation a x + b y = c z. (I will always designate vectors in boldface and scalars in italics).

There are multiple ways we can solve this problem. The first is by Gaussian elimination. The problem is equivalent to solving for

A good example of a solution using Gaussian elimination is ZorbaTHut's solution in Room 1. However, this method is tricky to implement correctly (unless one has the code already lying around).

Another option is to take advantage of all the constraints we are given. First, we are only interested in solutions that yield positive integral values for a, b, and c. Furthermore, the input constraint that prevents the number of atoms of a particular element from occurring more than 9 times provides a reasonably low upper bound for sensible values that any of these scalars may take. Thus the simpler solution is to iterate through each sensible value for a and b (the value for c, if any, will depend on the values of the other two scalars).

Due to time constraints, I will not cover the solution using Gaussian elimination, but instead will only cover the simpler solution that takes advantage of all the constraints. It is not difficult to implement, provided one can manage to convert the input string into the three vectors.

The first issue is determining an appropriate upper bound for sensible values for each scalar. An upper bound that is too high might cause the program to run too slow, but an upper bound that is too low will cause the program to be incorrect. The upper bound turns out to be 81, but Echo's proof of this is still forthcoming (if I get a chance I'll try to prove it myself).

Since the upper bound is so low, we could easily nest three for loops to iterate through each possible sensible combination of values for the three scalars. Or, if we want to get fancy, we could iterate through combinations of just two of the scalars, deriving the value of the third from the first two. In either case, we then check for consistency. That is, we plug the values for our scalars into (5) and see if it holds. If so, then we have found a solution. We must continue checking all combinations, returning the fact that multiple solutions exist if we find a second solution, but otherwise continuing until we exhaust all combinations. If we find no solutions, then the system is unsolvable, else we plug the values of the scalars in our solution into the original input string in the appropriate manner and return it.

There aren't really any known algorithms for computing the number of ways it is possible to pack a set of tetronimoes in an arbitrary space. Fortunately, the problem is designed with brute force in mind.

A high-level description of the problem makes it seem easy. For each piece that has not been used, attempt to find a location and orientation where it fits. If one is found, remove the Xs covered by the piece and continue with the remaining pieces. Then unmark the same Xs and try to find another location and orientation. After all locations and orientations have been tried, try the next piece. If all the pieces have been examined and all the Xs are covered, then a packing has been found.

The only tricky part is representing the pieces in a useful manner. Not only does the relative positions covered by a piece about its origin need to be represented, but an easy way to transform these positions by rotations has to exist as well. One can either represent each piece as relative row-coordinate pairs and specify which rotations are valid for that piece, or one can represent each rotation as a unique piece. The former requires more logic, the latter requires more typing. If the former method is used, keep in mind that piece A is only valid for rotations of either 0 or 180 degrees and either 90 or 270 degrees. The same applies for pieces D and E. Piece F is only valid for one rotation.

The rest is implementing the permutation logic in an efficient manner, exhausting the possible packings without exhausting the time limit.