TCO14 R1C

So, again I didn’t need to compete, which was good because my weekend was already very very busy…  2 easy questions this week, with 750th place scoring almost 628 points.  This time about 230 people got all 3 problems out in time.

Q1) Remove duplicate letters from a string, leaving the first instance.

A1) Even with the length limit of up to 1000 letters only the really silly O(N^3) solution  would run too slow.  Simple boolean array for seen and add characters to a list if they haven’t been seen yet then convert character list to string for return.  O(N) – very simple.

Q2) Count the number of multiples of 3 (but not 15) and 5 (but not 15) and 15 in a large range.

A2) There is always 1 multiple of 15 and 4 of 3 but not 15 and 2 of 5 but not 15 in the range n=15k to n=15k+14.  Thus take the modulus of the start and end in order to move them up and down to a 15k and 15m-1 value respectively, then hand code the start/end sections and add the results to m-k, 4(m-k) and 2(m-k).

Q3) Given a random walk of length n, what is the expectation value for the number of distinct locations it steps on, including the starting location.

A3) So with n up to 500, there are 2^500 different random walks possible, so brute force isn’t going to work.  The best of my initial guesses was to do this as a recursion on the average width after k more steps with current location x and a to b already painted, averaging on either the walk left or right.  This gives O(N^4) which is too slow and way too much memory, but the actual location x doesn’t matter, instead a and b can be normalized as distance to left edge and distance to right edge.  This gives O(N^3), which is feasible for run time, but the memoization table would exceed memory limits.  Even using some symmetry like if distance to left is greater than right we can flip them without loss of generality, I am pretty sure memory usage cannot be made to fit.

But this does give me another idea.  If we could get rid of one of left and right, O(N^2) space would be easy to fit.  This leads to the idea that memoize over remaining steps and current width where the current location is at one edge.  In this scenario the recursion would have 2 possibilities.  50% chance of growing width by one and reducing remaining step count by 1 and some other chance of not changing the width, but reducing the step count by k.  This requires the computation of the number of ways to choose a random walk which stays strictly in a given width starting from the edge of that use up all remaining steps, or lesser steps which end up at one of the edges of the width.  Using precomputed combinatorics tables, I think this can be calculated in O(N) time, giving the result needed, but the details are more complicated than I think I could have worked out in competition.

Turns out that I really got lost on this one, because there is a much simpler solution if I had of stuck on back where I started.  The simple O(N^3) space and time solution can be made to work by using a dynamic programming approach instead of recursion with memoization.  In this case you can use two O(N^2) size arrays and switch between them to calculate each number of steps remaining, since the recursion always decrements steps remaining by exactly one.  The final generated table contains the answer needed.

GCJ14 R1A

Looks like it was pretty competitive to qualify in this round.  With two questions that were not that difficult and one which was quite unusual and challenging the top 1000 were defined by getting both of the first 2 questions completely in under 2:15.  The third question was unusual because it was based on randomness to the point that there was a chance you would get it wrong even if your code was as good as it could be.

Q1) Given a set (no duplicates) of binary representations of equal length, determine if there exists a bit flip pattern which can be applied to all of them such that they become set equal to a second set (no duplicates) of binary representations of same size and length.

A1) The actual wording of this question was quite involved and I suspect would hide how easy this question is to many.  The small input was limited to up to 10 bits in length, so a brute force of the 2^10 bit flip patterns could be tried.  Large input however went to 40 bits to ensure such an approach wouldn’t work.

Looking at the other constraint however, the number of elements in each set, that is limited to 150, so a O(N^2) is clearly feasible.  Since every element in the original set has to map to an element of the target set, obviously at least one element in the original has to map to an element of the target set.  So take one element of the original set and determine the bit flip pattern which will work for each member of the target set.  Then for each of these up to 150 patterns (rather than potentially 2^40) the set equality can be tested.

For a nice compact solution code, the bit patterns on input can be parsed into 64 bit integers.  Then the bit flip pattern can be represented as another 64 bit integer, which will be applied using xor.  In this version generating the (up to) 150 patterns is as simple as calculating the xor of one element of the first set with each element of the second.  Each element of the target set can be placed into a set object, and the set equality (since we already know that they have the same number of elements and that xor with a pattern is a bijection, so there won’t be any duplicates generated) is as simple as checking that every value in the original set xor’d with the pattern value is a member of that target set.

Q2) Given a connected acyclic undirected graph, determine the minimum number of nodes to remove to be able to make it into full binary tree (where every node other than a leaf has 2 children for some choice of root).

