Month: May 2011

So like last year, I scraped through in R1A with only 1 out of the available questions solved.  But this year I was a bit faster, so I got 655th rather than 800+.

I was actually very close to a respectable score – an off by 1 which took me almost 2 hours to find… *sigh*

Q1) Given an inclusive upper bound on the number of games played today (and at least 1 game was played), with an ‘exact integer’ percentage win rate for today of Pd and an ‘exact integer’ percentage win rate for all time Pg, is the scenario even possible?

A1) The large inputs put the inclusive upper bound at 10^15 – which seemed daunting at first, but fairly quickly I discovered a short cut which I thought made it irrelevant…

First we can rule out a couple of obvious scenarios – if Pg is 100% then Pd must be 100% or something is wrong.  Similarly Pg of 0% implies Pd of 0% or again we fail.  For me the next thing I realized was that if the inclusive upper bound was >= 100 then the option of 100 is available – an important option in the presence of percentages.  In this case every value of Pd is valid.  In that case all that remains is to consider whether Pg is valid…

Pg being valid is actually very simple, so long as it isn’t 0 or 100, we can add so many games prior to today, that today becomes irrelevant, other than to serve as a tiny modulation factor which needs to be compensated for to make Pg an exact integer.  This applies regardless of whether the number of games today was 100, or much smaller.

Final scenario is where the inclusive upper bound doesn’t include 100.  This is less than 100 options to step through, so why not!  For each value of n, we check whether n*Pd is an integer, or similarly, whether n*Pd = 0 mod 100.  If we find a match the situation is plausible, if not then the situation is invalid.

So as I alluded to earlier the upper bound max of 10^15 isn’t a problem, 3 if statements take care of all scenarios >= 100.  However when I went to run my code on the large input file, it crashed!  I hadn’t noticed exactly how big the upper bound max was, and was using int.Parse.

Q2) In a variant of hangman where there is no way to lose, just a score that gets worse the more useless guesses you make, you are choosing words from a dictionary and your friend is playing to a specific strategy.  You want to choose the word which will give your friend the worst score – if there are equal options the first word in the dictionary is the one you take.  If the strategy can be described by a permutation of the alphabet, where each letter is guessed in turn unless there are no dictionary words which match the previous guesses which contain the letter, in which case the letter is skipped, given a list of these permutations and the dictionary, what word should you select?

A2)  A very wordy question (pun not intended!), and for the longest time the question text itself was self-contradicting.  Large input had a dictionary size of 10k words and up to 100 permutations to try for each dictionary.  Maximum of 10 test cases meant that it wasn’t entirely insane though.  A brute force attack requires iterating over the dictionary, for each entry in the dictionary – and performing this multiple times even – it was clearly not going to work in time O(D^2*P) is billions upon billions of operations for the large input.

I spent a while considering whether there was some dynamic programming approach but eventually came to the conclusion that I was just trying too hard, and that an O(D*P) solution would be okay even with a rather high constant multiplier.  So I started implementing.  The approach is not to try each possible word choice and simulate, but instead to simulate all possible word choices at once.

At this point I should mention something which possibly isn’t clear from how I wrote the question above, which is that since the first thing you do in hangman is to write down the full list of blanks, your friend immediately knows the length of the word, so whatever word you select your friend will only consider words of that length.

Put all the words of a specific length in a list, then going through each one determine what its response to the current letter being tried in the strategy.  The responses (which can be represented by a bit field as maximum word length is small) break the words into groups.  Each of these groups is self consistent – if any of those words had been the originally selected word, the group would be same set of words that your friend would consider as still plausible and the basis of the strategy.  Once each group is created you can move to the next letter in the strategy, applying it to each group, splitting it into potentially even more groups which remain self consistent.  All that remains is to keep track of the score for each group, and then select the best score once you get to the end.  Repeat for each different word length, and select the best of the best.

Keeping track of the score for each group is fairly easy, first group has score 0.  If a group response to a letter by splitting into 2 or more groups, and one of those groups contains words that do not have that letter, that group has its score increased by 1 compared to the input group.  Key thing to notice here is that if the response of a group to a letter is to not split, and the words do not contain the letter, the score doesn’t go up – because this corresponds to the scenario where the strategy is to skip a letter, because none of the plausible words contain the letter.

