So I get a t-shirt this year 🙂 not a google one, but a t-shirt none-the-less.
Round 2 was a very strange round, I thought I was slow on Q1, but apparently I was unusually fast on Q2 – which is very much not how I usually perform in these competitions, even less so at 2am start times…
As far as I can tell out of 8 Aussies only 2 of us got t-shirts and are through to round 3. In fact despite it not being a google code competition, and hence John Dethridge being eligable to compete, I was the highest ranked Aussie at 133rd place. I think that is my personal second best placing ever in a coding competition. (Although I guess it doesn’t really count until its a placing which gets me eliminated…) My best ever I believe was 115th or so in one of the first google code jams. One of the ones where 100 people were going to be flown to the US to compete on-site…
Q3 had a decent number of submissions, but they did not include me. Almost all of those submissions failed though, so I have to suspect there is something I am missing about this question (even if I did only work out how to solve it at the start of intermission – I hadn’t been trying that hard since I felt relatively secure that I would get through given my current score and with only 30 minutes left I felt my chances of writing up a solution were negligible… and on second thoughts I am not sure I actually have solved it…). 1 of the 5 people to solve Q3 didn’t even get through, because both their first 2 answers failed.
I might as well write up some analysis before I get 3 hours sleep…
Q1) Given a set of places and multilane roads which connect them (each multilane road has the same number of lanes in each direction) and a single snow plow which starts at place 0 and takes 1 minute to traverse a single lane between any 2 places. What is the minimum time to clear all the snow and return to place 0?
A1) I wasted a couple of minutes convincing myself that my very easy solution was correct.
Step 1, verify the graph is connected to all places which have roads – I used breadth first search from place 0 and then checked the two ends of every road were at places reachable from place 0.If not reachable return -1.
Step 2, sum the number of lanes, return that value. This step was the one which bothered me, but I eventually convinced myself that since depth first search visits every edge exactly once, and multilane highways can always be processed with all but 1 lane on the way in, and the final lane on the way back, that it is indeed this trivial.
Q2) Given a number less than or equal to 100 million, find the smallest number equal to or greater than that number, which is the sum of 2 numbers made up entirely of odd digits in base 10.
A2) The key to this question is to recognise that the number of numbers which consist of only odd digits less than 100 million is only half a million. 100 million itself can be expressed as 1 + 99999999, so there is no need for anything more than 8 digits.
So, generate all odd digit only numbers up to and including 99999999, in order. Then starting i and j equal to the first and last positions in the list, decrement j while the sum of the two positions is still greater or equal to the input. Do not go past it. Record that sum. Increment i and start repeating the j decrement again. When you can’t decrement j any further, compare sum with best so far, if better, update. Keep repeating this until i is greater than j.
There is a much more efficient method, where the solution can be found in time order of the number of digits in n, rather than a time order of n/log n, but taking the simpler to reason/code approach was probably the only reason I scored so well. If they had of wanted to make the question harder they could have simply increased the limit from 100million to 1 billion. This would have caused memory usage of the simpler implementation to jump, I believe past the memory limit.
Q3) Given a ‘large’ grid of squares, and up to 40 of those squares which ‘interesting’ determine the minimum number of grid splits required to get each square on its own. A grid split is dividing one section of grid in to 2 smaller sections, either along a horizontal or vertical line. And ‘on its own’ means no other squares, interesting or otherwise, may be in its section.
A3) I am still not sure why a greedy approach of selecting the edge which has the most number of interesting squares touching it for each of the current set of sections and choosing to divide on it might fail (which is where I spent my first 25 minutes of thought), but a memotization or dynamic programming approach is going to be the right approach…
The problem with DP is it does appear it will run too slow. The worst case of the number of potential sub problems is 80x80x80x80 and each of those cases will require processing time, with up to 160 different children for each of the highest level problems. 2 seconds processing time is going to be pushing it, and memory usage is going to be close to the limit.
Apparently some very good coding in c++ means the direct DP approach can run in time and in memory. And after hearing one of the other coders say 40^5 as their execution time, I think I may have worked out the trick. If you sort special squares along an axis, there are places where you get 2 potential edge splits in a row, where there are no special squares inside. I believe the optimisation is to realise that if you split one of those edges, you can split both and treat it as a single operation, but with a count of 2 rather than 1. This makes it 41x41x41x41 worst case, with 82 potential children at the highest (every?) level. I’m not 100% on this optimisation yet but I’m pretty sure its the one.
Actually I have subsequently convinced myself that this optimisation is fine, and the same logic allows us to immediately trim off any outermost edge split locations before we start the dp. This drops the dp table to 39x39x39x39 worst case with 78 potential children at every level (not just highest, but there could be some potential to speed it up with a binary search to find one which is in the current location and walk outwards, other methods seem to have a higher overhead than the time they save…)