So I barely managed 615th out of the 1439 people who registered out of the 2500 potential people.\u00a0 My rating didn’t move down much as a result, but I was disappointed with my result all the same.\u00a0 Getting the second problem out was good for a guaranteed t-shirt, and solving the 1000pt was a guaranteed advancement.\u00a0 Advancement cut-off was 442 points.<\/p>\n
Q1) Given 16 values arrange them into a 4×4 grid such that sum of all edge values + double the corners + the absolute difference between neighbour pairs is maximal.\u00a0 Return the maximal sum.<\/strong><\/p>\n A1) I am not a fan of this question.\u00a0 I solved it quickly, but accidentally, with a poor solution which is not at all obviously correct.\u00a0 I then spent far too long trying to convince myself as to whether I was missing something critical, getting a low score in the process.<\/p>\n So the trick to this question is to convince yourself that the values given do not matter, if you sort them and place them the same as you would place 1 through 16 optimally, you still get an optimal solution.\u00a0 One such ordering is as follows:<\/p>\n The idea is that if you choose to have your largest 8 numbers in a checker board pattern the sum becomes 4 * sum of largest 8 – 4 * sum of the middle 2 (because they are surrounded) – 2 * sum of those on the edges (because their being on the edge offsets one of their 3 neighbours) – 0 * sum of those in the corners (because corner offsets both of the 2 neighbours).\u00a0 So it smallest 2 numbers go in the middle, next 4 smallest on the edges, and the next 2 in the corners, and the rest are checker boarded is optimal for the checker board scenario.\u00a0 A small inspection shows that the formula still holds if some of the smallest 8 are equal to some of the largest 8.\u00a0 All that remains is to prove that there is no scenario where 2 elements of the largest 8 are neighbours produces a better result.\u00a0 But I have no idea how to do that and the checker board pattern is somewhat ‘obviously’ good.<\/p>\n As a demonstration of why this problem was ‘broken’ – placing the numbers into the 4×4 square in sorted order (but not for all random orders) and them performing a greedy pairwise swap until no pairwise swaps improve the sum, would pass system tests, despite having practically no relation to the actual greedy arrangement.<\/p>\n Q2) Given a set of positions in a long narrow hallway, determine the minimum they have to move in order to get to a different set of positions, if they can only pass each other at either end of the hallway.<\/strong><\/p>\n A2) This is where I am really disappointed with my self.\u00a0 Even with all of the time wasting I did on the first problem I still had > 25minutes left after my submission.\u00a0 However because I had become convinced that I was missing something with that first question, and no one else in the room had submitted the 500pt, and one person had skipped it in favour of the 1000pt, I decided it was a better investment in my time to try and come up with a killer test case to break my (and hopefully others) 250pt question.\u00a0 Which was both a) futile since everyone else’s code passed system tests and b) unsuccessful, since my solution passed system tests…<\/p>\n So this problem really isn’t that difficult.\u00a0 Sort by starting locations to get an ordered set of indexes, sort by ending locations to get another ordered set of indexes.\u00a0 Now there are 2 basic scenarios.<\/p>\n First up, some sub-range of the starting indexes which all have the same destination indexes directly shifts to their destinations while everything to the left shifts via the left end, and everything right shifts via the right end.\u00a0 This is only valid if every item to the left has a destination on the left, and every item on the right has a destination on the right.\u00a0 This has O(N^2) scenarios each with an evaluation time of O(N) to give O(N^3).<\/p>\n The second is a bit more complicated and I might have gotten it wrong (if there wasn’t a practice question which would have picked it up).\u00a0 In this case no elements move directly to their destination, everything moves either via the left or the right ends.\u00a0 So for every possible partition point you can consider everything going left and right, and getting to their destinations via the corresponding end points.\u00a0 However this doesn’t work if the set of destination indexes of the left and right sections aren’t also on the left and right.\u00a0 The trick is that these scenarios can all work, just that some items have to visit both ends.<\/p>\n So having partitioned the starting indexes into left and right groups, you also have to partition the destination indexes into left and right groups, and if they change groups, you have to add the extra distance of having visited both ends.\u00a0 This gives O(N^2) scenarios each with an evaluation time of O(N) to add an addition O(N^3).\u00a0 Input constraints were at most 50 items, so the result is easily managed.<\/p>\n Q3) Given a tree with black disks on some (non-root) nodes and a red disk on the root node, determine which nodes the red disk can visit by sliding along edges, if disks cannot pass through each other, but are otherwise all free to move along edges.<\/strong><\/p>\n A3) Only 6 people solved this successfully, and none of the solutions are trivial to read and understand.\u00a0 General idea seems to be that you cache the number of black disks and the number of nodes for each sub-tree and then use that to determine whether the black disks can be shuffled out of the way to let the red disk to visit.\u00a0 If a node has multiple children and can be visited by the red disk, and not all of those children are filled, the red disk can visit some of the children, and potentially the black disks in the other children can be shifted up and into available spaces else where on the tree, allowing the red disk to reach even more locations.\u00a0 I think this logic gets applied repeatedly until no more red disk reach locations can be found.\u00a0 Without the cache the solution would be too slow.<\/p>\n","protected":false},"excerpt":{"rendered":" So I barely managed 615th out of the 1439 people who registered out of the 2500 potential people.\u00a0 My rating didn’t move down much as a result, but I was disappointed with my result all the same.\u00a0 Getting the second problem out was good for a guaranteed t-shirt, and solving the 1000pt was a guaranteed … Continue reading TCO14 R2A<\/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-759","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\/759","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=759"}],"version-history":[{"count":0,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts\/759\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=759"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=759"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=759"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}16 3 15 8\n 4 14 1 13\n12 2 11 5\n 7 10 6 9<\/pre>\n