So, I forgot this was happening so soon… hello 3am.<\/p>\n
750 to advance, but < 1100 registered in time. \u00a0Looked like it could be positive scores advance, but then the problem set turned out to be more like what I remember division 2 being.<\/p>\n
I was ~250th before challenge phase having solved the first 2 problems. \u00a0~230th after challenge phase as a number of people had their solution to the 1000pt successfully challenged. \u00a0Finally 216th, safely advancing, so no more top coder for me until May 12th. \u00a0Advance cut-off was a pretty slow time on the 250pt problem.<\/p>\n
The top 38 people solved all 3 problems. \u00a0I 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.<\/p>\n
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\u00a0intermediary\u00a0positions.<\/strong><\/p>\n A1) This was mostly a question of whether you could format\/parse do some simple modulo math. \u00a0Split\/int.Parse the input, format {0:00} for output to get correct 0 padding. \u00a0Output 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.) \u00a0Output MM is input HH % 12 * 5.<\/p>\n Q2) Given a set of numbers, determine the smallest maximum difference that can be used to create P pairs.<\/strong><\/p>\n A2) I was a bit slow writing up the code for this. \u00a0The approach I and many others used is\u00a0a pretty straight forward binary search on the maximum difference required. \u00a0The 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. \u00a0If number of pairs made is greater or equal to P, pass, else fail.<\/p>\n 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. \u00a0If so return the lexicographically smallest ordering for the walk, else return empty array.<\/strong><\/p>\n 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.<\/p>\n 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.<\/p>\n First take the input (which is list of node parents) and construct a child\u00a0list for each node and a reachability matrix.<\/p>\n 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. \u00a0(Initial current node is 0.)<\/p>\n Graph is still solvable if there is a walk which doesn’t visit any nodes in the existing solution. \u00a0A walk can be found by marking\u00a0all 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. \u00a0If you visit every node, success, else fail.<\/p>\n 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. \u00a0N was 100, so an O(N^4) solution sounds risky, but the constant ends up being quite good in practice.<\/p>\n","protected":false},"excerpt":{"rendered":" So, I forgot this was happening so soon… hello 3am. 750 to advance, but < 1100 registered in time. \u00a0Looked 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 … Continue reading TCO16 R1A<\/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],"tags":[],"class_list":["post-809","post","type-post","status-publish","format-standard","hentry","category-code-competitions"],"_links":{"self":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts\/809","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=809"}],"version-history":[{"count":0,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts\/809\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=809"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=809"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=809"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}