GCJ16 Round 1A

So this round was blitz’d – cut-off was top 1000, and all of them finished all of the problems.  I’m not confident I could have solved them all in time, the key observation for the second problem doesn’t seem something I would have caught.

Contest analysis was posted almost immediately again, so my analysis is kind of redundant, but I’ll do it anyway!

Q1) Given a sequence of characters where for each you can choose to put it at the start or end of a word you are building, determine the lexicographically largest word you can make.

A1) So this is a greedy problem. At every point whichever action makes local sense, is also the path to the global maximum.  The contest analysis shows how to solve the large in 4 lines of python, I think it can be done in one (rather long) line of c# using the Aggregate function for enumerables.

However both of these solutions are quadratic in the size of the input (which is fine given a maximum input size of 1000).  Its possible to do this problem in linear time using a dequeue.  This is because the larger of adding the new letter as a prefix or postfix is the same as comparing the new letter to the first letter and putting it at the back if the new letter is smaller.  This reduction of the comparison to just the first character works because the generated word will always go down after any first sequence of repeated letters, never up, so extending the sequence of repetition is always an improvement.  Pretty sure this property can pretty easily be proved, but I’ve not done it formally.

Q2) Given 2N-1 sequences of length N which are all strictly ascending and each correspond distinctly to one of the rows or columns of NxN grid where every row and column is strictly ascending, return the missing row or column values in ascending order.

A2) Brute force for the small input isn’t exactly trivial to write but it is at least obvious.  Contest analysis tells me that the trick here for the large input is that every missing value will have an odd frequency due to there only being one missing row/column.  This leads to a very straightforward solution – which would be one (very long) line of C# if there was a method to Sort and return an enumerable…  I think I might add a ToSortedArray extension method to TMD.Algo.  This is O(N^2) since the data to be sorted is length N.

However since I feel that trick is too hard to spot reliably, I’ll now present an alternative implementation which doesn’t rely on it, but is still O(N^2).  Its just a bit more complicated and hence not one I’m confident I could design in the time available.

So this other method also has a trick, but one I think is more obvious.  The smallest value in the grid is in the top left corner.  Therefore the smallest value in the first spot of any of the inputs, is the value of the top left corner.  Further more any sequence which starts with that value, must be either the top row or the left most column.  Therefore there will be at most 2 of these.  This identification takes O(N) time, since we only look at the first value of each and find min, then a second pass to tag those that are min.  The trick is that now that we’ve identified the input data which could potentially be in the first row or column, the problem has been reduced.  Ignoring the data we’ve already tagged, the smallest value in the second spot of any of the rest of the inputs is the value from the second position of the diagonal.  Again there are at most two which match and we can tag those as being the second row or column.  We can repeat this until we’ve now identified the entire diagonal of the final grid and at most two options for any row or column pair passing through each position in the diagonal.

So far we’ve spent O(N^2) time, but we’re not yet done, we’ve only identified a fraction of the full grid.  Luckily we’re actually almost done.  Chose one of the elements of the diagonal that has 2 input data’s associated with it.  Since the grid is currently empty you can place these in any orientation without loss of generality, so make one the row and the other the column and place them into the grid.  Now consider the two arrays you just placed, for any indexes where they aren’t identical, the corresponding row/column pair which crosses perpendicular through those indexes is an interesting place to think about.  Since the values are not the same, if you have two options for that row/column pair, only one can be the row, and the other must be the column.  Thus they can be placed.  And so on for every time you place a row/column pair if any of the elements are different you have another row/column pair that can be placed if its not already placed.  So use a queue and a mask to know what you’ve put in the queue already, and this cycle of placing and finding new things to place is linear in the number of values in the arrays placed so far.  The one thing is that if there isn’t anything different, or if the difference is for the row/column where one is missing, your queue will flush, but you won’t be finished yet.

Here is the not quite so obviously true bit, but one I’m confident is fine.  Since you’ve gotten to a point where there is no difference in the rows or column pairs that are yet to be placed, you can simply choose arbitrarily again, just like you did for the first pair.  The known cells are guaranteed to match, and the unknown cells are guaranteed not to be influenced by anything you’ve already placed before.  Thus we can just throw a new index on to the queue and keep going.

Finally there is just the row/column pair passing through the diagonal where only one data set was tagged.  Check if the one data set matches the column, if so return the row, otherwise return the column.  Although before you return, do make sure you’ve set the diagonal value itself, it won’t have been populated yet unless you populated it at the very beginning while the diagonal values were being determined.

Every step along the way to fill in the values is linear in the number of values filled in, so O(N^2) just like the much simpler solution proposed by the contest analysis.

Q3) Given a directed graph where every node has exactly one outgoing edge, determine the maximum number of nodes that can be placed in a circle such that every element in the circle is directly connected to one of its neighbouring elements.

A3) Despite this problem being worth the most number of points – I found it to be conceptually the easiest.  Yes even easier than the first problem.  That being said the implementation is a pain, even worse than my extra complicated option for Q2 large input size.