A2)  Again the small input invites brute force with only up to 15 nodes.  The large input of up to 1000 nodes is more interesting.

With a limit of 1000 nodes O(N^2) is acceptable, and this is not too difficult to obtain.  Choosing each of the nodes in turn as a possible root node, a recursive solution taking two parameters, current node index and previous, can traverse the tree in O(N) time.  Specifically the recursion is the maximum nodes which can be kept – the final answer then being the best of each possible root subtracted away from the total number of nodes in the original graph.

The recursion is to consider every edge of the current node which doesn’t connect to the previous node.  Recursion down those edges will return a set of values.  If the set is 2 or greater, choose the largest two and return the sum, plus one for the current node.  Otherwise just return 1, since only this node can be kept.  For each recursion run from a root this obviously linear in the number of edges. Each edge is only considered twice, once on the way out and again to be excluded at the next level down in the recursion.  Since there are no cycles in the graph, the recursion trivially terminates when it gets to a node with no connections other than to the previous node.  Since the graph is acyclic and connected the number of edges equals N – 1 and so the total running time over all recursions is O(N^2).

Of interest to me here was whether the problem can be solved in O(N). The recursion itself invites a memoization over previous and current, which has O(N) states, but a simple star type graph, shows the total time in this case is still O(N^2) because the centre node of the star can be arrived from each of the leaves and has O(N) exiting edges which must be considered.  Even with the trivial optimization of not calling the recursion if there is only 1 candidate which fixes the basic star case, slightly more complicated star type graphs are still O(N^2).

I think I have a solution, which unfortunately complicates the algorithm a bit.  The idea is for each node to gather the (up to) 3 highest values of the recursion which have it as the previous node.  So we start by performing the standard set of recursions, but rather than simply taking the best 2, and memoizing the sum we take a slightly different set of rules.  First check if a memoization value for current node exists.  If not, recurse as normal, but store the 3 highest values and the previous index in the memoization for the current node, rather than memoizing against the sum against the current/previous pair.  If a value does exist in the memoization table but the table entry also contains a valid previous index which is not the same as the current one, call the recursion specifically for that edge, and replace the smallest value in the memoization table if appropriate, and mark the previous index in the memoization table as invalid.  Now there are up to 3 largest values in the table, and we can select the 2 largest of those are not for the previous index.

So, the memoization table contains O(N) entries, each of which get updated at most twice.  Since it is clear that the recursive calls made are only a subset of those made by the original algorithm, it will terminate.  The claim that it is has a total run time of O(N) is slightly trickier.  The first time a specific value in the memoization table is calculated, it could involve O(N) calls to recursion, but because the memoization is stored keyed by nodes instead of by previous/current pairs it won’t potentially be rerun for multiple different previous nodes, which is what caused the O(N^2) logic in the previous version. Basically each node may be visited once for every edge it has, but the total work performed over those visits is proportional to the number of edges it has.  Since each edge connects 2 nodes, each edge in the graph might be considered twice, but not repeatedly as in the original algorithm.  This makes the total run time proportional to the number of edges and hence total run time is O(N).

Q3) Given 120 examples of permutations of the numbers 0 through 999 where each one was generated either by a correct, or incorrect random shuffle with a 50% chance, correctly identify at least 109 of them.  Initial state before shuffle is ascending order and the incorrect random shuffle performs one random swap for each index in order from first index to last, with a randomly selected index which is selected amongst all indexes. (As opposed to correct which only selects from current or higher indexes.)

A3) Since the incorrect shuffle has as a subset of its possible swaps all of the possible swaps performed by the correct shuffle, there is no pattern which is ‘obviously’ only the output of the correct shuffle.  Also since every permutation is a possible output of the correct shuffle there are none which are obviously only the output of the incorrect shuffle.  Therefore the best you can do is come up with a heuristic which tells you something about the probability of a permutation being from the incorrect shuffle and hope that it can managed to identify 109 out of 120 a decent percentage of the time.

I think the key component of this problem is actually writing a program to perform the incorrect shuffles so you can look at the probability distributions.  One aspect of a correct random shuffle is the probability of index i being k should be equal for all valid k and i.  If you were to run 1 million shuffles for instance, there should be approximately 1000 cases of any given index i being equal to a specific value k.  Running 1 million incorrect shuffles, takes a while, but not so long as to rule out doing it once for every time you submit the problem set.  Indeed this naturally leads to an approach of generating this table, and then for each input looking up the index and value for the 1000 elements, and calculating a product of the ratio of the value in the table to 1000 (to avoid over/underflowing double) for each lookup.  The higher the result the more likely it is from the incorrect shuffle.  It might seem at first glance that a threshold of one is appropriate but the calculations are more complicated than that and they are effectively overlapping distributions where you want to choose a threshold to minimize false positives and false negatives. Potentially better luck can be had by taking into account the fact that things are generated with equal probability of correct or wrong and instead sorting the scores and giving out the highest half scores as being incorrect and the lower half as being from the correct sort method.

