GCJ13 R1C

So I am a bit late with this write up, I completely forgot about it…

Cutoff for the top 1000 which advance to round 2, was problem A small/large and problem B small with 45minutes spare.

Q1) Determine the number of subsequences which contain n (or more) consecutive consonants in a given string.

A1) Small input here is trivial, with a small maximum size you can use the brute force O(N^3) approach of considering each starting point, each end point, and checking  each scenario for maximum consecutive consonants.  Large input is size 10^6, so we need to do better than O(N^3/2) in order to run in time.

In practice it is actually not too hard to implement a solution in O(N) runtime – although given the answer can be proportional to O(N^2) we still need to remember to use 64bit integers.  The solution is to use a walking range of length n, you keep track of how many consonants in a row at the end of the range, first by just counting them, then as it walks forwards, adding 1 if the new location is a consonant, and subtracting 1 if the count was previously equal to n.  Each time the current number of consecutive consonants is n, add (length-n-current_starting_index+1)*(current_starting_index-last_successful_starting_index) where you initially set last_successful_starting_index to -1 and update it to equal the current_starting_index each time this calculating is performed and the total incremented.  The use of last_successful_starting_index here avoids double counting when there are multiple cases where the number of consecutive consonants is n.

Q2) Given you can only move along 2D grid in horizontal/vertical direction and each movement has a length of 1,2,3,4… determine a list of NESW instructions to get to any specific point from the origin.  Point is guaranteed to be reachable, and you should return the minimum length path.

A3) Small input was an interesting variation, you didn’t have to print the shortest path, it just had to be less than 500 moves, which makes the problem trivial as any consecutive pair of moves can be made opposing to have a delta of 1 in whatever direction you want, allowing you to step your way from 0,0 to x,0 to x,y, and since x,y are both less than 100, you will get there in less than 400 moves.

Large input however is not so forgiving, the result has to be the shortest path.  I had a few thoughts regarding a greedy approach where you do something like NENENENENNNN to get as close as possible (assuming the target is in the NE quadrant) and then use repeated approaches of ssssswswswswswsnenenenennnnnnnn type to converge even closer.  But I don’t see any way to guarantee that that is ideal.  My second thoughts was that maybe we can ignore the whole 2 dimensional nature of the problem for a bit, if instead of trying to get from 0,0 to x,y we tried to get from 0 to abs(x)+abs(y) we could end up with a sequence of EWWEEEWEW which appropriate use of replacement with NS can get us to abs(x),abs(y) instead.  Which can then be trivially flipped to get to the actual x,y.

This 1D version of the problem seems like it might be simpler.  Reading a solution it actually is definitely simpler.  Find how many steps it takes to go past the target.  Now we go backwards, starting at the destination, subtracting each value off in reverse, if we go negative, we add the next one back on instead.  Ultimately you can see that it must converge to 0.  Now how do we convert this sequence into one that works with 2D?  Using the same number of steps, we subtract off the largest absolute value out of x and y at each step.  This doesn’t converge to 0 quite so obviously, but apparently it does all the same.

Q3) Given a bunch of tribes which have a ‘length’ and move along a line and occasionally attack towards the other side of the line, and succeed if any part of the wall isn’t at least height s (which is potentially different for each team, and changes as time progresses), determine how many time they succeed if at the end of each day the wall is raised to the minimum height that would have stopped any attack made that day (if it isn’t already higher).

A3)  The small data set is a trivial simulation – you only need an array which covers from -200 to 200, and to order the maximum 100 events correctly and handle them happening simultaneously correctly.

The large input is a bit more tricky. 1000 tribes, each with up to 1000 attacks gives up to 1 million events, so if we are still doing pure simulation, we need do better than simulating each unit of the length of the tribe, since that is up to 10^6 and it moves up to 10^5 each move, giving a 10^8 space range and a 10^12 operation count.  I think using an interval tree will do the job, especially since the ranges are disjoint.  We need to handle splitting and merging, the former for correctness, the merging to avoid catastrophic performance.  I think with merging, each operating may match at worst 1000 height ranges –  giving a 10^9 operation count, which is huge, but with only 20 test cases, maybe plausible.

Looking at a solution, I think I needed to make the interval tree a bit more fancy otherwise it wouldn’t be fast enough, but the alternative is easier to implement than a full interval tree.  They don’t use explicit merging or an actual tree implementation, instead they create a list where the first element represents the entire set of distinct start/end locations for attacks, the second the first half of those locations, the third the second half, the 4th the first quater, a bit like a common binary heap implementation.  For each node they have 2 values, ‘whole’ and ‘min’.  ‘whole’ is used to shortcut when an attack area covers a large section – so if an entire node is covered, we don’t have to update all of its children, we just update the ‘whole’ entry, and from then on we use the higher of whole and min of the two children when looking at the tree to find the minimum height in a range, since min may not have been updated because of whole.  This ‘whole’ strategy obviates the need for merging, because it ensures n log n regardless (where n is the number of events) which is trivially fast enough.