So the problem has two pretty straight forward cases.

Option 1, the circle is fully connected.  Since each node has exactly one out going edge, this implies a cycle of some length.  So step one is to find the largest cycle.  That’s one possible answer.  Having found all cycles we’ll throw away them or any nodes that are connected to them if the cycle length is greater than 2.

All of the remaining nodes form pairs of trees pointing to a cycle of length 2.  Option 2 is to take the longest path to each side of that cycle, sum those together, then sum across all such connected components, this is the alternative answer.  This represents taking all the longest fully connected lines and placing them into a circle. Return the largest of Option 1 and Option 2.

Depth first search will identify all the connected components in linear time, it will also identify the longest cycle in linear time.  A second depth first search on each connected component with cycle length of 2 will find the longest path to the cycle in linear time too if you keep track of path depth and destination to avoid recalculation when your depth first search finds somewhere you’ve searched before when starting from a new possible deepest node.  Or reverse the direction of the arrows and just do a standard height of tree calculation.

GCJ16 Qualification Round

Contest analysis is already posted – 27170 positive scores and 1710 perfect scores.  Not mentioned was the cut-off, 22154 people are currently eligible for competing in Round 1.

The success rates for large were quite high for both of the first two problems, but quite a bit lower for the third and fourth.  I expected a low pass rate for the large input on the fourth as I’ll discuss later, but the third is less obvious.

Q1) Consider multiples of N, what is the end of the sequence which contains every digit in base 10 at least once at some point during the sequence.

A1) As mentioned in the contest analysis, it can be proved that other than 0 the maximum sequence length has an upper bound of 90, and the specific case of 125 gets close at 72.  Therefore the largest number to consider will be less than 90 million, so there is no risk of overflow.  So this problem boils down to can you correctly break a number down into its base 10 digits.  This is a pretty common operation in coding competitions for some reason or another, but one which is missing from TMD.Algo – I think I’ll fix that.

Q2) Given a sequence of – and + characters, determine the minimum number of operations to turn them all into +, if the only operation you can perform is to reverse the first k characters and also invert them all so – becomes + and vice versa.

A2) The key to this problem is that a change between – and + in the sequence will always remain a change during any operation unless the operation only includes one of those characters and the first element of the sequence is equal to the kth element of the sequence.  Therefore the number of changes, plus potentially one more because you end up with all -, is a trivial lower bound.  And simply repeatedly fixing the first change in the sequence is the solution because the prefix is always all the same character.  My preferred solution is to append a + on the end then just count where character not equal its next.

Q3) Generate a set of sequences of 1’s and 0’s that start and end with 1 and have a specific length, and when interpreted in each base 2 through 10, are always non-prime.

A3)  This was an unusual problem in that the entire test set was in the problem statement, there was nothing unexpected.  And despite that the large input only had a 70% pass rate.  This suggests a lot of people tried to be tricky like the contest analysis proposed, rather than just brute forcing with an arbitrary precision type.  Or didn’t realize that a 32 digit base 10 number is too large for 64 bit integers – I hope there wasn’t too many in that group, given to pass the small they would have already realized a 16 digit base 10 number is too large for 32 bit.

Anyway I just brute forced this problem using BigInteger and checking for trivial composites with factors less than 9.  Interestingly I found that just checking for composites using just 3 and 7 or 5 and 7 was effective, but not using just 3 and 5 or 2 and 7.  I’m not clear on why this is the case though, the contest analysis talks about a 3,2,7 being very popular so I guess 3,7 works for a significant fraction of those??  Really I’ve not done enough investigation to be sure.

Like the first problem, this problem involved digits, specifically for the brute force, interpreting them as values in different bases.  This is a pretty simple piece of code to write, but also one that shows up in programming competitions a bit, so it feels a bit of a deficit in TMD.Algo which I should fix.

Q4) Assuming that a K^C element sequence of L and G is generated by repeatedly applying a rule that starting with a length K (but otherwise unknown) base pattern of L and G a derived pattern is created by replacing each L with the original base pattern and G with an equal length sequence of G’s, determine S locations to check which will prove whether the are any G’s in the full sequence.

A4)  So this problem had a very trivial small input.  Regardless of the base pattern the first K characters are either base pattern, or all G.  If any of them are G then obviously the pattern contains a G.  If not then the base pattern is all L’s, which obviously means the entire sequence is L.  So when S = K you just return the numbers 1 through K.

The problem is that this approach tells you nothing about the large input.  Unless you actually understand the problem fully, you could come up with ways to do better than S = K, which will pass the small input, but then you’ll fail the large.  I think a second small input set where S could be anything, but K^C was limited to a much smaller number could have caught the first order failure to fully understand the problem without clearly giving away the full depth.