I found this approach to be somewhat cumbersome, and 1 million incorrect shuffles is 1 billion random number and swap operations, which is a lot of CPU time to be chewing up every submission.  So I had a look at the generated tables and tried to come up with a formula which approximated their outcome with minimal computation cost.  I came up with if value <= index return 1.0, otherwise linearly interpolate 1.3 to 0.7 for values between index + 1 and 999.  Using this and some sample testing I ran on my machine with a bunch of randomly generated problem sets I was managing to get a >93% success rate at identifying individual permutations correctly with an appropriately selected threshold.  This may only be 112 out of 120, but it does provide a pretty decent chance of getting past on any given submission.

TCO14 R1B

Since I got through last round, I didn’t have to stay up all night this weekend – which was good since I was pretty tired already!

43 people solved all 3 problems – >300 2 and the 750th cut off was 196 points, so at first glance the problems look like they might have been more difficult than last week.  The number of people with a point score in the >190 range was almost 1400 – so a small time difference on the first problem was a big difference in placement.  At first glance I thought 196 points was a pretty low score, but it turns out Q1 was only worth 200 points this time, so it truly was a race to qualify if you were unable to solve either of the larger questions.

Q1) Given a sequence of ‘good’ and ‘bad’ and a value for each, determine whether the running sum is ever negative (‘bad’ value is subtracted, ‘good’ is added).

A1)  Such a very very straightforward question here, I can see where the rush came from. 4 trivial lines of code will get this done…

Q2) Given a rectangular grid of cells, determine the minimum number of horizontal or vertical lines (which extend the full width/height each) which will ensure all ‘wolf’ containing cells are separated from all ‘sheep’ containing cells.

A2) A big step up in difficulty here, reflected by the 600 point score I guess.

A simple starting point is every wolf adjacent to a sheep implies a line.  With a 16×16 grid brute force is just out of reach with there being up to 30 lines.  However the limit of only 16 is suggestive when if the problem was was an easy polynomial DP type solution it would probably allow up to 50×50 grids.

So, one approach is to try all 2^15 options for one dimension and then ‘as required’ add lines in the other dimension.  This ‘greedy’ approach of putting off adding lines as long as possible, seems reasonable when there is only one dimension of consideration.  Alternatively if that seems too risky there should be a simple DP of minimum number of lines needed for the first k columns with the last line at column x, however the running time is starting to get a bit risky at 2^15 * 16^3 (requiring some pre-computing to get it down to that low even I think…).  The as need approach (looking at someone else’s solution which passed) seems like it can be done in 2^15 * 16^2 operations which is much safer, this still requires some care to avoid accidentally getting an extra factor of 16.

Q3) Given a tree of n nodes where each node other than the first specifies its parent, determine probability that the kth ‘bird’ can land on the tree if they random walk down from the root to avoid having more than 1 birds on a node and fly away if the final child they arrive at is occupied.

A3) So my first thoughts about this problem was that it was a simple ‘calculate probability of kth bird landing on each spot using probability that each spot is filled as of k -1th bird’, and accumulating up from the no birds scenario, but this doesn’t work – because of correlation effects, there are cases a simple method like this will count that can’t actually happen.  The probability of landing depends strongly on the number of birds that have passed through a given child.

Instead you need to calculate the probability the kth bird will land if k-1 birds have already passed through a given node.  Boundary conditions are If k = 1, then 100 %.  If the node has no children, then 0%.  Otherwise binomial coefficients are involved for each child and the subset of k – 1 which went down that child, plus 1 for the current bird.  Basically given the c children, what is the probability of n out of k – 1 birds go down any specific child is multiplied by the chance n+1th bird will land if n birds have already gone through that child.  This is then averaged over the children.

I suspect I wouldn’t have solved this problem in time, the strong dependence in the probability on the number of birds is a bit deeper into probability theory than I grasp intuitively.

GCJ14 Qualification Round

So, I didn’t compete in this, but plenty of people did.

20595 people qualified with the minimum 25 out of 90 points. 1737 people got 90 out of 90. ~25500 people submitted at least one solution.

