Category: Code Competitions

TCO hasn’t really been drawing the crowds this year – another relatively low turn out again for R1C.  Only 815 people registered out of 2500 available slots, 750 to advance (in theory), but again the positive score requirement kicked in and only 622 will advance as a result.  So including byes there is only ~2150 people advancing to round 2.  The problems were pretty easy this time round, although problem 2 wore a pretty good disguise.  I think I could have solved all 3.

Q1) In a given 2xN grid, no two filled in cells are touching by edge or corner.  Without clearing any of the existing filled in cells, what is the maximum number of filled in cells that can be without any 2 touching by edge or corner?

A1) So this problem doesn’t look that difficult, but it becomes trivial once you realize that in a 2xN grid, if no two filled cells can touch by edge or corner, there is no change in restriction if you move every existing filled cell to the first row, and delete the second row entirely.  Obviously only at most one can be filled in any column, and if it is, both of its neighbouring columns have to be empty.

Once the problem is reduced to 1xN, its trivially a greedy left to right fill in while both neighbours aren’t filled in – then count how many are filled in.

Q2) Given a rooted tree and defining a path as being a sequence of one or more distinct vertexes where consecutive elements in the sequence are connected by an edge, determine the maximum number of paths that you can select at once, such that no element of any one path is an ancestor of any element in any other.

A2)  Key here is that a path is a sequence of one or more vertexes.  But every vertex you add to a path can only decrease the number of other paths that could be selected such that there is no ancestor commonality. Therefore the whole paths thing can be disregarded, the question is just how many vertexes can you select such that none are a parent of any others.

Given a non leaf node in a tree, if it is selected, none of its (direct or indirect) children can be selected.  So if it has more than one direct child, it is obviously better to replace it with its children instead.  If it does have only one child replacing it with its child doesn’t make anything worse, but it does potentially lead to a further replacement if there a branching factor greater than 1 anywhere in its indirect children.  Ultimately this means there is no point selecting anything other than leaf nodes.  Leaf nodes also cannot possibly be an ancestor of any other leaf node or vice versa, so the problem reduces down to counting the leaf nodes in the tree.

Q3) In a list of boolean values, its ‘value’ is equal to the number of distinct subsections which are entirely made of alternating 1’s and 0’s.  A subsection of length 1 is considered to trivially ‘alternating’.  For a given n and k determine how many possible lists of boolean values of length n have ‘value’ k.

A3) This problem is clearly the hardest of the 3, but it has a fairly obvious dynamic program style solution.  A sequence of length i ending with alternating section of length j, with existing value v, can either be extended to i+1 with alternating length 1 with value v+1, or length i+1, alternating length j+1 with value v + (j+1)*j/2.  So if you have x of such sequences, you can add x to both of the destination cells.  Start with a seed of length 1 with alternating section length 1 and value 1.  Each target cell is always strictly greater in i and v, so iterate over j last.

Note that I didn’t talk about 0 or 1 here.  But you don’t need to, every sequence has a complement of same value by swapping all 0 to 1 and vice versa.  So the basic program output just needs to be doubled.  Then finally the n and k from the original input map to i and v, and you sum over all j.

This was a round of relatively tough problems.  In the end solving the first and the small of the second was sufficient to advance, so long as your time penalty wasn’t excessive.

Q1) Given the increment and reverse digit order operations, what is the minimum number of steps to get from 1 to x?

A1) So the small input can be brute forced using a breadth first search, but why this is true is one of the key points towards the large input which cannot be brute-forced.

The danger with any breadth first search is that the search space might explode.  But in this case a quick inspection finds that a search to find x never considers values greater than 10^(ceil(log10(x))).  Of the operations available, only the increment can increase the number of digits.  Therefore in order to get to a value in the next tier, you have to first get to 9999…  It is therefore interesting to see how many steps it takes to get to each tier.  Inspecting the bfs it takes 1 to get to 1, 9 more to get to 10, 19 more to get to 100, 109 to get to 1000, 199 more to get to 10000.  This pattern leads to the insight of what the minimum number of steps involved is to get from one tier to the next.  First increment until the last half of the digits are all 9, then reverse, then increment until next tier is reached.

Having made this observation it is natural to jump to a greedy approach, calculate number of steps for each tier, then on the last tier increment until the last half of the digits match the start of the desired number, reverse and then increment until the desired number is reached.  There is one corner case however.  If the target number ends in zeros, reversing leaves you with a number ending in 1, and you can’t go backwards.  The natural fix here is to aim at the first half of the digits – 1, reversed, as the last half of the digits.  So for 9900 the first step is to get to 1089.