I actually had this all written with almost an hour to go, I even took the time to generate the maximal input file to make sure it wasn’t too slow.  Except it didn’t produce the correct answers.  I was confused, I hunted for potential issues – only found 1, and it was still wrong.  With 30 minutes to go I decided I would write the brute force implementation, just get the points for the small input or if I had time, maybe use it to work out why the proper implementation didn’t work.  But I made copious mistakes in the brute force code – even though it was theoretically simpler, I got it wrong in multiple ways.  After the competition finished, I still had to fix 3 more bugs before it passed the practice small input.  At this point I compared it to my proper implementation, and found a specific test case to focus on.  Turned out that my proper implementation was actually much better, it hadn’t suffered from any of the bugs of the brute force code.  Just a single mistake, iterating over the dictionary of grouping words by length, I hadn’t used foreach, but had instead just iterated over the possible lengths, 1 to 10.  Except my loop stopped at 9, oops!

Q3) You are playing a special single-player card game.  You have at least 1 card in hand at the start, and the rest in the deck – with a total of up to 80 cards.  You start with 1 turn remaining until the end of the game, but each card has 3 values.  T, S and C.  T is the number of additional turns you gain by playing it, S is the score you get by playing it, and C is the number of cards you draw from the deck, if you play it.  You actually know the exact order and contents of both your hand and the deck before you start – determine the maximum score you can achieve.

A3)  This was the ‘hard’ problem and I definitely agree it was far harder than Q2.  Only 3 people got out the large input, and barely over 100 got the small.

The key difference between small and large was of course the limits imposed.  In the small input, C is at most 1, where as in the large input C could also be 2.  I think with the C is at most 1 limit, the problem can be more obviously turned into a dynamic programming problem…

I certainly had to look up the answer here, but the key comes from determining properties of the ideal answer and using those to limit your search space, which would otherwise be huge.  Firstly it is worth realizing that you should always play a T>0 card if you have one available.  Since they give more turns, there is no downside to playing them.  Next is the C=0 cards.  For a given maximal solution, any C=0 cards (which are not T>0 cards) can be reordered to the end.  Furthermore amongst C=0,T=0 cards you will always want to play them in largest score first order.  All that remains is to determine the order of playing the C=1 and C=2 (T=0) cards in between, if they are played at all.

The final and most important trick here is to determine that if you play 2 C=1 or 2 C=2 (T=0) cards, they can be reordered such that you play the one which arrives in your hand first, first.  Finally this gives enough limitations on the search for an ideal solution.  So we have a graph with status ‘index in deck of last drawn card’, number of turns remaining (capped at 80, since over 80 is pointless), the first C=1 card we might yet play, and the first C=2 card we might yet play and the first T>0 card we might yet play.  The transitions on this graph always increase one or more of these 5 values, so it is an acyclic directed graph.  Since there are no cycles you can fairly easily search this graph for the ‘longest path’ from the source, where each edge is a score and each vertex has an end bonus related to maximal use of remaining turns to play available C=0 cards.

To enumerate the possible transitions we have ‘play a T> card’, ‘play a C=1 card’, ‘play a C=2 card’, ‘decide to never play the current C=1 card’, ‘decide to never play the current C=2 card’.  A performance improvement option here is to remove the C=1/C=2 card options if there is a play a T>0 card option, since we know playing T>0 first is never a bad thing (Or alternatively, get rid of all T>0 from the status info and state transitions – presume to have used all the could be in the hand as part of every transition, and in determining the initial status). Use a DFS to generate the graph, as it is going to be sparse and maximum recursion is 80. Also add backwards pointing links because they will be useful for determining the maximum length.

Recursion with memotization will solve the problem at this point.  Starting from the implicit end node which every node connects to via the play of playable C=0 cards, recur across each back pointing link added before, using the edge weight (score increase due to that action) to build upon the result of the recursion.  Memotization to ensure the runtime is fine.

So this one was at a more reasonable time, so I participated.  281st, not as good as I might like, but good enough to get through.

Q1) Given a scrambled list of two item types with a total count of N, and the ability to at most once for each i in 1 to N switch two elements that far apart, determine the minimum number of swaps to order the list, if it is possible.

A1) So, the answer to this question was so obvious that it takes a while to see.  In the case of there only being 2 element types a single pivot sort pass will result in an ordered list.  If you consider a pivot sort where you walk from the outside towards the middle, swapping if both are on the wrong side, walking a specific end if it is on the right side – you can see that it will perform a minimal number of swaps and that every swap will be closer than the last.

Hence it is always possible to sort, and the answer is just the count of the number of items not in the right spot to start with/2.  Or you can simulate the pivot sort, like I did.