Q1) Given 16 distinct numbers arranged in a 4×4 grid, and a selected row, and the numbers after a reshuffle and another selected row that was picked, determine either the one number in common, or return ‘Bad magician’ if there is more than 1, or ‘Bad volunteer’ if there is less than one.

A1) I remember learning this magic trick as a child, although it was in the context of a deck of playing cards rather than 16 numbers.  But that seems neither here nor there – the code looks like it should be pretty simple either way.  You don’t even have to parse the 4×4 grids into 2 dimensional arrays, since the input gives you the selected row before the grid, so you can just only read in the one row which matters.  Then given the 2 4 element arrays, you can calculate the result using a pretty straight forward nested loop – or you can be lazy and just add the arrays to standard Set data types and ask it for the intersection.

Q2) If you have a base earn rate of 2 cookies per second, and buying a cookie farm costs C  cookies and increases your earn rate by F cookies per second, and have a target of X cookies, what is the shortest possible time to get to your target.  Earn rates and buy times are not based on integer time, can be any real number.

A2) So my first instinct looking at this question was pretty poor – I saw finding a minimum on a function which seems to fairly obviously only have a single turning point in the range of positive numbers of cookie farms bought.  This naturally made me think ternary search.  Which would work, but is completely pointless – because calculating the time to win for a large number of farms does almost all the same work as calculating the time to win for every smaller number of farms, so performing a ternary search is just a waste.  Also the upper bound of the ternary search needs to be defined, which is not trivially obvious.

So the simple solution is to have a running total of how long it takes to build n farms, and for each one, compute how much additional time to get to the target.  Once the total starts getting worse, just return the best found.  The running time of this is O(B) B is the number of farms which need to be built.

The size of B is an interesting question itself.  We can determine when the turning point is going to be by an equilibrium equation.  X/(BF+2) = C/(BF + 2) + X/(BF+ 2 + F)  For B smaller than this, it is faster to build another one, and for B greater, it is slower (for constraints of X/C/F all being positive at least…)

Solving for B:

X (BF + 2 + F - BF - 2)/(BF + 2 + F) = C
BF + 2 + F = XF/C
B = X/C - 1 - 2/F

Interesting here is how insignificant F is.  This is because a high F lets you build everything quicker, not just the final target, so if the starting rate had of been F rather than 2, it would have been completely irrelevant except as a scaling factor of the total time.

Since C is >= 1 in the problem statement, O(B) is practically O(X).

However, now that we have exact number of farms to build, interest turns to whether the solution can be done in O(1).  This becomes a problem of evaluating the sum of 1/(ax+b) for x = 0 to x = B.  This seemed vaguely related to the Harmonic sequence sum (a=1, b=1), which I provide a reasonably fast implementation in TMD.Algo, so I suspected it was possible.  Wolfram alpha told me that it was (digamma(b/a + B + 1) – digamma(b/a))/a.  So if you happen to be programming in a language which provides digamma evaluation, you are set.  If not, you will need to write it yourself.  Wolfram alpha provides formulas for small and large X, the large X one bearing a striking resemblance to the Harmonic sequence sum I implemented for TMD.Algo.  The trick here is that digamma(b/a) is digamma(2/F) which can easily be in the range of 1 to 2 which is probably its most tricky area to approximate.  This is especially difficult because the digamma passes through 0 in this vicinity, so the recurrence relation digamma(x+1) = 1/x + digamma(x) is going to end up subtracting very similar numbers, resulting in significant relative error.  But since that is only near 0, and if small B is handled separately the digamma(b/a + B + 1) term should be dominant enough to swamp the error.  So yes, O(1) is plausible, if you are happy considering digamma as O(1) when its implementation will probably involve at least 5th order approximation functions to get sufficient places to fill a double precision float.

Q3) Given an RxC board and M mines, determine if they can be placed such there exists a location where a single click reveals all non-mine squares, using classic minesweeper rules where 0’s auto expand in a cascading fashion.

A3) This problem by far had the lowest success rates.  Which is interesting because the a maximum of 5×5 it is actually plausible to brute force the small input.  Try each of the 2^25 patterns, throw away the ones which don’t have M mines (to avoid implementing a combination generator), then for each of the rest, calculate the numbers and ensure all numbers are adjacent a 0 and all 0’s are connected (flood fill count vs total 0 count for instance), return the first one you find, with any one of the O’s marked as the click location.  This is  worst case >125million instructions, which is quite a few given the 200 test cases, but given the memory locality it should be plausible for any language without excessive overhead.