This just leaves proof the approach is right.  The greedy algorithm is pretty obviously the minimum number of steps which stays within a tier, but we need to rule out going up a tier, reversing a number ending in zero.  This falls out from the number of steps the greedy algorithm takes to get to a number worst case within a tier.  For anything that doesn’t end in half zeros, the number of steps is obviously less than the number of steps to get to the next tier, since each sub part of the algorithm has less steps.  This leaves 90, 900 and 990 as a potential worst case scenarios.  First takes 18 steps (less than 19) from 10.  The second takes 108 steps (compared to 109) from 100.  Finally the last takes 99 steps (compared to 109) from 100.  So going up and then down is never going to be cheaper.

Q2) Given RxC grid and N filled in squares, what is the minimum number of shared edges.

A2) The small input is only 15, so brute force simulation is nice and easy.   Conveniently 15 is also 3×5, which ensures good coverage of the main corner case.

The large input seems a natural ‘greedy’ approach scenario.  Checker-board coverage, then fill in any empty corner locations (for 2 edges each) then any empty edge locations (for 3 edges each), then the centre (for 4 edges each).  But this fails.  Inspecting brute-force vs greedy the differing scenario is in 3×5.

Greedy for N=12 gives:

xxxxx
xx.xx
x.x.x

Brute force on the other hand gives:

xxxxx
x.x.x
xx.xx

Greedy scores 12, brute force scores 11.

At this point I have to say I was stumped, I started to consider DP style approaches, but they were all very very computationally expensive, the large input was not plausible.  So I looked at one of the submitted solutions.  And now staring at the cases I presented above it seems obvious, but maybe it would have been more obvious if I had of presented N=11.

Greedy vs Brute-force for N=11.

xxxxx xx.xx
xx.x. x.x.x
x.x.x xx.xx

For an odd by odd grid, there are 2 ways to tile checker-board style and the maximal one is not always the best option as a starting point for the greedy algorithm.  A single extra spot has a cost of 3 in maximal grid, but in the inverted grid the first 4 extra spots cost 2.  The inverted grid fills one less spot, so at 2 spots at 2 each vs cost of 3 is a loss, but 3 spots at 2 each vs 2 cost of 3 is a draw, and 4 spots of 2 each vs 3 of 3 is a win for the inverted grid.  Ultimately the inverted grid starts losing again because it has more interior points which cost 4, but while its edges are still being filled in, it gains and then holds the advantage.

Ultimately 3×5 is not required to force the inverted grid, 3×3 has a win for the inverted grid at N=8.  But 3×5 does cover the full progression of cases better.

Q3) Given a bunch of people walking endlessly at constant speeds around a circular track, with varying starting points, determine the minimum number of times to meet up with anyone else in order for you to do one loop of the track, if you can do any speed you want whenever you want.

A3) So I think that your super powers with regards to speed means the problem can be turned into one of arrival time.  If you arrive at the destination at time x, you have to have gone past anyone who hasn’t yet completed a lap (for 1 meeting each) and have one additional meeting for every time you have been ‘lapped’ by someone who has completed 2 or more laps.  Trivially infinite speed with an arrival time of 0 gives you an upper bound which is equal to the number of walkers.  It also seems obvious that an arrival time larger than that of the slowest walker’s first arrival is not worth considering, it is a possible minimum, but any longer you can only be lapped by more walkers, so it can’t be any lower. The trick is to determine the potential arrival times of interest and calculate the number of meetings in time.

It is easy enough to sort everyone by their first arrival time, this gives a bunch of ranges to calculate the number of times you get lapped, but the naive approach of calculating number of times you get lapped is O(N) for each arrival time.  And O(N^2) is not going to cut it for N=500000.

In between each arrival time the number of meetings can only go up, when you get lapped, the instant after an arrival time is the only time it can go down, and it only goes down by one.  This leads to an observation.  Arrival time 0 gives an upper bound on the answer of 0 and if you are considering arrival time of the kth earliest first arrival and the number of meetings which have occurred is greater than N+(N-k), there is no way the remaining meetings can get the total meetings below N.  Therefore there is no value in continuing once you have reached 2N-k meetings, or more simply 2N.  2N is 1 million.  So if we can simulate ‘every’ arrival time (not just the first arrivals) in O(log N) time each, and early out once we hit 2N, we can run in time.  Simply putting walkers in a heap ordered by their next arrival time, and putting them back in with their next arrival time, will give the desired behaviour.  Just need to track whether its first arrival or not in order to decrement or increment the times.