TCO13 R2C

Low turnout as usual – only 1032 registered out of ~1900 potential.  With the top 100 through already, this round was always going to be the best opportunity to get a t-shirt, and I was probably close.  I got 258th with just a solution to the first problem  I was slow to implement, a fast implementation time of shortest path would have gotten me into t-shirt contention range.  Alternatively a successful challenge would have got me 150th which is good t-shirt contention.  I was looking at a broken 1000pt solution, which I was confident was broken, when I saw that a bunch of 250pt problems had been challenged and had a quick look at the carnage.  By the time I switched back to the 1000pt and was about to open the challenge window for a try, someone else picked it off first.

There is always next year of course…

Q1) Given an undirected graph determine the minimum number of steps to make 2 specific vertices neighbours where a step consists of taking one or more distinct pairs of vertices which each have a common neighbour, and making them neighbours.

A1) Looking back on this now, I should have realised after the clarification announcement that this question would have a lot of challenge opportunities.  Clarification seemed to state the obvious to me, so I didn’t pay any attention to it, but the 7 challenged solutions in my room all had the same mistake – assuming a step could only introduce one new edge into the graph at a time.

So the solution is straight forward – we need to know the shortest path between the 2 nodes, then calculate the number of steps to make them neighbours.  Most of the quickly implemented solutions used the DP version of all pairs shortest path which is O(N^3) – but given the restriction to 50 vertices this was not an issue.  I implemented the much longer piece of code for a breadth first search (O(N^2) due to adjacency matrix rather than edge lists) for single source shortest path, this cost me a bit of time.

Once we know the shortest path length, the actual vertexes are irrelevant, along that chain we takes groups of 3 consecutive and remove the middle one.  We repeat this phase until we get down to 2.  This can simply be implemented as subtracting floor(number of vertexes remaining/3) repeatedly until there is only 2 left, and counting the number of steps.  I stupidly actually implemented the loop of copying the vertex ids that remain each time into a new list and repeating until the list only had 2 elements – which again cost me time.

Q2) Given a requirement that a rectangular grid of numbers have a ‘peak’ where every value before the peak row is strictly ascending and after the peak row is strictly descending, and correspondingly for the peak column, determine the minimum sum of elements  given that some of the elements have to be specific values. (Up to 200 by 200, but only up to 50 specific values.)  Solution is not always possible, impossible states must be identified as such.

A3) I made a start on this question, but I’m pretty sure I was heading in the wrong direction, so I gave up.  Code required was quick lengthy and prone to mistakes, justifying the extra points (550 instead of the usual 500).  It appears that the correct path was to realise that in the ideal scenario, the 4 corners will be as low as possible.  So you create 4 pseudo answers by numbering starting from 1 (or given value) in each corner, and satisfying all the fixed values.  Then you merge the 4 pseudo answers together to get the smallest possible sum. (For actual details, you’d need to read a solution, they are in-depth.)  Its O(N^3) unlike my original idea which I suspect would have been O(N^4) in the worst case.

Q3) Given a numeric range 1 to n and the ability to make guesses regarding a hidden selected value where each guess is told correct, left or right – determine the maximum probability you can select the right answer between turns a and b inclusive. (n, a and b are all less than 1 million.)

A3) First off you have to realise that this question wants you to maximise the probability of selecting the right answer between a and b turns, not what the probability of ending between turns a and b if you play optimally with intent to win as quickly as possible.  So the actual problem has a straight forward cached recursion solution, which is O(n^2*a) time and O(n*a) space – which given the range of values you can clearly see is not even going to remotely work.  The solution I was about to challenge used this approach, with a few short cuts to make it fast enough for the basic cases given in the problem, but it was clearly not enough for general case of 1million, 500k, 500k type scenarios.

Only a handful of solutions for this problem, but unlike Q2, they are short.  Short but difficult to understand unfortunately.  One key thing I see is if the difference between a and b is more than ~21 they replace b with ~a+21 – because if you make it to a turns without getting it correct, you can guarantee that you get it right in the next ~21 turns because of binary search, so any optimal strategy will never go past a+21 turns.  The rest is not so easy to understand – at first glance it appears they are walking through possible first guesses and finding the best one, but I suspect this may not actually be a correct reading.

GCJ13 R1B

This time around the top 1000 advancement cut-off was Q1 + Q3 small in fairly fast time, or Q1 and Q2 small.

Q1) Given a game where you can absorb other smaller objects to become the total size of the 2, a starting size and a set of other objects, determine the minimum number of changes that have to be made to the set in order to be able to absorb every object into one big super object.  When adding to the set you can choose whatever size object you like.