Q2) Given a ‘map’ (1 dimensional array) which shows the position of two critter types, which are either grumpy at time t % K = 0 or at t % C != 0, determine the minimum time to get from the left to the right of the map if you cannot by in a cell at a time when its occupant is grumpy, if it is even possible.  Maximum value for K,C and length of array are all 50.

A2) So this is really pretty easy, its a shortest path algorithm, with a small twist.  Because the behaviour of a critter depends on time, each cell needs to be replicated in the graph to represent how time plays a part.  Obviously replicating once for every time step defeats the whole purpose of a shortest path algorithm… but since behaviours are dependent on mod K and mod C, it is pretty obvious that t mod K and t mod C are the only things that matter for a given cells possible future paths.  So each cell is replicated K*C times (or LCM(K,C) if you want to get really fancy, but given the availability of primes near 50, worst case for K*C and LCM(K*C) are pretty close…

So 50*50*50 vertexes in the graph, and 3 edges from each vertex.  From there you just use a priority queue based Dijkstra algorithm and presto, successful solution done.

I on the other hand used a non-priority queue – which for a while I had convinced myself should perform much slower in the worst case.  Shows how rusty I am!  graphs with equal edge distances don’t need a priority queue as a normal queue already walks them in breadth first search order.  Using a priority queue would only make things slower by adding the logarithmic insert/remove cost overhead.  So yeah, in hindsight my algorithm works pretty well…  If .Net had of had a built in priority queue I probably would have used it and only made things marginally worse!

Q3) Define S(x) to be the sum of the digits in x.  Define D(x) to be the recursive application of S until the input equals the output.  Given a range, determine how many of the contained numbers can be represented as y*D(y).  Range constraints: less than 10 billion.

A3) This problem was easy! – unfortunately I only realized as much with 10minutes on the clock, and I just wasn’t fast enough to write it all up.  I was 4 lines of code from being complete. (Although said 4 lines require a little bit of thought each…)  If I had of rushed rather than taking everything at an easy pace I might have saved those extra 2-3 minutes I needed to finish those 4 lines and perform the final debugging.  That would have gotten me in the top 40, which is where I know I am capable of reaching.

D(y) = 9 if y is a multiple of 9 else y mod 9.  If you’ve played around with digit sums before you would know this, if not a short exploration should make it fairly obvious.  So y*D(y) can be decomposed into 9 linear functions, which sometimes overlap.  Includes/Exclusion principle applies, so you can sum, subtract, sum, subtract your way through every possible n choose 9.  That is quite a few equations to write out, but everyone of them is pretty simple – if you could be bothered…

However! Every one of the 9 equations is of the form a*9k+b.  Note that these equations all have constant ‘mod 9’ values and they aren’t all the same.  Hence many pairs don’t have any overlap and so the inclusion/exclusion can be simplified significantly.  It decomposes into 3 pairs and 1 triple. This means you only need 9 base equations, 5 pair equations, and 1 triple equation.  I was half way through the pair equations when time ran out.  Interestingly I found one of the pair equations cancels with one of the base equations, and apparently there are more cancellations because looking at once of the successful answers, they only needed 9 equations and 7 of those were base equations. (So technically I was 2 lines of code away from being finished :P, 1 add and 1 delete…)

So TCO11 kind of crept up on me, wasn’t paying much attention compared to Google code jam.  But here it is qualification rounds 1 2 3 intermixing with the schedule for GCJ Round 1.

I was thinking of entering this round, probably would have been tricky to get through though, QR1 is not usually agreeable to my skill balance.  I signed up for it, but by the time it hit midnight here I decided that I was too tired to stay up another 2 hours until the competition started.  QR2 and 3 are much better times for me, although QR3 is during a work day so, hopefully I get through on QR2.

Almost 1600 contestants competed in QR1 – cut off for 600th place to advance to round 1 appears to be 235 points.  So a ‘fast’ question 1, or question 1 + challenges, or question 2 was the target.  Only 1 Australian through this round – but given the time zone it is hardly surprising…

Q1) There is a group of up to 50 people and each knows exactly how many of them are compulsive liars.  Each makes a claim ‘there are at least n liars’, for a compulsive liar this means there are ‘less than n liars’.  Determine the minimum number of liars, or return -1 if there is no possible correct answer.

A1) So this isn’t a difficult question, although there might be 2^50 possible scenarios for consideration they can easily be excluded in bulk, and exact scenario is not required.  We just need to walk through each possible liar count and determine whether it is satisfiable.