Oh and there is likely a corner case to do with equal arrival times, they have to be processed as a group because you can’t arrive in between them, only before or after.  And getting accurate equal arrival times requires using fractions rather than floating point.

I’ve migrated TMD.Algo from my internal source control to a GitHub public repository.  It can be found here.

As part of the migration I have dropped the signing key, so a simple download of the project will actually compile, but adding the built result to the GAC (if you so wish) will involve a bit more work.

Also along with the move to GitHub comes some work I’ve done on the library over the last couple of years, so I’ve upped the version number to 0.0.6.0.  The major new feature is the GCJ class under TMD.Algo.Competitions.  This class is designed to be the main entry point of a program parsing Google Code Jam style input and producing Google Code Jam style output.  It simplifies the basic parsing logic.  It also optionally supports running test cases in parallel, for those times your code just doesn’t quite optimize fast enough to otherwise solve in time.

The majority of the work for 0.0.6.0 however was in starting a new set of integration tests.  These integration tests take custom written solutions to past GCJ problems, which attempt to use the TMD.Algo library as much as vaguely makes sense, and ensure that they can handle the practice sample/small/large inputs to produce outputs that GCJ practice website considers passing.

Other smaller changes can be found in the commit description.

Over 12000 qualifiers could have turned up for R1A, but given time zones that was always unlikely.  5032 positive scores, over 300 perfect scores, and the advancing cut off was a fast time on the first 2 problems completely solved.  If I had of been doing this round I think I would have advanced, but maybe not having completed the easiest question – as I think the wording is incomplete, leaving the question open to being interpreted as a much harder question.

Q1) Given a list of observations of the number of items on a plate at 10 second intervals and knowledge that there is someone who can add items at any time, and another person who removes them either whenever, or at a constant rate if the plate is not empty (but not both).  What is the minimum number of items the second person removes under each mode of item removal.  Presume that constant rate item removal is a continuum, if removing 1 per second, there is half of the item still on the plate at 0.5 seconds.

A1) So I’ve changed the wording for this question to be what was actually marked correct, there is no statement regarding whether items are removed from the plate discretely or gradually across the period of constant rate of removal.  Removing discretely is a much different question, which is quite a bit harder.  (And given the persons ability to remove arbitrary numbers of items at any point in time in the first mode, my mind gravitated towards discrete.)

To see where this is different consider the example 1 1 1 0.  Under the continuum removal case the number of items removed per 10 second period must be an integer, as all observations are integer.  Hence 1 item per 10 seconds is the minimum removal rate, and 3 items are removed.  But if removing is a discrete event, you can choose a removal rate of 1 every 25 seconds, in which case only 1 item is removed. (Assuming that the discrete removals happen at the end of each removal period rather than the start – the start you have to remove one immediately, so the total is 2.)

Given the continuum restriction this problem is trivial.  In the first mode of removal you remove items only if the count goes down from observation to observation, so just sum the neighbour differences where they go down.  In the second mode the minimum number removed is described by the minimum rate – and the minimum rate is given by the largest drop.  Once largest drop is found the answer becomes simply a sum of all the values (excluding the last) except if the value is above the largest drop, then you just add the size of the largest drop instead.

The non-continuum problem is much harder as you have a search space which is not limited to integer values per 10 seconds, and its not clear that it is even a single transition from too slow to fast enough which would allow it to be binary searched.

Q2) A list of barbers each have a well defined customer processing rate.  When will the nth customer be served?  Assume that if multiple barbers are free, they are filled earliest in the list first.

A2) Nice problem.  The size of N may be huge meaning simulation is out of the question, even for the small input.  For the small input it might be possible to find a period of repetition of patterns of when barbers become available and skip ahead as appropriate, but the large input clearly rules that approach out as well.

While a simulation is not feasible, it is possible given a time T to determine quickly how many people each barber has started serving by the end of that minute, its just (T / barbers_time_to_cut) + 1.  The same formula given T – 1 gives how many people had started being served before this time.  This gives a range, which if it contains N, you’ve found the minute N starts being served and all that remains is to determine which barbers changed state between T -1 and T (which comes from the same formula), and choose between them based on how far N is from the start of the range.  To find which T-1 to T contains N, binary search on T.  If N is before the value at T – 1 T needs to be lower, if its greater than the value at T it T needs to be higher, otherwise you’ve found the value.

Q3) Determine, for each vertex, how many other vertexes need to be removed, for the specific vertex to be on the convex hull.  Consider co-linear points to form a convex hull which touches all of them.  All input vertexes will be distinct integer coordinates.

