20 points to advance meant that a full solution to the simplest problem wasn’t sufficient. Even so 12438 people advance to round 1. 23296 people got a positive score. Makes the 1371 people who turned up to topcoder open pretty tiny, although maybe the simultaneous scheduling of code jam qualifying round and topcoder open was part of why topcoder open’s numbers were so much lower than usual.
348 perfect scores, despite the problem worth the most points having significant scenarios in the large input that were not even close to covered in the small input.
Q1) Given a count of the number of people who will stand up for each threshold of people already standing up, determine the minimum number of extra people (of any mixture of thresholds) required to make everyone stand up.
A1) This is a basic greedy problem, consider each threshold with non-zero population in order, if there aren’t enough people assume there are by adding the difference between how many are standing up and need to be standing up to the already standing up set. Accumulate these differences and return. This works because larger thresholds won’t stand up before earlier thresholds, and so you have to add enough to trigger the earlier threshold. Large input is only 1000, and the solution is linear anyway, so no problems with running time.
Q2) Given stacks that go down by one every minute, except if you pause everything and move a subset of one stack to anywhere else, including making a new stack, what is the minimum time for all stacks to become empty?
A2) So my first instincts here were wrong, a single stack of size 9 can be done in 5 minutes, but my first instinct was to only ever divide stacks into two, which gives 6 minutes as best effort here. The correct approach is to take 6 (or 3) off , then 3 off the remaining stack of 6, then allow 3 minutes to run its course of the 3 stacks of size 3. Interestingly the small input includes stacks of size 9, so at least this mistake wouldn’t slip past to the large input. The high percentage failure rate on the small input here suggest I may not have been alone in missing this key point at first.
To get the large input done in time it is sufficient to solve the problem in O(NK) time, so one option is to consider best time where you split tall stacks down to a maximum height of m before allowing time to run. Height ranges to consider are from 1 to tallest stack, and number of turns to split a stack down to at most height m is given by simple division, so the total of all stacks can be done in O(N) time. Giving a total of O(NK) N being number of stacks and K being the height of the largest stack.
Assumptions at play here are that it is always better to split first before letting time run. This is pretty obvious as if a split is worth doing, doing it sooner means more pancakes per second are removed later.
I think there is an approach with better runtime characteristics, which involves considering only a subset of all heights, something like O(N*Sqrt(K)*Log(N*Sqrt(K))). For each stack generate the the set of heights for splits down to sqrt of its height, sort all of these in decreasing order and consider the ones greater or equal to sqrt of the largest height. Each step through this list of heights corresponds to one extra minute doing a split, and defines a sequence of heights of highest remaining after n splits. Then just linear search for best. This approach presumes it is never any better to divide a pile beyond its square root, which seems straight forwardly true, dividing things further takes more than one extra split per height reduced.
Q3) Given a potentially repeating sequence if i’s j’s and k’s, determine if it is possible to subdivide them into sections which evaluate to i, j and k respectively assuming that the i, j and k’s represent standard quaternion’s and are being multiplied using standard quaternion multiplication.
A3) The problem helpfully explains that quaternion’s satisfy A*(B*C) = (A*B)*C.
One approach (which is a bit slow, but just sufficient for the large input) is to determine all prefixes which can create i, all the postfixes which can create k, and determine if the gaps in between create j. The fact that the sequence can be repeating (and the repeat count can be huge) appears to be a problem at first, but a close inspection of quaternion powers reveals this is not going to be a problem. A fairly quick inspection finds that any quaternion to the power 4 is 1. Hence repeat counts mod 4 are the only cases needing to be considered. So, calculate the value of the entire repeating sequence, and consider each of its 4 powers as a pre multiple of any prefix of the repeating sequence. If the answer is i, store the pairing of the mod 4 power and the prefix length. Similar for k, but post multiply and postfix of the sequence. Both of these sets can be generated on O(N) the size of the repeating sequence which is at most 10k. Each set is also O(N) in size, so we have to be able to determine whether there exists a j in between in O(1) time, as anything over O(N^2) is clearly too slow.
Given a candidate i and k prefix/postfix – there are 2 possibilities, the prefix postfix meet at the same central location and the j is the middle section of that repeated segment, or they have a larger gap in between, and j is a postfix (optional repeats) prefix sequence. The later is easiest, the postfix length is defined by the prefix length of the candidate i, the prefix length defined by the postfix length of the k candidate and the number of repeats, mod 4 is defined by the mod 4 of each of the i and k candidates and the total number of repeats. Care must be taken if the number of repeats is small that the only mod 4 value which satisfies the criterion, might be negative. If you have a cache of prefix/postfix values and powers of the repeated section, this becomes 3 quaternion multiplies.
The first case where the 2 touch is more difficult. Need to check the mod sum vs the total repeats works out, since the j section doesn’t have any repeats this time. But unless you pre-cache the product of every subsection of the repeated section, it can’t be done in O(1) time. That pre-caching is another O(N^2) cost, and a lot of memory, so nice if we can avoid it. The solution is quaternion division (pre/post) is well defined. Each quaternion multiplication is a permutation, so for a result and one of the input multipliers, there is only one possible value. We know the value for the product of an entire section, and the value of the prefix and postfix, so we can do prefix division and then postfix division to determine the value of the middle part. This is O(1) time, as we need.
However, there is a better way! – if the sequence can be broken in to i, j and k subsections, its total product must be the same as the product of i j and k, which is -1. So if the total product if the entire sequence (including repeats) is not -1, we can exit out early. If it is, there is no need to verify the value of j, instead all that is required is to verify that there exist i and k prefix/postfix, and those do not overlap. So generate the i and k prefix/postfixes as before, but select the shortest of each. Now there is no longer an O(N^2) inner loop, just a check of the 2 shortest prefix/postfixes do not overlap. If they don’t, then the inner section is known to be j – given by the fact that quaternion division is well defined and knowing the total product.
Q4) In a game where an opponent gets to choose one n-omino, and you have to place it in an RxC sized container and then fill the remaining space with n-ominos of the same size (but not any specific shapes), determine whether for a given RxC and n the game is always winnable by the opponent (as in they can always choose an n-omino that you cannot place and fill the surrounds).
A4) The small input is interesting here because the number of test cases is 64 exactly. This corresponds to the number of possible small inputs! – R, C and n are all limited to the range 1-4. The large they are limited to 20, meaning there are only 8000 possible inputs. You could theoretically write a less efficient program, brute force them all and hard code the result.
There is one main early out. If R*C % n is non-zero, it doesn’t matter what the opponent does, they always win by default.
Another easy scope reduction is if R is larger than C, switch so R is the small one and C is the larger. Then if n is larger than 2R it can be made into an L shape that cannot possibly fit, so the opponent wins. This is actually almost sufficient for the small input, the one remaining case is the t piece can be selected in 2×4 for n=4, which splits the the space into a 1 and 3 areas which can’t be filled.
The large input covers a lot more scenarios. But they can be brute forced by hand, if you are careful. The 17% pass rate suggests cases are easy to miss… First there is a hint in the problem itself, it shows some of the 7-ominos, one of them has a hole. Obviously the opponent can always choose this piece and make tiling impossible. This is trivially extended to all larger n-omino’s.
Before I cover the remaining scenarios it is worth mentioning that if the opponent can’t win for AxB, anything larger than AxB that satisfies the mod n condition also can’t be won by the opponent. So we just have to start small and work our way out, as soon as we get a case where we win, everything larger is a given. It is fairly trivial to see that some simple zig-zag filling can be used to fill any L shape or rectangle shape that you might add to an AxB to make it a larger case, so long as these L/rectangle shapes themselves are a multiple of n in area.
So lets cover things in order
- n = 1 – trivially no opponent win.
- n = 2 – trivially no opponent win if mod satisfied
- n = 3 – no opponent win if R > 1 and mod satisfied, otherwise opponent win – again pretty trivial.
- n = 4 – opponent win for R = 1 by L shape. As mentioned before the t shape is opponent win for R = 2 and C = 4, but this extends to R = 2 in general, as it leaves both sides of wherever you place it with a 1 mod 2 value, which can’t be tiled using pieces of size 4. R = 3 and higher always works because 3×4 can easily be tiled regardless of opponent choice. (There aren’t many choices for tetromino’s so they are easily worked through.)
- n = 5 – here is where it gets tricky… base is opponent win for R <= 2 using the L shape. R >= 4 is no opponent win, not trivial to work out, but you can consider all 12 by hand for 4×5, and then larger falls out.
R = 3 is the gotcha case. The tricky piece is the diagonal step shape – also known as ‘W’ under standard pentomino naming. Regardless of rotation in an R=3 space this divides the space into two parts. For C = 5, the size of these parts is 3 and 7, or 6 and 4 depending on placement. Neither of these can be tilled. But for C = 10 or higher, it can be placed so the spaces are 15 and 10 (in the C = 10 case, similar in larger), which can be tiled easily. - n = 6 – again L shape gives opponent win for R = 2. R = 3 is an opponent win by the dagger shape a 4×3 cross which divides the shape into 2 mod 3 and 1 mod 3 spaces, which can’t be tiled by size 6 shapes. It also can’t be tiled due to the 3×3 ‘space invader’, despite being able to place it in any rotation, which I think is cool…
R = 4 – this time there are 35 different 6-omino’s to brute force, but none of them cause trouble in 4×6, and hence all larger is no opponent win if mod condition is satisfied. - n >= 7 – the piece with a hole gives guaranteed win to opponent.
I missed the W shape in n = 5 when I tried to work these things out by hand, I wonder what the most common mistake was for the large input.
I also wonder how many people tried to actually solve the puzzle programmatically rather than hard coding rules from by hand brute force. This is not trivial as it involves determining whether you can tile a connected space or not and it is possible to create a ‘t’ junction which means even if the space to fill is a multiple of the n under question, it depends on how many pieces are on each side of the ‘t’ junction as to whether it can be connected. Its also tedious generating all the n-ominos (if you don’t hard code them) and writing reflection/rotation generation and sliding them all around. And for the largest sizes you might risk time-out, unless you take advantage of the expansion proof where smaller cases answer larger cases I mentioned, and pre-calculate the answer for all possible inputs (from small to large) before running the 100 test cases.