So TCO10 round 1 finally came along, of course I’ve been sick all week and TCO starts their competitions at 2am, so I wasn’t feeling in the best of shape for getting through in the top 850.
But I did, about 750th, entirely due to a successful challenge during the challenge phase. Been a long time since I’ve done one of those, and its the first time it has made a real difference. I only got the first question out successfully, I realised I had been an idiot for about an hour with 2 minutes left on the clock to do the second question, and I made some stupid mistakes in my implementation, which I submitted without testing knowing my time on the first question was likely insufficient to get through. Interestingly no one challenged it despite the fact it failed even the most basic tests!
Its 4am, but I am a little energised from having snuck through, so I’ll write up the first 2 questions. Question 3 will have to wait – I haven’t really looked at it. (Although at first glance I think I would have made better progress on it than Q2 – although I probably would not have solved it).
Q1) Given 2 strings of equal length, find the smallest string which you can both make them equal to in the minimum number of moves. A move is changing one letter in either string to either the letter above or below (where z can wrap to a and vice versa). Minimum number of moves has priority over ‘smallest’ string. Smallest being lexicographically earliest, alphabetical sorting.
A1) The examples pretty much covered how to do this, although I imagine that skipped the one tricky corner case. In any case, the solution is to check each letter in turn between the 2 strings. If the absolute difference ignoring wrapping is less than 13, add the smallest of the letters to the result, otherwise add the letter a. I was very concerned that at the 2am start I might have gotten the less than 13 condition wrong, implementing an off by one. A simple mistake would have been to used less than or equal to. If the non-wrap distance is 13, the wrap distance is also 13, but you have to remember that wrapping always takes you through a, which results in a lexicographically smaller answer.
Q2) Given a computer with 2 registers both initialised to 1, and 2 instructions, one which sets register 2 (Y) to the sum of the 2 registers, and the other which sets register 1 (X) to the sum of the two registers, determine the shortest program set register 1 to the value ‘R’, where ‘R’ is between 1 and 1 million inclusive. If there is more than one program, return the program which is lexicographically smallest, where the second instruction as described above is called ‘X’ and the first one is called ‘Y’. (Just to confuse, the instructions have the same names as the registers!)
A2) I felt pretty stupid at 2minutes to go when I realised that the approach I had discounted immediately, was the answer. That approach was trying each combination of register 2 with register 1 equal to R and where register 2 is less than or equal to R.
Instead I recognised the similarities with Fibonacci numbers, and wasted time thinking the golden ratio might be involved in the solution. I tried breadth first generating under the assumption that the answer string would be short, but I soon proved that it would not always be. Despite that I somehow went back to golden ratio thinking…
What I should have realised was the association with GCD, a combination of registers can only be reached if their GCD is 1. But more importantly, I should have realised that for a given pair of X and Y, there is only one X’, Y’ pair which can produce it. And following this back to X=1, Y=1 (if it does indeed reach that) can be done very quickly (since it is Euclid’s algorithm). So running it 1million times is acceptable. (This is what I realised with 2 minutes to go…)
The subtlety is the requirement to return the program. If you try and build up the program for every execution of Euclid’s algorithm you will find making the generated strings will consume more cpu time than Euclid’s algorithm… So the trick is to only generate the strings if needed. Solving the problem in 2 phases is one approach, executing the second phase only for the cases which phase 1 indicated were smallest. Another is assuming that the shortest answer will have X’ and Y’ near each other, iterating in an order which does that first and then capping the Euclid algorithm recursion to whatever your best previously seen depth is. This doesn’t actually seem a guaranteed success, but it did seem to be good enough.
The best answer I saw calculated the programs as a single phase, but expressed them as a run length encoding, allowing for the division acceleration of GCD to be maintained. Better yet the run length encoding was a list which when compared to another list, actually maintained the lexicographical sorting of the non-encoded string, so the only point at which a large string might be constructed, was creating the final answer.
Finally if you were using c++ and 2 pre-allocated 1meg char arrays, it appears you can run in under 2 seconds cpu time even if you don’t use division acceleration. Sneaky…
Q3) Given a fully connected directed cost graph, determine maximum profit from tours of the graph which all have the same income (regardless of where the tour goes), all start and end at vertex 0, but cannot visit the same non-zero vertex as each other.
A3) I initially suspected something like enumerating subsets of the destinations, determining cheapest tour for each, and sticking them in a maxflow graph in a way which ensures no 2 which overlap destination wise can be selected, then running max flow graph algorithm. Suspect the creating of the graph is the bit which I would get stuck on, not enough practice.
… Apparently I couldn’t sleep until I solved this one, at least I didn’t feel the need to come and write up the solution straight away.
Create a max-flow/min-cost graph as follows. For every vertex in the original graph, create 2 vertexes, destination enter, and destination exit. Between each pair (exception for vertex 0) create an edge with no cost and capacity 1. For each edge in the original graph, add an edge between destination exit for the original edge start, and destination enter for the original edge end, with cost equal to original cost and a positive integer capacity (might as well make it 1). Connect vertex 0 enter to the sink with infinite capacity and no cost. Connect vertex 0 exit to the source with no cost and capacity C.
Run max-flow/min-cost for each C equal 0 to number of vertexes -1. Return the best of flow times income – cost, out of each simulation.
I was happy I managed to solve this without looking at any solutions (at 5am no less), I think that is the first time I’ve reasoned through a max-flow/min-cost problem from scratch. Interestingly I thought I had implemented a max-flow/min-cost in TMD.Algo, but it appears not. I really should get to that!