A3) The small input only has 15, so a brute force trial of every subset using the standard O(N log N) convex hull algorithm (like in TMD.Algo) – would work.  However the one in TMD.Algo throws exceptions if you give it a subset smaller than 3 or perfectly co-linear points, so those cases have to be handled separately.  For each node on the convex hull from each subset, it gets a new potential minimum based on the size of the subset vs the original input size.

The large input is much harder – 3000 obviously can’t be done with an exponential cost algorithm.  However with a fast computer and lots and lots of cores… an O(N^3) approach might work, if it has a sufficiently low constant.  Consider each pair of nodes gives N(N+1)/2 options.  These 2 nodes define a line of the form ay + bx + c = 0 (or a dx,dy vector).  Now every other point can be substituted into the formula (or cross product with dx2,dy2 vector formed by subtracting the point from original point  used to create the dx,dy vector).  Count the number of positive, negative and 0 outcomes (from either case).  Since we are considering every possible point pair, then obviously one of those pairs will be an edge on the ideal convex hull, for one of those points.  For the edge to be part of the convex hull, either all the positive, or all the negative points must be removed.  Thus the size of the smaller of the two options is a potential minima for both of the original two points.  Calculating the line formula is 2 products and 2 additions, then 2 conditional increments to classify.  Giving a constant for N^3 of 1 multiply, 1 add and 1 conditional increment, each of which is potentially only a clock cycle on a modern cpu.  The cross product approach is 3 subtractions instead of 2 additions, but should also be reasonable.

But if your programming language doesn’t optimize well, or you don’t have a bunch of cores available there is an O(N^2 log N) approach, which can be considered slightly inspired by the standard fast convex hull algorithm.

For each point sort all other points by angle relative to that point.  This can be done by first dividing the points into left/right and using a standard sort algorithm on each side using cross product of each point’s vector relative to the starting point as the comparator function.  Once the points are sorted O(N log N) the minimum removal of the original point can be calculated in O(N) time.  For each sorted point, it defines an edge with the starting point, and the rest of the sorted points are either left/right or equal of that edge.  The counts of these left/right/equal can be efficiently calculated in general, by first doing a linear scan of the sorted list for the first candidate edge, then to do the rest of the candidate edges you just have to advance the the indexes in the sorted list that mark the interesting areas, left, right, equal but on same side of starting point as candidate point, equal but on opposite side of starting point as candidate point.  In the process of going through all candidate edges each marked index will never need to backtrack more than one index per step, so they all have a maximum of O(N) operations each to maintain, giving a total of O(N) operations. (An alternative to all this state maintenance is to for each candidate edge binary search to find each of the 4 transition points.  Its O(log N) rather than O(1) per candidate edge, but given the original sort is O(N log N), this is not significant.)

The above algorithm is simply repeated for every input point, giving a total of O(N^2 log N)

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.

Is currently under way.  I’ll do a write up once everything is finalized and official!

So round 1 looks like it is going to be a bit silly this year, 750 to advance per round, 3 rounds, 250 byes, but only 1371 people registered for R1A.  Unless a bunch of people forgot about R1A, everyone with a positive score in R1B will advance, let alone R1C…

I had a poorly written solution to Q1 and a decent solution to Q2, but ran out of time to really think through Q3.  Both my submitted solutions passed, regardless of how wrong my solution to Q1 was in theory…

In the end the positive score criterion came in to play, only 700 people advanced, the rest got 0 points or lower.  I was in 221st, not an amazing effort considering the 250 byes, but not bad.  My rating even went up a tiny bit, 1805.

Q1) Given an inclusive range, determine the greatest number of distinct common digits between any pair of numbers.

A1) I wrote a brute force solution, which I limited to running if the range was 200 in length or less, then for the rest I checked each number against single pair digit switches, if the resulting number was in the range that was a pair to consider, if not I presumed that it could be paired with one of its neighbours, to give distinct count of digits in itself – 1.  There are numerous flaws in this approach, but I couldn’t work out how to actually exploit any of them, as they only overestimated in scenarios where another valid option was better anyway, and seemingly never underestimated.

The better approach (far better) is to create a 10 bit mask out of each input, for the distinct digits present.  Then tabulate the masks.  Result is then the best bit count out of any mask with a count  > 1, or of the ‘&’ of any two bit masks both with counts > 0.

Q2) Given a directed graph  with exactly one edge leaving each node (which can return to self) determine the number of subsets of the graph which can follow there edges for up to K times without the new subset being any smaller.