Anyway, I like this problem because of the subtle connection back to problem 1 and 3.  This is actually a problem about digits.  Given a zero-based trial location the zero-based positions in the original base sequence which could affect the trial locations value are the same as the digits of the trial location when written in base K.  More specifically, if any of those locations are G then the trial will return G.  So the ideal search is a set of C digit base K numbers where there is no unnecessarily repeated digits.  If any of the base pattern contains G, one of the search locations will be a G, otherwise the entire sequence is L’s since the base pattern is all L’s.  Once I have some nice digit sequence logic in TMD.Algo, I think the implementation for this solution will only be a couple of lines.

TCO16 R1A

So, I forgot this was happening so soon… hello 3am.

750 to advance, but < 1100 registered in time.  Looked like it could be positive scores advance, but then the problem set turned out to be more like what I remember division 2 being.

I was ~250th before challenge phase having solved the first 2 problems.  ~230th after challenge phase as a number of people had their solution to the 1000pt successfully challenged.  Finally 216th, safely advancing, so no more top coder for me until May 12th.  Advance cut-off was a pretty slow time on the 250pt problem.

The top 38 people solved all 3 problems.  I was making some decent progress on the 1000pt, but I had missed a key insight regarding how simple the problem really was, so was making my life too difficult for myself as usual.

Q1) Given a time in HH:MM form where HH is 1-12 and MM is 00-55 in 5 minute steps, return HH:MM format for a ‘clock hand switch’ where the hour hand is assumed to only show integers (by flooring) rather than the usual intermediary positions.

A1) This was mostly a question of whether you could format/parse do some simple modulo math.  Split/int.Parse the input, format {0:00} for output to get correct 0 padding.  Output HH is input MM divided by 5, then if 0 use 12 instead. (This can be done by (x+11)%12+1 – but an if statement seems simpler.)  Output MM is input HH % 12 * 5.

Q2) Given a set of numbers, determine the smallest maximum difference that can be used to create P pairs.

A2) I was a bit slow writing up the code for this.  The approach I and many others used is a pretty straight forward binary search on the maximum difference required.  The test to see if it is possible takes the sorted set of values and greedily pairs subject to the current maximum difference under test where possible taking from the smallest first.  If number of pairs made is greater or equal to P, pass, else fail.

Q3) Given a tree, determine if it is possible to visit every node once starting from the root, by only jumping between nodes which are ancestor/descendent (regardless of distance) of each other.  If so return the lexicographically smallest ordering for the walk, else return empty array.

A3) So I’m pretty sure I had the first part solved, I just needed to extend my solution to determine the smallest of the many possible solutions.

I think its possible to do this problem in O(N^3) or better, but here is an O(N^4) solution which is simple and I saw pass in time.

First take the input (which is list of node parents) and construct a child list for each node and a reachability matrix.

Loop N times, for the first node you can jump to from the current node (by checking the reachability matrix) and still result in a solvable graph, add that node to solution and mark it as the current node.  (Initial current node is 0.)

Graph is still solvable if there is a walk which doesn’t visit any nodes in the existing solution.  A walk can be found by marking all nodes in existing solution as visited, then while still possible, either jump to the deepest non-visited node if available or the shallowest non-visited parent if not.  If you visit every node, success, else fail.

Where I got stuck was I wrote an O(N) check for solvable (rather than the O(N^2) check described above) but it didn’t easily extend to starting from an arbitrary location with several nodes already marked as visited.  N was 100, so an O(N^4) solution sounds risky, but the constant ends up being quite good in practice.

GCJ15 R3

Last round before the finals, only 25 to advance.  Looks like 1 Australian in the top 25 which is an improvement I think…

5 questions in only 2.5 hours was a tough ask. No one got a perfect score, but the top 4 solved all but the last question.

I think I could have solved the first 2 and the small of the 4th on a really good day had I been competing, which would have gotten me 120th range, which I would consider a personal best.  More likely I would have came ~250th solving just the first problem.  Small of the 3rd isn’t too bad either, but I doubt even on my best day I would write solutions for 4 round 3 problems correctly, even if 2 of them were just smalls.

Q1) Given a tree with a root, and each node having a value, determine the minimum number of nodes to remove from the tree to ensure the difference between minimum and maximum values is no more than D.  When removing a node, you must remove all child nodes.

A1) So I found this question to fall into my personal skill set.  If you sort the nodes by value, you can sequentially from smallest to largest, and in reverse determine which nodes have to be removed to in order to have the any specific minimum or maximum value.  These passes are both O(N) assuming you keep a hashtable or boolean array lookup of which nodes you have already removed.

The problem is that any given combination of minimum and maximum that is closest to D (which could be done in linear time by walking up either the minimum or maximum depending whether the current range is less or equal to D or not) might have an overlap between the removed nodes, and so you would be double counting if you just add the two numbers together.

To do the large in time, we need to resolve this double counting without slowing things down.  The trick here is when constructing the nodes to be removed, in the first two passes, don’t just keep the counts, keep the actual lists of nodes removed.  This way when walking up the maximum and you are ‘undoing’ a batch of nodes that might be removed, you can keep linear time because you can just ‘replay’ that list of nodes.  As you replay adding and removing nodes, you check the boolean lists for minimum and maximum, if the node you are removing no longer exists in both, you decrement the count, if it newly exists in only the minimum list, you increment the count.  Otherwise the count stays the same. Then whenever the current range is less or equal check if you have a new minimum removal.  Note that while you start the loop having removed everything, you will at some point reach the value of the root, and since a single node trivially has 0 range, you will never return removing all values as a result.

