{"id":775,"date":"2015-04-12T07:28:09","date_gmt":"2015-04-12T07:28:09","guid":{"rendered":"http:\/\/www.themissingdocs.net\/wordpress\/?p=775"},"modified":"2015-04-12T07:28:09","modified_gmt":"2015-04-12T07:28:09","slug":"gcj15-qr","status":"publish","type":"post","link":"https:\/\/www.themissingdocs.net\/?p=775","title":{"rendered":"GCJ15 QR"},"content":{"rendered":"

20 points to advance meant that a full solution to the simplest problem wasn’t sufficient.\u00a0 Even so 12438 people advance to round 1.\u00a0 23296 people got a positive score.\u00a0 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.<\/p>\n

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.<\/p>\n

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.<\/strong><\/p>\n

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.\u00a0 Accumulate these differences and return.\u00a0 This works because larger thresholds won’t stand up before earlier thresholds, and so you have to add enough to trigger the earlier threshold.\u00a0 Large input is only 1000, and the solution is linear anyway, so no problems with running time.<\/p>\n

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?<\/strong><\/p>\n

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.\u00a0 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.\u00a0 Interestingly the small input includes stacks of size 9, so at least this mistake wouldn’t slip past to the large input.\u00a0 The high percentage failure rate on the small input here suggest I may not have been alone in missing this key point at first.<\/p>\n

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.\u00a0 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.\u00a0 Giving a total of O(NK) N being number of stacks and K being the height of the largest stack.<\/p>\n

Assumptions at play here are that it is always better to split first before letting time run.\u00a0 This is pretty obvious as if a split is worth doing, doing it sooner means more pancakes per second are removed later.<\/p>\n

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))).\u00a0 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.\u00a0 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.\u00a0 Then just linear search for best.\u00a0 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.<\/p>\n

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.<\/strong><\/p>\n

A3) The problem helpfully explains that quaternion’s satisfy A*(B*C) = (A*B)*C.<\/p>\n

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.\u00a0 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.\u00a0 A fairly quick inspection finds that any quaternion to the power 4 is 1.\u00a0 Hence repeat counts mod 4 are the only cases needing to be considered.\u00a0 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.\u00a0 If the answer is i, store the pairing of the mod 4 power and the prefix length.\u00a0 Similar for k, but post multiply and postfix of the sequence.\u00a0 Both of these sets can be generated on O(N) the size of the repeating sequence which is at most 10k.\u00a0 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.<\/p>\n

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.\u00a0 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.\u00a0 Care must be taken if the number of repeats is small that the only mod 4 value which satisfies the criterion, might be negative.\u00a0 If you have a cache of prefix\/postfix values and powers of the repeated section, this becomes 3 quaternion multiplies.<\/p>\n

The first case where the 2 touch is more difficult.\u00a0 Need to check the mod sum vs the total repeats works out, since the j section doesn’t have any repeats this time.\u00a0 But unless you pre-cache the product of every subsection of the repeated section, it can’t be done in O(1) time.\u00a0 That pre-caching is another O(N^2) cost, and a lot of memory, so nice if we can avoid it.\u00a0 The solution is quaternion division (pre\/post) is well defined.\u00a0 Each quaternion multiplication is a permutation, so for a result and one of the input multipliers, there is only one possible value.\u00a0 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.\u00a0\u00a0 This is O(1) time, as we need.<\/p>\n

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.\u00a0 So if the total product if the entire sequence (including repeats) is not -1, we can exit out early.\u00a0 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.\u00a0 So generate the i and k prefix\/postfixes as before, but select the shortest of each.\u00a0 Now there is no longer an O(N^2) inner loop, just a check of the 2 shortest prefix\/postfixes do not overlap.\u00a0 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.<\/p>\n

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).<\/strong><\/p>\n

A4) The small input is interesting here because the number of test cases is 64 exactly.\u00a0 This corresponds to the number of possible small inputs! – R, C and n are all limited to the range 1-4.\u00a0 The large they are limited to 20, meaning there are only 8000 possible inputs.\u00a0 You could theoretically write a less efficient program, brute force them all and hard code the result.<\/p>\n

There is one main early out.\u00a0 If R*C % n is non-zero, it doesn’t matter what the opponent does, they always win by default.<\/p>\n

Another easy scope reduction is if R is larger than C, switch so R is the small one and C is the larger.\u00a0 Then if n is larger than 2R it can be made into an L shape that cannot possibly fit, so the opponent wins.\u00a0 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.<\/p>\n

The large input covers a lot more scenarios.\u00a0 But they can be brute forced by hand, if you are careful.\u00a0 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.\u00a0 Obviously the opponent can always choose this piece and make tiling impossible.\u00a0 This is trivially extended to all larger n-omino’s.<\/p>\n

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.\u00a0 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.\u00a0 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.<\/p>\n

So lets cover things in order<\/p>\n