A2) Two tricks here.  1) K can be huge, but the graph only has at most 50 nodes.  So it is fairly obvious that K > 2500 can just be considered as K = 2500 as any pair of nodes which might eventually map together will have a cycle length each of at most 50, and hence will either never meet, or meet in under 2500 steps.  Indeed this seems like a very conservative analysis, I think they either never meet or since they end up in the same cycle its at most 50 ‘pre-cycle’ links before they meet.  2) We just need to consider whether any pair of nodes eventually maps to the same place.  Once these pairs are found, they transitively form in to groups in which every pair collapses.

Together this means there are at most 2500 scenarios needing at most 2500 (or 50) steps of simulation, which will run quickly.

Once the groups are identified by simulation the the result is the product of the values of size of each group + 1.  This is because for each group either nothing is selected, or at most one element is selected.  Any node which doesn’t find a pair with any other node is in a group by itself, causing a multiple of 2, which leads to the worst case value of 2^50 as expected in the case where every node is independent.

Q3) Given a weighted bipartite graph, determine the minimum edge removal cost to ensure there is no perfect matching.

A3) So I’m still trying to understand the solutions I’ve read here, but basically it considers every non-empty subset of the one side of the graph, determines the cost to disconnect each node in the other side of the graph from that subset, and considers a possible minimum as disconnecting the cheapest x nodes, where x is the number of nodes in one side of the graph – the size of the subset + 1.  For the case of subset is everything, this corresponds to disconnecting one node entirely.  In the case the subset is a single node, it corresponds to disconnecting everything from that node.  In between it covers the other cases like if 2 nodes are disconnected from everything except 1, they can’t be perfectly matched due to pigeon hole principle.

Only thing I’m not clear on is the proof that every non-perfect matching scenario can be reduced to x nodes disconnected from n-x+1 nodes.  The reverse is obvious every such scenario is non-perfect matching, but the equivalence is not so much…

Last chance to get through to round 3 or get a t-shirt, but I was never really in the running for either this year it seems.  Final ranking of 420th with a fairly slow submission time for the first question, probably could have gotten into the top 300, but the trick to solving the second problem seems clearly out of my reach for 3am with 45 minutes.

Q1) Determine the range which if reversed produces the lexicographically smallest string.  If multiple equal results prefer smallest first index, then smallest second index to break ties.

A1) This question was rated for 300pt, so I thought there was going to be some real difficulty to it, so I ended up going slow and careful.

Pure brute force is O(N^3) which for length 2500 is too slow.  But it is pretty easy to get this down to O(N^2).   If there are 2 candidates for lexicographically smallest, unless the first change they make is at the same place, you can trivially choose the one with the earliest change.  This means that once you have identified a starting index which can be improved by swapping with something later, the question is reduced to which later index is best.  Finding the first index which can be improved can be done in O(N) time (because there are only 26 distinct possible values, otherwise O(N log N) would apply).  But given dealing with all the possible second indexes is going to generate O(N) scenarios with a cost each of O(N) to check if they are smaller than the current best, you might as well just brute force finding the first index, which is O(N^2).

There are a couple of corner cases that can come up.  If you actually construct the strings with segments reversed it is best to avoid gathering them all up and doing a sort, it might be too slow as O(N^2 log N) is pretty high.  However doing in-place comparison (like I did) requires care that you remember that the earlier of the possible last indexes will run out of reversed area first, and you need to compare the later reversed part of the larger range to some of the non-reversed part after the smaller range, and not accidentally compare with non-reversed part before the smaller range.

One corner case which I thought existed but seems does not is that if you have a range which when reversed gives the best lexicographical string its ranking could potentially be improved if the character before and after the range is identical, since reversing the larger range still gives the same result, but the first index is earlier.  I wrote code to handle this case, but for the final result, and as a tie-breaker when considering two possible last indexes.  However it cannot happen.  Presume that it did exist, for example that the best lexicographical ordering is …ej……ge… which the j to g range has been selected for reversal.  Immediately this can be shown as invalid as the j to e range produces a better result.  So lets try …ej…….ee… where the j to first e range has been selected for reversal.  Here we know that there is no letter earlier than e anywhere after that first e, because otherwise switching that letter and the first e would provide a better reversal.  This means that j to first e in the ending pair is a worse option that j to the second e in the ending pair, because the reversed sequence will have a longer sequence of e’s before something higher is encountered.

Q2) Given a undirected graph which is specified as clumps of vertexes which are fully connected (where the vertexes in each clump are not distinct from other clumps, indeed the graph is connected). Determine the sum of the all pairs shortest path distances.