So what is the requirement for satisfiability?  For a trial n, there must be n claims greater than n, and the rest must be less than or equal to n.  This corresponds to the n liars and the N-n truth tellers.  Trivial enough really… probably trivial enough that I would have been too slow.

Some corner cutting options which are totally pointless and just serve to make your answer more complicated include counting the 0 and 1 entries – as those cannot be liars, and counting the N and greater entries – as those must be liars, then performing the walk in between.  If the range had of been larger, sorting entries would allow for an O(n log n) implementation rather than O(n^2) – but it was just pointless in this small input size scenario.

Q2) Given a set of up to 50 integer music track lengths, and random selection from them (where repetition is possible)  determine the probabilities that a given time (T) will be playing each track.

A2) Looks like an interesting question on the surface… seems like it calls for dynamic programming, but with T being up to 80000, need to be careful not to invoke O(T^2) on the DP array population.

At T=0, all probabilities are equal and it stays that way up until minimum track length.  At that point probability of that track drops and the others go up.  So it looks like maybe the probabilities can be linked to when tracks last ended.

At this point in my investigations into the solution I went down a long path of counting the number of ways to be ending a given song at time T.  This was a problem in 2 ways. 1) It produced Huge numbers which were just too large to handle, and 2) it was useless because it didn’t account for the probability of the starting point of each song.  Counting is not a good option, probabilities are better.  I doubt I would have realized this during the competition soon enough, so highly likely I would have failed to get through.

So the correct approach is to ask “what is the probability that a song can start playing at time t?” This is even easier than the counting question. P(0) = 1. P(t) = Sum(P(t-ti)/N).  The probability is the sum of the probability at the previous potential start time for each song divided by the number of song options for playing at that time.  From there the answer is just the sum for each track over each possible start time that would have it still playing at the finish time. (Remembering to divide by the number of tracks that could have started playing at that time.)

Q3) Given a pattern of ‘B’, ‘W’ and ‘?’, where there is always exactly 1 question mark and 0 or more of the other characters, determine the shortest and lexicographically minimal replacement of ‘?’ which makes the sequence have a value of N, using the following rules.  Sequence of length 1 has value 1. A letter alternation increases value by 1, a letter repetition decreases by 1.  The sequence as evaluated left to right must never decrease below value 1.  Further conditions, input pattern is at most 50 characters, and the final value of N is at most 100.

A3) Initially looking at this question I am thinking it must be a joke…

Four scenarios.  1) Question mark is on the end.  Evaluate the pattern start for viability, and then proceed from evaluation end value to target value with directness – empty, alternates, or continuous repeats. 2) Question mark is on the start.  Slightly more tricky, Check for empty, or add alternating on the front until it works (if it is going to at all). 3) Question mark is in the middle.  Hardest case.  Similar to case 2, but target to get back to isn’t empty. 4) Question mark is on its own.  Answer is alternation starting from B until target value reached.

Scenario 3 is the only tricky part.  Given a start and end character, and a target end value and a given start, without ever going below 0, what is the lexicographically smallest approach that yields the correct result.  I suspect this could be done using a list of maybe a dozen or so scenarios which are simply thought through for the optimal strategy, but it can also be turned into a recursion, but one which needs to be evaluated in a fashion which is greedy so as to avoid considering solutions which are known to be way too long.

So with a known start character and start value, we can look at it as a shortest path to specific value ending in specific character.  Adding a character the new state is determined by the old value, the old last character, and the new last character, with the outputs being the new last character and new value.  If the assumption is made that the value never needs to exceed a certain threshold in order to achieve the shortest path, this state space is limited and easily fully explored (only two possible transitions from each spot, which we only need to consider if we find a better answer for that position).  A simple threshold to assume is double the maximum target, or 200 – but I suspect the true threshold is much lower.

So, not a joke after all…  still I think I was more likely to solve it than question 2…

So looks like a pretty big turn out – 10566 qualifiers. 1855 perfect scores – which I was a part of – although in some ways I don’t think I deserved to be.

The 4 problems was definitely more than I could have handled in a 2.5 hour competition (not without less huge insane mistakes at least!) – I actually took more than 5 hours to submit my answers – although I had a lot of distractions and took a few hour break in the middle.  So sure it took less than 2.5 hours to write up the code, but I cannot ignore the value of that break allowing to the answers to mull over in my head.