More interesting is doing the problem without brute force, as is needed for the large input.  This isn’t hugely difficult, but the number of corner cases is significant.  It is convenient to write a transpose function so you only have to deal with the cases of R >= C. (And remember to transpose back if needed when you are done.)

From there there are several cases which need special handling.

  • M = RC – 1.  Here the solution is, fill in everything and overwrite one of the mines with the click location.  Handling this scenario first is useful.
  • C = 1.  Fill all the rows until you reach M, and then put click location in the last row (or anywhere not next to the mines).
  • C = 2.  Here M must be even and RC-M must be at least 4.  If those are true, then simply fill every row until you have M mines, and place click location in the last row (or again anywhere not next to the mines).

Which leaves the general case C >= 3.  C = 3 itself has some specialness but it can be treated under a single code path with the rest easily enough as far as I can tell.  For convenience, define L as RC-M – the left overs.  If leftovers (L) is >= 3C it is almost as simple as just filling from the top, left to right.  The one case which needs handling is L % C = 1, in this case the one left over on the right is not adjacent to a 0.  This can be solved by moving the mine next to it, down one row and all the way to the left.  This newly placed mine is fine so long as it is on the 3rd last row or earlier, hence the condition of >= 3C.  In fact we can extend this condition to L >= 2C + 2, since the first problematic scenario is L = 2C + 1.

In fact, L=2C is trivial, so our first step is to fill everything except the last 2 rows.  If L = 2C+ 1, we remove 3 from the 3rd last row, and put 1 in each of the first column of the last 2 rows. This pattern of switching 3 for 2 is one of the basic steps we can use from here on. However, this only makes sense if C >= 4 which brings us to how this code path can be made to work with C = 3.

So, what values of L are clearly impossible?  L=1 is fine, we covered it first up. L=2 is bad, there is no way that only 2 spots can exist with either of them being a 0 (excluding C = 1 as all of this discussion here will). L=3, same.  L=4, this is possible in a corner so long as C >= 2.  L=5, again no way.  L=6 works with an edge which allows the 3×2 empty rectangle. L=7, again impossible.  L=8 has two options 4×2 on an edge or a 3×3 in a corner with the opposite corner taken out of it.  So why is this important?  Because if C = 3, L = 2C + 1 = 7, which is a known impossibility, so we can test for known impossible values of L before  starting the general case logic.

So, this leaves handling of L < 2C and L != 2, 3, 5 or 7.  Starting from having filled in all but the last 2 rows, the first operation is remove 3 from row 3 and add 2 each to the last 2 rows.  This gives 2C – 1, although it only is in a valid state if C is at least 5, but again C = 3 this is 5 and C = 4 this is 7, both of which have been excluded.  Now put the 3 back in the 3rd row, and remove the right most one for each of the last 2 rows.  This moves us to 2C – 2, and this time it is valid for C >= 2, which is all those under consideration.  Repeating the first step gets to 2C – 3, but this time only valid for C is at least 6, but again smaller C values are excluded by the L being 3 or 5 or 7.  These steps can continue to be alternated, decreasing L by 1 until the desired target is reached.  In every case the click target is the bottom right corner.

Q4) There are 2N distinct numbers selected from 0-1 exclusive, half the numbers are given to player 1 and half to player 2.  A turn consists of player 1 announcing a number, player 2 selecting a number, and player 1 winning a point if their number is actually greater than player 2’s.  Player 1 is it a disadvantage obviously, so they are considering cheating.  They would cheat by first looking at all of player 2’s numbers at the start of each game, and then potentially lying when announcing the number, knowing that in this specific game the number comparison is confidential, only the result is public, not the specific values that went in, and that player 2 will be playing to maximise their score.

A4) This questions problem statement is a bit of a mouthful, you would be better to just go and read the original…

So this problem is interesting, in that what I think is the hardest part of this problem is also the easiest, and that is ‘what is the ideal strategy’ for the non-cheating version.  Its the hardest in that I can’t come up with a viable proof in the time I allotted to considering it, but it is seemingly pretty easy to guess.  So first off player 2’s strategy is pretty obvious.  If they can win, they will play the smallest number which wins, if they can’t win, they will play their smallest number remaining.  Player 1’s strategy, I don’t know, does it even matter?  Just playing them in sorted order seems reasonable.