A3) So all pairs shortest path distance sum can be calculated in O(VE) for an undirected connected graph with all edges of equal length using a simple BFS.  The problem is that with 2500 vertices, and potentially being fully connected, this is O(N^3) which is too slow.

I thought the trick here was to treat vertices which are only in one clump specially, but on a closer look the problem statement doesn’t actually restrict how many such vertexes there are, even to the potentially silly case where every vertex is listed in 2 identical clumps that are completely overlapped.  Even if subsets were disallowed, this would still have the all but 2 vertexes in common case which is still going to be O(N^3).

The actual solution appears to be to introduce more vertexes.  One which represents each clump.  Then rather than connecting nodes in a clump together, they are connected to their clump vertex.  This doesn’t change the connectedness of the graph, it only doubles the distance between everything.  Calculating the all pairs distance (excluding the clump nodes) is still a simple BFS, just with a conditional for when to add values based on whether you are at a fake vertex or not.  Then you just take the final result and divide it by 2.  This new graph has a number of edges equal to the sum of the number of clumps each vertex is in, which by the definition of the problem is limited to double the number of vertexes.  The number of clumps is also limited to be the number of vertexes, so O(VE) becomes O(N^2) with a reasonable constant.

Q3) Given a set of ranges of indices and the maximum value in each range, determine whether there exists a permutation of the numbers 1 to n which can satisfy all the defined constraints.

A3) With up to 50 constraints, considering how every subset interacts is going to be too slow. However it might be possible to just introduce each new constraint one at a time and check against implied constraints calculated from previous checked pairings.  Information can only be inferred over sections which start or stop at a constraint boundary, so there can be at most 2500 implied constraints.  Therefore the running time should be O(N^4) if constraint interactions need only be considered pairwise in O(1) time.  Point 4 below looks like the most problematic to this, but might be able to be addressed by sorting regions by their implied maximum or similar.

There are several things to consider at a minimum.

1. Two disjoint ranges cannot have the same maximum.
2. A subset cannot have a higher maximum.
3. A range cannot have a maximum value smaller than its width.
4. Multiple disjoint ranges cannot all have maximum values smaller than the sum of their widths.
5. Two ranges which overlap define a union range with the larger maximum.

Two ranges which overlap with equal maximum define an intersection region with the same maximum and the maximums of the non-overlaps are less than specified.

 

Two ranges which overlap with different maximums imply neither maximum is in the overlap.

But getting from there to a working solution is not obvious to me.

A couple of little mistakes on my behalf cost me several hundred placings in the final score board, but I don’t think I was ever going to get a t-shirt this round.  A really fast first problem was probably enough for a t-shirt this time round, with solving the second problem to make it safe.  Solving those 2 in a decently fast time was needed to advance, solving all 3 was only done by a few.

Q1) Given N steps of M conditions (true, false or don’t care), determine the minimum number of times true values have to be changed to false (in a batch) or vice versa to get past all N steps in order, starting from M values which are all false.

A1) This problem boils down to realizing that it can be solved using a lazy greedy.  If it wasn’t for the ‘don’t care’ states, the problem is trivial as every change is defined and you just don’t do any unneeded changes.  The lazy greedy approach is to pretend ‘don’t care’ means the condition of the next step that is something other than ‘don’t care’, but only if you were going to make a change from positive to negative or vice versa for other reasons.  This works because either it gets changed before you get there for free, or you avoid incurring the cost of doing it early when there was going to be a batch at the final step anyway.

So the simple way to do this is with an O(M*N^2) algorithm where at each step you determine what ‘has’ to be done to satisfy true and false conditionals, and also perform any changes of state for ‘don’t care’ conditionals where the future desired value can be put into a batch which is already going to be performed, by scanning ahead each time you see a question mark.  I wrote an O(NM) algorithm by pre-calculating the results of the scan ahead by working backwards through the steps.  This was my first mistake, as I missed a line of code in my pre-calculation loop, and so it contained garbage data, resulting in my wasting a bunch of time debugging.  The second mistake was I wrote a conditional of the form if (A and !B) B = true – which could have just been if (A) B = true.  Then I copy pasted that conditional and changed to B = false, but didn’t change !B to B.  I had to take a time penalty to resubmit because I only thought to double check my copy pastes after I pushed submit…