Q2) Given a sequence of numbers which are the running sum of length K from an original sequence of length N, determine the minimal difference between minima and maxima of the original sequence, assuming the original sequence consisted entirely of integers.

A2) I tried my hand at this for a while, but made a major mistake in thinking early on which left me stumped.  The difference between consecutive sums gives you the difference between two values K apart.  The difference between the next two sums, also does the same.  Combining these two formulas together doesn’t seem to let you derive anything.  I mistakenly then assumed that combining formulas wasn’t the way forward.

The trick is to see that if you have a difference which tells you the relationship between position 0 and K, there is another which tells you the relationship between K and 2K.  Hence you know the relationship between 0 and 2K.  Thus the problem can be reduced to K pairs (if N is >= 2K, otherwise the problem gets some slightly different corner cases I’ll discuss later).  Each pair consists of the relative maxima and relative minima, of how high or low the sequence will go assuming the first value was 0.  Now the question becomes how to align these such that they have minimal range, and their first values are integers and add to give the first sum.

So extend these pairs to triples, by adding 0, the imaginary starting value.  Then align them to have the same maximum, which could be 0, or the first maxima, doesn’t matter.  The sums of the starting values will now be X.  Calculate (X – first_sum)/K using integer division- and subtract that from all values of each triple.  Now you need to reduce the sum of starting values by (X-first_sum)%K.  Sort the triples by their minimum’s in descending order.  The aim is to avoid moving them past the last one.  If we can do that the result is the range of the last one, otherwise it is the range of the last one + 1.  This can be done with a simple greedy strategy, shift each down to be the same as the last minima until you reach the mod value, or you don’t.  If you do, success, else add the one to your return value.

If N < 2K there is a slight difference.  You get less than K pairs to start, and so effectively you have some ‘free’ starting values.  These values can be represented as having 0 maxima and 0 minima as the starting pair.  They make it a lot easier to avoid having to add 1 – but they don’t eliminate it.  To demonstrate this clearly consider the ultimate degenerate case N=K.  Here you only have 0,0 pairs.  But if first_sum%K != 0, you can’t just make all the values have equal starting value.  Hence the result will sometimes be 1.

For this problem the small input really wasn’t much simpler than the large, and it showed, only 5% of those who solved the small failed to solve the large.

Q3) Given a set of points, which all run away from you at their own individual speeds, if you have speed Y, what is the soonest you can visit all the points.

A3) First a trivial simplification, you don’t care about points which you have already visited, so running away from you can be considered running away from the starting point.  If all the points were on one side, the problem is trivial, you just run that direction until your last intercept time based on speed difference and starting positions.

The small data set is 25 points.  That gives 25! scenarios if you ignore that you might visit something on the way to somewhere else.  This is too large, even the basic dynamic programming solution is 2^25 * 25 * 25 (cheapest way to visit subset S ending at T, each state has to consider being continued to visit any other node not yet visited).  If you happen to have a small super computer, this might be fast enough if you parallelize the test cases and optimize well, but otherwise this is going to be too slow.  This ignoring whether you reach something on the way to something else or not is okay, because you can guarantee that ignoring it results in a worse time than visiting it in the right order, but it is expensive.

Looking at a solution which solved just the small, you can take advantage of the fact you visit them on the way to each other.  You will not possibly turnaround more than 25 times.  At any given point in time you will either go left or right and visit the first unvisited node you catch up to in that direction.  This gives you a brute force 2^25 with each point in the brute force having a search cost of 25 to determine the earliest unvisited left/right catch ups.  Overall cost O(N*2^N) which is okay if you have a fast machine…

Looking at a solution for the large, its a DP on having caught the fastest i points going left, the fastest j points going right, and going to catch point k.  First set every value in DP to infinite time.  Then its initialized with the time to reach each point having not previously caught anything (IE starting from 0), which seems like you are ignoring visiting things sooner vs later, but that is not the case.  From each state you consider catching the next fastest left or right point.  If your current position implies you have already gone through that item, you can improve the time for that to the current time, assuming you haven’t already found a better time to get there.  If its not you can calculate a new intercept time as given time of the current state and which node you are currently at, you know where you are.  If that is an earlier arrival time, done again.

It all seems clean and simple.  The question is why does sorting them by the fastest to slowest work even though you might catch a slower one on the way to a faster one.  I think the proof of that is somewhat involved, maybe the official contest analysis will have details… It does seem somewhat intuitive though, fast ones are hard to catch, so you should focus on them first.

Q4) Given the values and frequency of the sums of elements in each set in a power set, determine the original set that created the power set.  If that is ambiguous, determine the ‘smallest’ original set.