A1) So this problem is somewhat greedy in nature.  It should be fairly obvious that there is never a downside to absorbing an object you can currently absorb.  So you start off by sorting the objects by ascending size, and absorb from the start until you can’t absorb any more.  At this point you have 2 choices – remove every larger object, or add a new object to make yourself larger in the hopes of continuing.  Again greedy comes into play, there is never any value in adding an object any larger than yourself (right now, you can always do it later when you are bigger) and no point making it any smaller than the largest you can absorb.  So add an object exactly equal to your current size minus one, absorb that, and repeat from the beginning.   You can continue this process until they are all done.

Along the way at each point you have to add an item, check to see whether your current number of added items + the number of remaining items, is better than your best result.  If it is, replace the best result.  Finally check whether always adding was better still at the very end.  Return this result.  Since you almost double in size every time, the answer is always going to be no more than about 21, so everything will easily run in time.  There is one special case that I have ignored so far.  If the initial object size is 1, you have to remove everything, because adding an object never helps in that case.

Q2) In a scenario where diamonds fall down and stack up (with random choice in fall direction when there isn’t an obvious choice) what is the probability that after n diamonds fall a given location has a diamond at it.

A2)  The important thing to notice with this question is that the falling diamonds occur in phases. Until the mound of diamonds reaches height n, it never goes wider than n either side of 0.  So the answer is either 1 or 0, unless the location being asked for is in the current phase.  Each phase adds 1, 5, 9, 13, 17 … diamonds.  This is of course an arithmetic series, so it has a quadratic sum formula, so the large input is obviously no worse than ~1000 phases, so it is safe to walk through them all until we get to the one of interest.  If the point of interest is in the final shell, we need to work out the probability.  For the small input there are only a handful of scenarios, you can probably work them out by hand and just hard code them, but for the large input it can get a bit more complicated.

If the final shell is full, obviously the answer is 1, otherwise we have 4n locations to fill with k objects where the 4n locations form 2 stacks of height at most 2n.  If k is <= 2n then each of those k had a 50% chance of falling to either side and the probability of reaching a certain location of height h is the probability of getting h or more heads from k coin tosses, which is standard probability theory (although some care will be needed for the calculations in the large input, 1600 choose h can be a very large number, as is 2^1600 – if you create your pascal triangle cache pre-scaled by 2^-depth and use double precision that should be sufficient accuracy).  If k > 2n, then it is possible to fill up an entire side, after which every diamond is guaranteed to fall on the other side.  I think this means that k-2n on both sides are guaranteed and we can treat the remaining (k – 2k+4n)=(4n-k) diamonds exactly as before, but with the height of the target location being reduced by k-2n – but I can’t say that I’ve double checked that carefully for probability theory mistakes.  If that isn’t true you can instead formulate a separate DP for each problem case (rather than reusing the same pascal triangle cache over and over) and build it up for each diamond dropped.

Q3) Given a string of ‘words’ where the spaces are removed and then someone introduces errors no more than once every 5 characters, determine the best cost match to a starting scenario based off a dictionary.

A3)  First thing to realise is that while the dictionary is quite large (500k words) the words themselves have a maximum length of 10.  This means that there can be no more than 2 mistakes per word.  This problem then boils down to a fairly standard dynamic programming problem.  The problem state is what character are we up to in the input, and how many characters since the last mistake (capped at 5).  From each problem state we consider each word length (1 to 10), and each valid scenario of adding errors to that next section (no errors, 1 error after the minimum gap, 2 errors after the minimum gap with minimum gap), check if the result exists, if so produce a new potential minimum for the final state (length and characters since the last mistake).

Only question is will this run fast enough for the large input.  Large input is 4000 characters, which gives 20k states.  Each state has 10 potential word lengths, and the worst case of those word lengths with has ~9500 cases, and the exists check requires operation cost at least equal to word length.  This gives an estimate cost magnitude of 20k*900k.  Or 18billion memory ops.  Even with only 4 test cases, that is very scary time wise.  We can probably trim quite a bit by skipping any scenarios where we can’t possibly improve the target cost scenario, and that cost magnitude is a bit of an exaggeration due to taking easy approximations.  So release build, no debugging, cross fingers… (or test run time before you submit…)

However, we can probably do better.  One option which seems a likely candidate is to use a prefix tree rather than a hashset to store the original dictionary contents – that way while we are generating our potential cases, we are going to get early failure quite often.  I would estimate this probably gives at least a factor of 20 improvement in practice.  Another option is to pre-compute separate dictionaries for each single character error position, then use them as a basis for the exists check, to avoid having to generate 2 character error scenarios which are the vast majority of the cases to check during the DP.  Memory usage will be quite large in this last case, but it should also definitely give a factor 20 improvement if implemented correctly.

I originally considered doing a once off creation of every 2 character error scenario from the dictionary, but the memory requirements can easily start heading towards 50+GB which defeats the point since I don’t have a home super computer.  Oh well.