Q2) Calculate the sum of values which satisfy a criterion within a range.  The criterion is that they are not one more than a prime number, and that there exists exactly one pair of positive integers which sum to that number such that the product of that pair can be decomposed into 1 or more pairs that multiply to give that product, but the sums of which only have one value which is not 1 more than a prime. (Caveat that the value 2 does not satisfy the criterion either.)

A2) Believe it or not, the above description is actually a simplified version of the original description…  With the range being up to 5 million, O(N^3/2) is going to be too slow, so the algorithm needs to be O(N log N) or better basically.

A solution which passed in my room seemingly presumes that if the pairing of 1 and n-1 works, it is a distinct pairing, and no other scenario works.  It then creates a vector of the prime decomposition of n – 1 and uses a bit mask to create every pair that multiply to give n – 1 ( excluding 1 and n – 1), and if any of those pairs sum to give not 1 more than a prime, it fails.  Given the initial assumption, this matches the conditional because n – 1 is not prime by initial check, so 1 + n – 1 – 1 is not prime, so we already have 1 pair which is not 1 more than a prime, finding any more would be bad.  The weird bit however is that this algorithm is not obviously fast enough.  Non-primes are dense so the initial check doesn’t prune much and the bit mask loop means O(2^(log N)) operations worst case per number.  So you might be tempted to say this is O(N^2).  However the bit mask loop’s worst case is for powers of 2, which are not-dense.  The average number of prime factors is in fact O(log log N) which means that this algorithm does indeed kind of run in O(N log N) time after all (generating the prime factors is also a O(log N) component if you precompute a composites table with smallest prime factor – which can itself be done in O(N log log N) using the sieve).

What needs more thought is why the assumption that the distinct pair is always 1 and n – 1.  Why does 2 and n-2 always fail for instance.  We know that n-1 is not prime.   2 and n – 2 added together is n so it is 1 more than a not a prime.  All we need now is one more example.  1 and 2n-4 is 2n-3 which is one more than 2n-4 which is obviously not a prime as it has 2 as a factor.  Presto it fails.  More generally k and n-k.  Precondition of n-1 is not a prime, so the direct sum is 1 more than a prime.  1 and kn-k^2 is one more than kn-k^2 – which is k(n-k) which is not a prime if k >= 2 and again it fails.  The only case that could work is k=1.

Q3) Given a large range, determine how many numbers can be recursively mapped using the following function.  If x is not an integer, no mapping.  If x mod W is 0, no mapping, otherwise f(x) is x/(x mod W).

A3) The range is indeed huge, no way enumerating will work.  First off every positive number less than W is a recursive map to 1.  Every value x where x mod W is 1 is a recursive map to itself.  The number of these scenarios in the range can easily be calculated.

Beyond that is much more complicated.  x where x mod W is 2, where x is even and x/2 is mappable, is mappable, obviously.  2kW+2 works fully recursively because it maps down to kW+1.  But if W is even, W+2 works.  3W+2 is W+1+W/2, which looks like it won’t work…  So it looks like the factors of W need to be special cased in some fancy fashion which is non-obvious.  Maybe I’ll look at this more deeply another day – but not today.

As usual round 2 is pretty competitive, to advance required all 4 small inputs and the 2 easiest large problems, and even then time was a minor factor…  T-shirt was the 2 easiest large problems and one of the remaining small inputs, the harder one to not have to worry about time.

Q1) Given a set of containers of equal size and a list of item sizes and a maximum of 2 items per container, determine the minimum number of containers needed to pack all the items.

A1) This can be solved by a greedy approach.  Take the largest item, if there is another item which fits in the container with it, take it.  If you want you can choose to take the largest of such other possible items for the ‘most greedy’ approach.  But I am pretty sure you can just take the smallest and it makes no difference.  This later scenario makes the problem trivial, as you just walk inwards from the ends of a sorted version of the list of items, advancing when you can take them to count the items.  This works well for the large input since it is an O(N) approach (after the O(N log N) of sorting).  But even with 10^4 items the simple O(N^2) implementation of the ‘most greedy’ approach will run in time with a decent compiler.  Or it could be implemented with a sorted dictionary (specifically one with a ‘find value or prior’ method) for O(N log N), but in this case you have to be careful how you handle multiple items of the same size, since they will have the same key.

Q2) Determine the minimum number of neighbour swaps to make a sequence be sorted such that it has a single maximum, that is it is either all descending/ascending or ascending followed by descending.

A2) I had to go remind myself about minimum neighbour swaps to work out how to do this question.  Even the small input looked tough, brute forcing all possible swap locations and orderings was way way too slow.

So this question boils down to two parts.  Minimum neighbour swaps to make a specific permutation, and deciding which permutation takes the minimum neighbour swaps to satisfy the criteria.