A4) The small vs large is two very different problems, which is shown by the vastly different solve rates.

The small problem there are up to 20 values in the original set, but they are all non-negative.  This helps a lot.  You can determine how many 0’s there are by looking at the count of 0 sums, log base 2.  The rest of the frequencies can then be divided by number of times 0 occurs. The smallest non-zero value is then in the original set, and its frequency is how many times.  Anything less than double this value is also in the original set.  As you get more and more values, you can calculate how frequently the sums they generate should be.  Basically you get a loop, what is the smallest value who’s frequencies aren’t all accounted for.  Add that to the set and for each result and existing frequency, also add result + value and the new frequency.  Loop runs at most 20 times, each time it runs its cost is proportional to the number of different values, which the problem caps at 10k.

The large introduces negative numbers.  Which complicate things enormously.  You don’t clearly know how many 0’s there are by looking at frequency of 0, because values might add together to give 0.  Starting from the smallest doesn’t work, its the sum of all of the negative values.  Starting from the closest to zero doesn’t work, some of these could be the sum of positive and negative values…

Looking at a large solution.  First thing is you can easily tell how many numbers you are trying to find.  Just add the frequencies and log 2.  Turns out you can work out how many 0’s there are, just log 2 the frequency of the smallest number (not sure why I didn’t think of that…).  Now there are no 0’s you can determine one value by taking the difference between the smallest two values. (Also obvious in hindsight…) Now we just have to update the frequencies for the removal of that value and repeat the process.   You might think you are done here having generated N numbers this way… but each of those gaps is either a positive number being added to the set or negative being removed. So generate all the possible sums (using a set to avoid duplicates since 2^60 is large, but we know distinct sums are much smaller), and while each number removed is in a sum path for the smallest value, consider those as negatives, the rest are positive.  Consider the numbers in the reverse order of discovery, since the smallest absolute values are found first and the question asks for ‘first’ under ambiguity, large negative values are good for satisfying that critieria.

Q5) Given a small section of an infinite sequence of values determine whether they can be the sum of some number of streams of 0 and 1 where the 0 to 1 transition happens every 2^K for some K between 1 and D (each stream can be different in transition frequency and no restriction on starting offset – and there are also potentially streams which never change and are always 1).  If it can, determine the minimum number of changing streams.

A5) Getting late, I’ll have to look at this another time.

GCJ15 Distributed Practice Round

So, I think everyone qualified for round 3 was eligible to do the practice round.  202 positive scores, 14 perfect scores.  I hope everyone who intends to participate in the distributed online round had a go in the practice round, as the distributed format is new and quite different – I think people who spent a good long time on the practice round will have a big advantage.

Even with 50 hours to think things over, and a testrun feature which lets you check if your solution is too slow on the large input, for test cases of your own design, pass rates for large input were quite low.  2 of the quests had less than 50% pass rates.

The top 14 perfect scores was 12 c++ and 2 java. No python.  Small sample size, but given the ratio of language use in the group that advanced to round 3, its absence is slightly suspicious.

Q1) Find the largest prefix/postfix sum for a list of numbers if the prefix/postfix are not allowed to overlap. 5×10^8 members in the list.

A1) On a single machine this problem boils down to what is the largest drop.  Once you’ve found the largest drop (by calculating running sum and keeping track of the previous maxima vs the current value) the answer is the sum of all numbers – the largest drop (which will be negative, giving you a bigger total).

Splitting this to multiple machines isn’t too difficult.  Give each machine a subsequence of approximately equal length, calculate the minima, the maxima,  the ‘local’ biggest drop and the total.  These can all be calculated in a single pass of O(N) time.  Send all these values back to the primary machine and exit.

The global biggest drop is either the largest of the local biggest drops, or it is the difference between one of the maxima’s and a subsequent minima.  First the maxima’s and minima’s need to be corrected since they are local, so add the running total of the previous totals to each local minima and maxima.  Then calculate the biggest drop, and finally subtract that from the overall total of totals.  These steps are O(Nodes) so will easily run in time.  Remember to use 64 bit integers everywhere, as the numbers can sum to 5*10^17.

Q2) Calculate who, if anyone, is a majority in a vote. 10^9 voters and potentially 10^9 candidates.

A2) So I have 2 approaches for this problem, which have different scaling functions, but are surprisingly similar in run time for the problem size.

The ‘cool’ solution is to count the frequency of each of the 32 bits in the candidate vote identifier over all votes.  If there is a majority, the set bits of the majority candidate will have over half the vote, and the unset bits will not.  So simply send the totals to central server and accumulate and compare to number of votes.  This lets you create the bit pattern of the majority, if there is a majority.  Send this majority holder back out to everyone, who then counts the frequency of exactly that candidate.  Send these new counts to central server, accumulate and check if its a majority.

This solution is linear, but requires two passes.  Given how long it takes to call GetVote you will lose 500ms of your time just doing that if you don’t store the values, and if you do the store the values you should be careful you don’t run low on memory, but it will save you 250ms…  Each value also has 32 bit extract’s to perform to potentially increment the 32 counters.