Speaking of sorted order, sorting all the numbers for each player is a good starting point.  For calculating the non cheating version consider each of player 1’s numbers in order, and walk up player 2’s as needed. Once you find a player 2 value greater than player 1, player 1 loses that point and increment both indexes.  Once you run out of player 2 values, player 1 wins all remaining plays.

For the cheating version first we need to identify how you can cheat.  There are 2 ways, one which is more obvious to me than the other.  The first is that you can increase the number you announce until it is just smaller than the opponents greatest number, to force them to beat you using their largest value, rather than potentially a smaller value.  The second is that if you can beat their smallest value you can announce a value of 1 minus epsilon (since the values are all 0 to 1 exclusive, you can always announce a value higher than their actual highest value) and your opponent then plays their smallest value, which you beat, just as you stated you would.  They are both important, but this second one has the most obvious consequences.

To calculate the cheating win, take the sorted lists and compare the first values.  If player 1 is greater than player 2, player 1 wins this round and both indexes advance (by using cheat method 2).  Otherwise player 2 wins this round, but by using cheat method 1, player 2’s largest value is the one which will be discarded, so only player 1’s index advances.  Repeat until all player 1 numbers have been considered.

TCO14 R1A

So the reschedule actually happened this time.  For a moment I suspected it might not as my client broke at room assignment time, had to log out and in again.  I have been sick for the last 4 days, so I wasn’t looking forward to even more 4am nights if this one had been cancelled as well.

750 to advance… Turned out to be pretty easy looking questions with 750th before challenge phase being 500points, almost 200 people submitted something for all 3 problems, including myself.  Been a long time since I submitted a 1000pt problem, although this one did seem pretty easy…

Challenge phase had a few successes, but not a huge number.  750th shifted slightly to ~495 points, and the number of people with all 3 still submitted was almost 140.

System testing took out another chunk, but I survived unscathed.  59th.  Even assuming all 250 byes would have beaten me, that is a decent placement…  Just over 100 submitted all 3 problems successfully.  750th place dropped down a tiny bit to 484 points.

Ratings took forever due to a glitch with the display of the results (seems the results were not affected much at a basic glance at least…) but I am now 1882 – which is a new personal best.

Q1) Given the ability to sort L characters and discard any characters after those sorted, return the lexicographically smallest result given an input string and any number of uses of this ability.

A1) So, I was a bit slow here, spent too long trying to decide whether the greedy approach was right.  Turns out it was.   So sorting the last L characters then moving one character forward, repeat until getting to the front, carries as many alphabetically early characters forwards as is possible, and since shorter strings compare earlier, truncating the rest is always a win.

Q2) Given a string S and the ability to permute it such that the index of a character doesn’t move by more than D, determine the lexicographically smallest result possible.

A2)  Again greedy, but this time I was more confident.  Greedy approach is to take the smallest character, at the earliest index available, to use as the new letter.  Exception being if there is a letter that is still unused which is D characters earlier than the current index, in which case it can’t be put off any longer, and must be used now.  I used a simple search the 2*D+1 locations for each output index, but I saw one solution which was O(N log D) rather than O(ND) by using a sorted set for the letters under consideration.

Q3) Given a set of lamps controlled by switches, which might also potentially toggle one or both of their neighbours, but always toggle their target lamp, determine the worst case minimum number of lamps that must be on.  Lamps are in a line, not circular.

A3) So, the description of this question is a bit awkward, but the examples provided were surprisingly useful.  They clearly showed than a sequence of YN(on off) or NY(off on) had a worst case of 1 light on.  A sequence of NN or YY had a worst case of 0.  So a greedy approach of trying to get as many YN, NY pairings as possible seemed sensible.  Except the final example didn’t work.

I took longer to get it than most, but I did get there in the end.  The missing case is ‘YYY’, This can be wired up such that at least one of the lights is always on.  Seemingly a greedy approach may still work from here if written carefully, but at this point I decided enough was enough with the greedy solutions, so I wrote a basic DP where the best ‘worst case’ for the first n lamps was either that of n-1 lamps, or n-2 lamps + 1 if NY or YN or n-3 lamps + 1 if YYY.

The fact that there are no other scenarios which need considering is not exactly obvious. But I did prove to myself that YYYY worst case is 1 and YYYYY is also worst case of 1, so I was pretty confident.

GCJ 2014 Qualification Has Started

Registration is open until the qualification round is finished, but you will probably want to leave yourself some time to actually do the problems, so I suggest taking a look sooner rather than later…

TCO14 R1A failed to happen last weekend, so it was rescheduled for tonight – I’m not sure what the registration time requirements are for TCO this year, but it might not be too late…