As is usual with SRM I didn’t do this one.\u00a0 However, I figure I might keep writing up blogs until next years TCO.<\/p>\n
Q1) Given a boolean rectangular array which maps to a hexagonal grid by shifting every second row half an entry to the right, determine the number of edges between true and false exist.<\/strong><\/p>\n A1) This is easy enough, its a simple case of walking each cell and checking its 6 ‘neighbours’ and incrementing a counter if its not the same.\u00a0 Once complete divide answer by 2.\u00a0 The only difficulty is making sure you don’t screw up the determination of the 6 neighbours, which is different depending on whether the current cell is in an odd or even row.<\/p>\n Q2) Given a list of numbers, determine the greatest number of distinct pairs which can be selected such that all such pairs are the shorter sides of a integer sided right triangle and have a gcd of 1.\u00a0 Numbers are all less than 1 million and worst case there might be 1250 numbers (less if they aren’t all single digit – maximum of 350 6 digit numbers).<\/strong><\/p>\n A2) The constraints on the pairs are pretty significant, and could easily rule out most of the numbers entirely.\u00a0 However 600 3s and 600 4s are a real possibility.\u00a0 We can easily go through each pair of numbers and work out if they are compatible.\u00a0 We can turn this into a graph with counts available for each number.\u00a0 Not certain whether the graph can contain cycles.\u00a0 If the graph can’t contain cycles, it is bipartite and we can perform a max flow to determine the answer.\u00a0 If it can contain cycles we have a problem…<\/p>\n So I checked out some answers – and yes it does seem max matching is now considered a question 2 level algorithm, not question 3 as I thought it used to be.\u00a0 However, whether there are cycles or not is not relevant, as 2 odd numbers apparently cannot satisfy the requirements (since the sum of their squares will be 2 mod 4), and 2 even numbers is ruled out by the gcd(a, b) == 1 requirement.\u00a0 Hence the pairs are bipartite based on even or odd.<\/p>\n Q3) Given a weighted tree with up to 200 nodes, determine the minimum weight sum of a tour which starts and ends at node 0, visits every edge at least once, and can teleport for cost L up to K times.<\/strong><\/p>\n A3) If K is 0, the answer is 2 times the sum of the edge weights as every edge will be traversed twice.\u00a0 If K is 1, we can subtract the longest path and add L, and choose which is best. That is to say if the depth of the deepest node from any other node is > L we will teleport between those nodes.\u00a0 However once K is > 1, it becomes a lot trickier…<\/p>\n Again looking at solutions.\u00a0 The problem is a dynamic programming problem.\u00a0 Recurse over the minimum tour length within a subtree if there are i teleport endpoints in that subtree.\u00a0 This can be determined by considering that if a subtree has an even number of teleport endpoints, it will be both exited and entered, otherwise it will only be exited or entered, not both.\u00a0 So there are n nodes, and up to 2k teleport endpoints, so the DP has O(nk) states.\u00a0 Determining each recursion requires considering how to distribute the i teleport endpoints between a nodes children.\u00a0 Considering every combination is too much, so we need to switch up the DP a bit.\u00a0 If instead of thinking about each node, we consider each edge, we realise we only need to consider each possibility for i down a given edge, not in combinations with other edges out of a given node.\u00a0 So we can instead either recurse to the left most child and all its outgoing edges, or to the ‘set of edges to the right of the left most child’\u00a0 Since the number of edges equals number of nodes -1 in a tree, the DP states is still O(nk).\u00a0 Number of possibilities to try for each case is O(k) giving O(nk^2) running time to populate the DP table.\u00a0 Once the table is populated all we have to do is check for root of the tree, each even number of end points, modified by the cost of teleporting, and determine the best result.<\/p>\n The real trick here is disassociating the end points, realising the problem can be solved without caring about specific locations teleporting to specific others.<\/p>\n This is the second time I’ve seen the ‘dfs edge walk on a tree’ DP problem.\u00a0 I should probably write up a solution to practice it.<\/p>\n","protected":false},"excerpt":{"rendered":" As is usual with SRM I didn’t do this one.\u00a0 However, I figure I might keep writing up blogs until next years TCO. Q1) Given a boolean rectangular array which maps to a hexagonal grid by shifting every second row half an entry to the right, determine the number of edges between true and false … Continue reading TC SRM 477<\/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-248","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\/248","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=248"}],"version-history":[{"count":0,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts\/248\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=248"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=248"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=248"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}