The alternative solution is to sort the segments you assign to each server.  This is O(N log N), but with at most 10million entries, the log N is only a factor of 24.  You must be sure your sort function is in place, because otherwise you will run out of memory.  Having sorted them you take every entry which got more than 20% of the vote (which is easily found now that they are sorted).  There are at most 4 of these, send their identifiers to central server.  Also send the size of the threshold you used to select them, which is 20% of the number assigned to this node.

The central server now has up to 400 candidates, which it can easily total and sort.  Any total which when added to the sum of thresholds sent back (which should be close to 20% of the overall, but might be slightly off due to rounding) gets a majority is a candidate.  There is at most 3 of these as they each have to have at least 30% of the vote.  Send these back and do a second pass counting totals for each of the 3.  Finally the majority holder either appears, or does not.

This solution has the advantage that rather than doing 32 operations per entry to start and 1 more to find the majority candidate total, it does 24 (for the sort), 1 to count run lengths and then 3 more for the totals.  In practice there is more overhead, sorting operations are compare and swap where as bit extract and increment is cheaper – memory locality of the operations is also much better in the first solution. It also has the advantage of potentially not doing the second pass.  If you get a straight majority or none get to 30%, the second phase can be skipped.  This bonus has an interesting correlation – it is more difficult to construct a fast running input which has slow sorting time and also has 30% of votes going to one person.

Q3) Find the shortest distance between two specific nodes in a circular doubly linked list.  10^9 nodes.

A3) So the single machine version is you just walk left from start until you find the other target, compare the number of steps to the total number of nodes and you are done.  The distributed version is a bit more awkward…  you need to break the input set into sections, but given the nodes are in random order, how do you do such a thing?

One option is to select evenly spaced nodes and call your section done if you ever see another node which is x mod k.  This is however fragile, its not hard to construct inputs which means regardless of your choice of x and k, one of your nodes is going to do a lot more work than the rest.

Solution is to use random nodes instead, that keeps you safer.  To be extra safe, choose 10 random nodes per server, that way if one of its segments is double length, that only adds 10% extra running time.  However you now have to compare every value you get while walking against 1k potential terminals.  This is way too slow.  One option is to sort the selected nodes and binary search.  This has potential to run fast enough.  Another option is to not use truly randomly selected nodes.  Instead divide the nodes into groups of k, and for each group select a random terminal position.  Then you can check if you are terminal by checking node value mod k vs random_nodes[nod value / k] mod k.

Potential little tricks for avoiding overhead.  Assume each machine runs the same version of libc – rather than communicating the random node selection from central server to each server, use a hard coded seed to rand and calculate it on each server.

In any case, each node returns the length of its segment, the start, stop nodes, and whether it saw either or both of the start and end nodes.  The central server can then easily and quickly construct the path from start to end node.

Q4) Determine whether it is possible to partition a set of numbers into two equal halves.  52 numbers, each of which have a large range of possible values.

A4) Unlike all the other questions, this doesn’t bombard us with lots of data.  But the question is NP-Complete, so it doesn’t really have to.  Wikipedia (see subset-sum problem) tells us that it can be solved in O(2^(N/2)) time, which is actually almost really close to fast enough for a single machine – but it would use more than the allotted memory limit.

The simple fix is to use 64 of the 100 machines, and tell each to ‘fix’ 6 of the numbers as either left or right, then run subset sum on the remaining numbers with an adjusted target based on the ‘fixed’ values.  This saves a factor of 8 in memory usage and running time, which is just about enough.  Each machine returns whether it finds the partition, and central server thus has the answer.

This only has Sqrt(Nodes) scaling, unlike the other problems which each have linear scaling – but getting linear scaling for this problem seems likely to be quite a bit more difficult…

GCJ15 R2

The all important t-shirt round, top 500 advance but 1000 t-shirts were on offer.  Four problems for round 2, in the end advancing meant solving all the small inputs and the easiest large input, or one less small in a very fast time.  Even with a slow time that was enough to get the t-shirt, 2 small and a large was okay if you were fast, or the second small was for the hardest problem.  I think I stood a decent chance of advancing if I had of been competing this year, definitely would have gotten the t-shirt…

Q1) Given a 2D grid where some cells propel you in a direction, what is the minimum number of cell with direction that need to be changed to ensure that regardless of starting location, you never fall off the edge?  (Note its not always possible to solve, so return ‘impossible’ if there is no solution.)

A1) I didn’t immediately get this problem, but when I looked at it again I realized it was trivial.  Seems the contestants agreed, with very high success ratio and high solving rate.

In the end it boils down to the question, why would you fall off the edge at all?  Because a cell is pointing there with nothing else in the way.  So for each such cell, just point it at another cell with a direction.  If you can’t then the problem is impossible and you should return as such.  Otherwise you are done, just count how many cells you had to change.  The run time of the simple brute force is obviously no more than O(WH*max(W, H)) which given the constraints is trivial.  A tighter bound is actually O(WH) every cell can only be traversed at most 5 times, once to find the cells with direction, and then 4 times from being reached from each direction by other cells. So even if the problem had of allowed much larger grids, it would still have performed in time.

