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\u00a0 the top 850.<\/p>\n
But I did, about 750th, entirely due to a successful challenge during the challenge phase.\u00a0 Been a long time since I’ve done one of those, and its the first time it has made a real difference.\u00a0 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.\u00a0 Interestingly no one challenged it despite the fact it failed even the most basic tests!<\/p>\n
Its 4am, but I am a little energised from having snuck through, so I’ll write up the first 2 questions.\u00a0 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).<\/p>\n
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.\u00a0 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).\u00a0 Minimum number of moves has priority over ‘smallest’ string. Smallest being lexicographically earliest, alphabetical sorting.<\/p>\n
A1) The examples pretty much covered how to do this, although I imagine that skipped the one tricky corner case.\u00a0 In any case, the solution is to check each letter in turn between the 2 strings.\u00a0 If the absolute difference ignoring wrapping is less than 13, add the smallest of the letters to the result, otherwise add the letter a.\u00a0 I was very concerned that at the 2am start I might have gotten the less than 13 condition wrong, implementing an off by one.\u00a0 A simple mistake would have been to used less than or equal to.\u00a0 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.<\/p>\n
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.\u00a0 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!)<\/p>\n
A2) I felt pretty stupid at 2minutes to go when I realised that the approach I had discounted immediately, was the answer.\u00a0 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.<\/p>\n
Instead I recognised the similarities with Fibonacci numbers, and wasted time thinking the golden ratio might be involved in the solution.\u00a0 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.\u00a0 Despite that I somehow went back to golden ratio thinking…<\/p>\n
What I should have realised was the association with GCD, a combination of registers can only be reached if their GCD is 1.\u00a0 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).\u00a0 So running it 1million times is acceptable. (This is what I realised with 2 minutes to go…)<\/p>\n
The subtlety is the requirement to return the program.\u00a0 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…\u00a0 So the trick is to only generate the strings if needed.\u00a0 Solving the problem in 2 phases is one approach, executing the second phase only for the cases which phase 1 indicated were smallest.\u00a0 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.\u00a0 This doesn’t actually seem a guaranteed success, but it did seem to be good enough.<\/p>\n
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.\u00a0 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.<\/p>\n
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…<\/p>\n
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.<\/p>\n
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.\u00a0 Suspect the creating of the graph is the bit which I would get stuck on, not enough practice.<\/p>\n
… 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.<\/p>\n
Create a max-flow\/min-cost graph as follows. For every vertex in the original graph, create 2 vertexes, destination enter, and destination exit.\u00a0 Between each pair (exception for vertex 0) create an edge with no cost and capacity 1.\u00a0 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).\u00a0 Connect vertex 0 enter to the sink with infinite capacity and no cost.\u00a0 Connect vertex 0 exit to the source with no cost and capacity C.<\/p>\n
Run max-flow\/min-cost for each C equal 0 to number of vertexes -1.\u00a0 Return the best of flow times income – cost, out of each simulation.<\/p>\n
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.\u00a0 Interestingly I thought I had implemented a max-flow\/min-cost in TMD.Algo, but it appears not.\u00a0 I really should get to that!<\/p>\n","protected":false},"excerpt":{"rendered":"
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\u00a0 the top 850. But I did, about 750th, entirely due to a successful challenge during the challenge phase.\u00a0 Been a long … Continue reading TCO10 R1<\/span><\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3,6],"tags":[],"class_list":["post-192","post","type-post","status-publish","format-standard","hentry","category-code-competitions","category-random-musings"],"_links":{"self":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts\/192","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=192"}],"version-history":[{"count":0,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts\/192\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=192"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=192"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=192"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}