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.