Q2) Determine the minimal time to fill a container of volume V to temperature X, given a bunch of sources of flow rate F_i and temperature T_i.

A2)  The small input here has only 2 flow sources, and the problem gives the formula for mixing temperatures.  Solve simple simultaneous equations in 2 variables and you are done.  The inputs are given to 4 decimal places, and the answer is 1 part in 10^6 accuracy, so doubles sound like they would be fine here.  But this isn’t quite like other such floating point problems.  This one has the ‘can’t be done’ answer, if both temperatures are the same side of the actual temperature.  So you need to be sure that you don’t introduce a numerical error which means that in the case where one of the input temperatures is equal to the desired temperature, you incorrectly return impossible.  One solution is to ignore the fact that the question specifies things as 4dp, and just multiply everything by 10000.  These factors of 10000 cancel out in determining the time, so you can switch to mostly integer arithmetic, just converting back to floating point for the final division.   You have to be careful with overflows though.

The large input is too large to brute force, which suggests a greedy approach.  My best guess was to order them by temperature.  I took a look at some passing solutions and one of them did exactly this.  Order by temperature, then slowly prune either the hottest or coldest until you switch from the output being too hot to being too cold or vice versa.  Then its like solving the small input, just with one high flow mixed temperature of everything, and the last temperature you removed.  I found it interesting that they didn’t bother to solve the simultaneous equations though, they just binary searched for the flow rate that produced the right output temperature. (Since you can simulate lower flow rates just be having that tap turned off for part of the time.)

Another solution I saw instead binary searched over ‘can it be solved by time x’.  They also sorted by temperature, but instead of pruning backwards one by one, they built outwards from the middle.  Given the time t, they had actual volumes rather than rates, and could determine if each volume from a given tap could be mixed with some from another to create the right temperature.  As they used up each tap, they moved to the next one out.  Eventually all of the colder than target taps or all of the hotter than target taps get used up, and the the rest is discarded.  If the total used volume is greater than or equal to target, success and binary search a smaller time, otherwise a longer time is needed.

Q3) Given a set of sentences which are in ‘English’ or ‘French’ determine the minimum number of words that must be in common between English and French.  The first two sentences are labelled, the rest are unknown.

A3) The small input looks like a trivial brute force, but unless you start by replacing strings with numbers, the hash/equality cost is quite high and will probably stop your code from running in time.  So relabel everything to numbers.   Given the constraints there will be no more than a few hundred distinct words which you can number consecutively 0 to N, so rather than hash lookups you can just used indexed arrays.  Enumerate the 2^18 scenarios adding to the counts of times you’ve seen each ‘word’ against either English or French arrays.  Then sweep them both looking for anything which has both positive for the same index.

The large input however had me stumped.  My best guess was some kind of maximal matching or flow graph, but I couldn’t see how to construct it.  Looking at other solutions it appears max flow graph was the answer.

Each sentence has two nodes, each distinct word has two nodes.  Unlimited flow from the first to second nodes for each sentence, but only unit flow between the first and second nodes for each distinct word.  Then connect the second node of each sentence to the first node of each distinct word in the sentence, and vice versa – both with unlimited flow.  The answer is then the maximum flow from the first node of the first sentence, to the second node of the second sentence.

I don’t understand why this works though, maximum flow for a minimal answer.  Even the meaning of each node doesn’t seem obvious.  The two nodes per sentence seems redundant since there is only unlimited flows involved, probably just a convenience rather than having source and sink nodes for the first two sentences especially.  A flow between the two nodes for a word means they must be both English and French.

Looking at the case of just the input two sentences, every word in common allows a flow which goes first node of first sentence, second node of first sentence, first node of word, second node of word, first node of second sentence, second node of second sentence.  Words not in common don’t allow flows because they just form a cycle with their parent sentence.  Next simplest example, one word third sentence which is in common with English (or French) but not both.  It gets ignored.  Good.  Three word sentence with two in common with English and one in common with French.  One more flow, from first sentence through the fact its in common with English, to third sentence, then over to French by the one in common with that.  The second potential flow gets stuck at the 3rd sentence.  It all works, but the why still escapes me.

 

Q4) Given a cylinder labelled with a rectangular grid of positive numbers such that each number has exactly that many neighbours of the same value determine how many such labelling exists, modulo 1 billion and 7.  Two labellings are considered distinct only if they aren’t rotations of each other.

A4) Brute force on the small input here seems scary, but back tracking algorithm stands a good chance of running in time, because the problem is so restrictive.  Some smarts might still be needed.  Pure brute force is 3^36, which is obviously too slow. (4 and higher can’t be on the board, 5+ trivially, 4 because it implies an infinite board.)