Minimum neighbour swaps to make a permutation is pretty straight forward.  But it requires knowing things which aren’t exactly obvious.  For instance the bubble sort is optimal in the number of swaps, so for the small input you can just use the bubble sort to sort the items, relabelled by the desired index to move them to.  For large input you need to know that a merge sort can be used to count the number of swaps a bubble sort would have done, but with batches rather than 1 by 1, allowing it to run in O(N log N) even though the number of swaps is O(N^2).  Some Google searching found me the algorithm, which is not that complicated.  Every time an item in the merge is taken from the top half instead of the bottom half, you add the distance it would have had to move assuming the halves were joined in sequence rather than being merged into a destination array.

Deciding the permutation had me stumped for a while.  Obviously the largest value in the input is the pivot point, but which elements should be on its left, and which should be on the right?  In hindsight the small input brute force is obvious here, just try every combination of values other than the largest being assigned left, or right.  Once they are labelled, sort the lefts ascending, and the rights descending and that determines the desired permutation to calculate the minimum swaps for.  The large input on the other hand is I think far from obvious.  I think it can be done just by using a hill climb.  For each value see if the minimum swaps decreases by switching sides, repeat until you can’t make it any better.  I can’t prove this however…  This hill climb could be O(N^3 log N) (which is quite slow for N=1000) if switching sides made things better to switch back for others, but I think it is much closer to O(N^2 log N) in practice.

Looking at a solution on the other hand shows another option which is much simpler, and is intuitive, but not obvious.  The idea seems to be that you select the smallest value in the item and then swap it to the closest end.   Lock that one in, and repeat the process.  Can be made to run in O(N log N) although given the large input is still only at most 1000 items, the simpler O(N^2) option is fast enough.

Q3) Given a grid of squares determine the maximum flow from the bottom edge to the top edge, if each square has a capacity a flow limit of 1 and can flow through its edges, but some cells have 0 flow capacity.  All bottom edges are an input flow of 1, all top edges are accumulated for the maximum flow.

A3)  So if you have a maximum flow implementation at the ready, the small input here is probably not too crazy.  However with 100000 nodes in the graph and each node having 4 connections, and a potential maximum flow of 100 it will need to be the Ford Fulkerson algorithm with its O(E max(f)) running time as anything O(VE) or worse will run way way way too slow.

The large input however has a grid height of 10^8 which ensures the O(W^2 * H) Ford Fulkerson approach is implausible.  However there is a limit of 1000 blocked out areas, which means there is only at most 2000 different interesting positions in the height.  However even O(W^2 * count_interesting(H)) is pretty slow and determining how the flow graph looks even for that is tricky.  I am not clear on how horizontal elements can be safely coalesced to give edges with maximum flow greater than 1, because there is a limit to how fast a given flow can migrate left or right, and so you would have to ensure that everything that was coalesced can make it to the next area in time rather than just blindly coalescing everything which is horizontally connected.

To discuss the bit I think which is interesting (but probably not sufficient to solve) is how flows can migrate left or right across a distance.  If there are 4 adjacent flows entering an ‘open’ area, one of them can migrate to anywhere after one cell down as it can flow across all the empty spaces.  Then after the second cell down another can join it, then 3rd can move after 3 and so on.  These would probably be represented with cross links in the graph with a specific capacity dependent on the height difference between the current position and the next.  If there are 2 ‘streams’ coming down to an open area these links would be set up so that flow can’t go both directions.

Q4) Determine the worst case for the number elements in the tries created by splitting the input works in to k groups, then determine how many ways this worst case can be performed.

A4)  Small input is pretty easy here, only 4 groups and 8 items,  gives only 2^16 base scenarios to consider in a pure brute force.  From there eliminate the ones where any group has no elements, the build the tries and sum the counts and if worse reset counter to 1, if equal increment counter, otherwise ignore.

The first part of this question is actually quite easy, just count how many times each substring exists in each word, choose the smaller of that and the number of servers, sum all those values and that is the worst case.  Basically this just states that any given substring can always be distributed amongst the servers to potentially be counted a number of times equal to the number of servers.

The number of ways that it can be done is a much more difficult problem.  How many ways a given substring could be distributed amongst the servers such that it is spread out as much as possible is a fairly simple combinatorics question, but you can’t just multiply these together because they have correlations because the shorter substrings have to match the servers of their corresponding longer servers.

Trying to reverse engineer the logic from reading a solution is beyond me right now, so I think I will leave this question for another day…