Q1) Given starting positions for 2 robots and that they can both move at 1 unit per second, and that it takes 1 second to press a button, and a list of integer button positions and who has to press them in exactly the given order, what is the minimum time to complete the required work?

A1) This puzzle was actually portal themed – there was mention of possible cake.  As usual they provided a sample example of ‘one way’ to solve a sample optimally.   I almost wonder whether I should start to assume that any time they say that it is an example of a sub-optimal strategy which just happens to be optimal.

Anyway the question itself is a fairly basic simulation using a greedy algorithm.  At any given point in time the two robots have a target position, which is based on the next button which needs pushing by them.  For a tiny optimization, this only ever changes when they push a button, but given the constraints even on the large input you could probably have gotten away with updating the target every timestep.  Then it just comes down to simulating each timestep.  If a robot is at its target, it doesn’t move.  If it is supposed to push a button it pushes the button and doesn’t move.  A likely trivial mistake to make would have been to accidentally let the second robot push its button in the same turn as the first robot because you’ve updated which is the next button to press but haven’t yet ended the current turn.  Maximum number of turns is something like 100k for the large input, no problems given the 8minutes you have to submit the answer.

Q2) Given a list of pairs which if matched consecutively are replaced by a third (which will never be found in the list of pairs), and a list of pairs that if they are ever found anywhere in a list (except if they are instantly replaced by something in the first list) cause the entire list to be cleared.  Process a list of input characters adding each one to the output list in turn, subject to these rules, print the output list in a pretty format.

A2) At 82% this problem had the lowest small to large conversion ratio – and it isn’t surprising because the small problem constrains the list of pairs to be at most 1 for each case and the large allows up to 30.  This isn’t a performance problem at all, but it does mean that several corner cases just cannot occur.  Writing up my solution for this problem probably took longest of all of them, although I found it easy to solve in theory – I made copious errors during implementation – several of which would have crept past the small inputs if I hadn’t of noticed them in time. (Keeping with the computer gaming theme, this problem is inspired by Magika)

So again this is a straightforward simulation.  If the list is empty you add the character.  If not first check whether the incoming character and the existing last character are a pair in the first list of pairs.  Performance is not a problem, just walk them all, checking both orders (scale optimization is to add pairs a dictionary of dictionaries – but not needed here).  If a match is found, replace the current last character with the replacement and continue loop onto next character.  If not it is time to check whether there is a need to clear the entire list.

Again because the scale constraints are so small there is no need to optimize this using dictionaries, you can just walk every entry already in the list, consider it with the incoming character against every pair provided in both orders.  Obviously this is O(n*k) but k is at most 30 in the large input.  If you do optimize this scenario you would probably do what I did and add a set to keep track of the unique elements in the input list so you can dictionary lookup the next character, and do a set intersection between the dictionary results and the set of unique elements in the input list.  The one thing to be careful of here is that a set is not a good implementation for keeping track of the set of unique elements in the input list, you need a count of each unique.  Without a count, the pair transformations which remove the last element can cause you to incorrectly claim that element is no longer in the list.  In any case, if you find a match, you clear the list and do not add the incoming character.

Finally if neither transformation nor clearing occurs, add the character.  At the end of the simulation loop the nice formatting was trivially achieved using string.Join – but a simple loop with a first loop condition does the job.

Q3) Two boys have a set of items which each have a value.  One boy can’t add – any time he adds two numbers he always forgets to carry the 1.  He also adds in binary… The other boy however can add just fine and wants to create two piles of these items which the first boy will think have the same value, but hopefully do not.  In fact he wants to minimize the value of one non-empty pile, and being a mean boy, give that to the first boy and take the rest for himself. For a given set of values, is it even possible, and if so what is the maximum value the second boy can take for himself.

A3) Looking at the questions, I would say this one gives the first question a run for its money as the easiest question – but the statistics don’t back me up.  I was bemused to see people asking the Admins questions about this question during the competition.  ‘Does the first boy add the items left to right?’ – ‘Yes’.  Addition without carrying the 1 is both commutative and associative, so the order is irrelevant.

First off we note that the first boy thinks A+A=0.  This combined with commutative and associative, quickly shows that the sum of all items must be 0 if there are 2 piles which have the same sum.  The next leap is to see that A+A is the only way to get 0, hence again because of commutative and associative natures any bi-partition of such a pile with sum 0,  has equal values.

So, from there it is trivial.  Second boy gives the single smallest item to the first boy and takes everything else.