Looking more deeply unlocks this problem.  There are limited number of ‘units’ which a solution can be made up of.  A row of 2’s where nothing above or below is a 2.  2 row’s of 3 where nothing above or below is a 3.  These 2 are the obvious ones given in the question itself.  The trick is to come to understand there are only 3 more building blocks.  They all involve just 1’s and 2’s.

122
122

112222
222112

1222
1212
2212

Each can only be placed next to itself in a row, and each can be rotated a number of places equal to its width, but again rotated versions can only be next to rotated versions.

The problem then becomes a DP over rows.  2 rows of 3s separating one of 4 scenarios of 2’s.  One which uses one row, 2 which use 2 rows, but have 3 or 6 rotation variants, one which uses 3 rows with 4 variants.  The trick is to make sure you don’t over count.  Each variant is like a rotation, so if you only use one pair of rows of mixed 1 and 2, you have actually over counted by exactly 3 or 6 times.  One solution is to assume that you are always going to over count by a factor of 12, so divide the result by a factor of 12.  Then at the deepest level of your recursion, force over counting to be 12.  If you’ve not used any 1 or 2 mixed, return 12, if you’ve used only the first kind, return 4, only the second kind (or second and first), return 2, only the 3rd kind return 3, both the 1st and 3rd or 2nd and 3rd (or all 3) return 1.  The DP is then on rows and 4 bools representing whether you’ve ever used each of the 3 types of 1,2 mixed and whether the last set of rows were all 3’s or not.

GCJ15 R1C

Three easier questions this round, although I have to say I found the ‘easy’ question the hardest… Advancing cut-off was either of the first 2 problems and the smalls from both the others and a few minutes to spare.  Solving the 3rd problem and smalls of the other was worth 1 more point and ~400 places as a result.

Q1) In a game of finding all the locations of a 1xW rectangle in an RxC space, where before each guess the opponent is free to move the 1xW rectangle anywhere that is consistent with the previous answers, determine the minimum number of guesses to guarantee victory assuming the opponent plays to maximize your guesses.

A1) So I spent a while rabbit holing entirely the wrong direction.  I seem to have ‘divide and conquer’ on the brain, this is the second time I’ve gotten stuck on a problem this year because I was convinced that dividing the problem in half was optimal.

So in practice this question boils down to forcing the opponent to have no options as fast as possible.  This starts by reducing the places the rectangle can be.  The fastest way to do this is obviously (in hind sight) to guess W cells away from an edge of where it could be.  The opponent will answer no unless it has to, a yes easily reaches a smaller number of guesses.  No answer eliminates W spots.

When you are down to one last row with 2*W-1 or less possible spots the strategy changes.  W spots you know everything, so just guess every spot left to victory.  Between 2*W-1 and W+1 inclusive you know some subset of the middle. Guess immediately next to that, the opponent will answer no (or possibly yes if there is more than one unknown spot left, it makes no difference to them if they are assume we play ideal).   Once they answer no, we know everything and can guess all the remaining spots.

In the end this entire problem can be boiled down to C/W*R + W – (C%W==0 ? 1 : 0).  Each row other than the last takes C/W guesses to eliminate entirely.  The last takes C/W – 1 guesses to get down to the last section, then W+1 guesses to pin everything down.  With one exception if C%W == 0, the last section is W spots, so only W guesses are required to pin everything down.

In the end I wonder why the limited the large input to just 20 x 20, I guess it leaves open a DP solution rather than just the greedy.

Q2) Given a list of letters (size N) to choose from at random, a length of output (size S) and a ‘target’ sequence (size T), determine the maximum number of times the target sequence could appear, then determine the difference between that and the expectation value for number of times it appears in the output if generated at random.

A2) So this is a deceptively easy problem.  I usually don’t like probability problems, but in this case the details clearly point out that multiple overlapping instances all count.  Hence the probabilities are independent and easily calculated.  List of letters can be turned into base probabilities by summing 1/N for each letter.  The target is then converted into a probability by the product of those base probabilities for each letter in the target.  The full expectation value is then that ‘target’ probability times S-T+1, since each possible starting point is fully independent.

The maximum number of times target sequence can appear is determined by the maximal non-complete overlap of the target sequence with itself.  Which can be determined with a simple nested for loop.  The maximum is then (S – T)/(T-overlap) + 1.  One length T, then as many T-overlap sections that will fit.

Q3) Given a list of values that you can have up to c of each of, determine the minimum number of extra values in order to be able to create every possible total between 1 and V.

A3)  I found this question easy, but only because I’ve had previous experience with this kind of question before.  Its a greedy problem.

Start off with having used none of the provided values.  With this you can make 0.  Take the smallest unused provided value, if it is what you can currently make + 1, or smaller, add c * that value to what you can currently make.  Otherwise add c * (what you can currently make + 1) and increment the extra values you had to have counter.  Repeat until you can make V or higher.

One corner case to be careful of for large input. While the target V can never be more than 1 billion, and the provided values are always small, the extra values you have to add can be very closer to 1 billion, so adding c * extra value can overflow a 32 bit integer very easily.