Implementation involves proving the no-carry sum is 0.  Afterwards I realized that I could have implemented this using simple xor on the whole number, but I broke the integers into arrays of bools and reimplemented bitwise no-carry sum (xor!) by hand.  Once you prove that the xor of all inputs is 0, sort, and sum the top n-1 elements and return that as result.  Simple.

Q4) Given a permutation of the first N integers, and a single operation which is ‘randomly permute a selected subset’ and acting ideally – what is the expectation value for the number of operations until the list is sorted.

A4) This was by far both the hardest and easiest problem.  The provided sample provided a hint which was both useful and useless at the same-time…  Random simulation looked liable to time-out before convergence, especially for large input and presumed you knew what the ideal strategy was.

So, what is the ideal strategy?  The sample provided a hint that if you have n disordered elements, acting on each sub-permutation cycle independently appeared a good strategy. (Permutation cycle in disordered elements is the smallest set of entries which can be reordered on their own to end up completely ordered correctly.  For example 2341 is a permutation cycle of 1234, as is 2413, but 2143 and 4321 are not as they can be divided into pairs which when switched are in the correct positions.  This may not be the correct definition of a permutation cycle, but I can’t think of a better term to use in this discussion…)

Indeed I could see that it seemed reasonably obvious, that not randomizing a subset of a permutation cycle was inefficient.  I didn’t prove it, but a trial with small permutation cycles agreed with the hypothesis. So I started down the path of dividing the input into a count of the number of each permutation cycle length, under the assumption that the ideal strategy was to randomize each permutation cycle in turn until it was ordered.  At this point I tried some examples – in fact the first example I tried was a cycle of length 3, 312.  However due to some incredibly stupid mistakes (I made 3 in quick succession, but only noticed 2) I incorrectly calculated an average of 2.5 operations to order this cycle.  I then made a completely mistaken leap from this mistaken value to presume that this was further evidence that working with cycles was better than working at random.

So at this point I start breaking out some serious combinatorics deriving the formula for the average number of operations for a cycle of length n, assuming the ideal behaviour of working after each operation was to work with one cycle at a time.  I’m not great with combinatorics, and it took me a while to realize that most of the combinations and permutations and factorials in my formula would actually cancel out, and I wouldn’t be needing to calculate the ratio of 3000 digit numbers to 7 significant figures.  I then made a mistake doing the cancellations and ended up with something again, completely wrong.  It was obvious though, so I started some trials again.  This time on the core piece of my formula which is ‘how many different ways is there for n randomly permuted entries to have a length k cycle which includes the first element.  I was bemused to find that my trials didn’t depend on k, it was always (n-1)! – or 1/nth of the total permutations.  I could see where I screwed up my cancellations now and ploughed ahead with my formula.  I implemented mutual recursion memotization, and hit go.  It was fast, it produced the correct answers for the sample.

At this point I decided to have a look at my memotization tables – I laughed because there, accurate to 7 or more significant figures, was a table which contained ‘n’ at index ‘n’.  I had successfully demonstrated that for ‘n’ disordered elements the sum of the times for each subcycle is equal to ‘n’, which is tantalizingly close to suggesting that advanced strategy was irrelevant. The only thing you have to do, is make sure you don’t randomize something which is already in the correct place (and make sure you do randomize every member of any given cycle, which comes from letting everything else randomize).

So at this point I ripped out my memotization tables and replaced them with ‘if passed n, return n’.  I then realized the obvious, that I didn’t actually need almost any logic any more at all.  The answer was equal to the number of disordered elements in the input.  Counter, for loop, if statement, increment, return result.

I probably would have solved this problem quickly, if it wasn’t for that mistake of calculating 2.5 as the expectation value for cycle length 3…  Instead I wasted almost 3 hours on it alone.  3 hours for 4 lines of code… (ignoring the file parsing code of course!)

 

So its almost halfway over and over 4500 people currently have the requisite 25 points to their name – of course the final testing could still play havoc with a few of them.

A significant change in format this year – previously there was no way to qualify solving just the small input files, solve one problem in full and you are through.

This year there are 4 questions, and you could solve just small input files to get through – indeed I’ve solved them all so baring some catastrophic event there is no way I am not through to round 1. (I also solved the large inputs, we’ll see how the final testing treats those…)  Also, the first question isn’t worth enough points to get through.

So I plan on doing a write up tomorrow once it is all finished, but it is looking to be rather a busy day, so it might get delayed…

Just 2 and a bit days till GCJ11 qualification round now.  Registration is open on the day I believe, so no rush.