Again a late night, and again a poor performance.<\/p>\n
I was faster on the 250pt question this week, but I probably spent more time testing than I needed to.\u00a0 Still 217 is acceptable.\u00a0 Unfortunately, at the prior to systest phase, the top 600 lowest score is 300 and I failed to get the 500pt.\u00a0 So I sit in 750th, hoping for a huge number of failures in the 500pt problem that I struggled with.\u00a0 I definitely saw a few solutions which were greedy in nature in my room, and although I couldn’t find a counter example, greedy is usually high risk.\u00a0 I guess I’ll find out shortly.<\/p>\n
Greedy solution passes… but still quite a few failures, enough for me to go up to 646th.\u00a0 Just 11 points from cut-off this time.\u00a0 R1C here I come?<\/p>\n
Q1) Given up to 50 objects with lengths between 1 and 50 inclusive, determine the largest k where you can make k rows of length k either by using a single object or 2 objects separated by a gap of 1.<\/strong><\/p>\n A1) Nice easy problem.\u00a0 The answer is obviously in the range 0-50, and its not too hard to verify possibility, so try each one descending until it works, or you reach 0.\u00a0 To verify, sort the objects, any object larger than k can be discarded, every object equal to k, count that up.\u00a0 Then perform an inward walk of those left checking for sum equal to k-1.\u00a0 If sum equals step both ends inwards and increase your count, if sum smaller move the bottom point up, if the sum is greater move the top point down.\u00a0 Continue until the points meet or cross.\u00a0 If the count is greater or equal to k, then its possible to make the k rows needed.<\/p>\n Q2) Given up to 50 tasks which take time between 1-3600 time units, determine the minimum time to complete the tasks subject to the following strange constraint.\u00a0 You have a single worker, each worker can only do one task.\u00a0 However a single worker can split into 2 workers in time t.<\/strong><\/p>\n A2)\u00a0 The greedy solution is to sort in descending order and replace the 2 smallest entries with the largest of those two plus the split time.\u00a0 Repeat until there is only one task remaining and return its time.\u00a0 Very simple, but is it correct?\u00a0 The answer is yes.<\/p>\n The path I erroneously took was to try and determine the minimum time to perform the largest i tasks and have k workers left over.\u00a0 However I couldn’t get this to work because my formulation didn’t allow for the other tasks occurring after a split but still concurrently with another task.\u00a0 I actually realised this fairly early on and tried to formulate a reverse search more like the greedy solution, but I got confused, went round in a circle and started working on the same broken approach again. (Way too tired!)<\/p>\n ‘Proof’ for greedy solution.\u00a0 You can treat the splitting of workers as creating a tree.\u00a0 Each leaf node of the tree does some work.\u00a0 There are no empty leaf nodes because any empty leaf node could be removed and its parent replaced with the other branch.\u00a0 In an optimal solution the 2 smallest items will be at the deepest level of the tree.\u00a0 As if they are not, then they can be switched with any non-deepest leaf node and the solution either improves or stays the same.\u00a0 Furthermore all deepest levels are reached at the same time point, so you can freely interchange any leaf at the deepest level without changing the total time for that tree.\u00a0 Hence, the two smallest nodes can be made to share a common parent.\u00a0 This pair of two smallest nodes and their parent can be replaced with a single leaf which takes as long as the longest of the two smallest nodes plus the split time.\u00a0 This results in an equivalent problem with an identical solution presuming we have started with an optimal solution for the original problem (I don’t have a strong proof of that, but it appears obvious – decomposing a node can only make it easier to arrange the tasks to achieve an optimum so if we are already optimum, we are also optimum for composition).\u00a0 We can now start all over again, but we have 1 less leaf node.\u00a0 Hence we can repeat until we only have 1 node, and the total cost is now obvious.<\/p>\n Q3) Given two rows of equal length of up to 16 people each with heights between 140 and 190, determine the minimum number of adjacent people swaps such that every member of the second row is larger than its corresponding member in the first row.<\/strong><\/p>\n A3)\u00a0 Interesting question… the limits of only up to 16 people suggests an exponential search is feasible.<\/p>\n Looking at one of the passing answers, it looks like an exponential search on the minimum number of swaps to make the first k elements correct, looking at every possible subset of the k-1 swap locations.\u00a0 I’m not sure how this accounts for swap ordering… maybe I’ll work it out after some sleep.<\/p>\n So, post sleep revisit…\u00a0 The approach is to determine the minimum number of swaps required to have index i and smaller satisfy the criteria using i out of the available slots.\u00a0 The tricky bit in understanding the solutions is that they use a compact state space.\u00a0 If you use a bit field, with i bits removed, the fact that there are i bits removed indicates that those numbers were placed in the first i slots, in some order.\u00a0 So all bits set means any ordering, so that is where we start.\u00a0 For each set bit, we consider moving that value to the beginning.\u00a0 This will take a number of swaps equal to the distance between the start and the candidate, the rest of the values will retain the same order, and obviously we only do this if moving it results in a satisfiable condition.\u00a0 We now have a bunch of new bit fields to determine the minimum swaps for, with the bit corresponding to the moved index removed.\u00a0 So looking at each new state we can determine which index we are moving to by counting the number of gaps, and we can start again.\u00a0 However when it comes to distance to move to the new spot, we have to account for the fact that in moving an item to the left, the items to its left have all moved right 1.\u00a0 Conveniently we can determine this from the bit field.\u00a0 Each 0 bit corresponds to something which was moved, so if we pretend the 0 bits aren’t there and align right, that’s where the candidates are currently placed.\u00a0 So the count of set bits to the left of the candidate to move gives the number of swaps.<\/p>\n This recursion can be memotized over the bit field to ensure it runs fast enough.\u00a0 Terminal condition is the empty bit field which has a cost of 0.\u00a0 All that remains is to prove this approach correct…<\/p>\n Looking at the recursion from the inner most levels first.\u00a0 Obviously if all are in the right place, the cost to move them into the right place is 0.\u00a0 If all but 1 of the left most spots have been made correct, obviously the rightmost must stay still, and if it is in the correct spot, the cost is 0.\u00a0 If all but 2 of the left most spots are correct, either we swap or we don’t.\u00a0 If we swap the cost is 1, otherwise the cost is 0.\u00a0 The recursion will try both options so there is definitely no loss of generality yet.\u00a0 All but 3.\u00a0 In this scenario if the ideal scenario has the right most moving left 2, there is nothing to gain by swapping the other 2 first, it just increases the cost now and increases the search space, we can leave deciding whether to swap those until after swapping the right most across without any lower cost scenarios lost.\u00a0 Thus demonstrating that we do not lose generality. (Not a proof, but doesn’t look too hard to formalize.)<\/p>\n Now if you’ve been paying close attention you’ll notice I left something out completely.\u00a0 Everything above presumes that you only swap the people in the front row, or only in the back row.\u00a0 I can’t see a good way to demonstrate why this still leads to the correct solution, but intuitively, mixing front and back swaps serves to lose the ability to chain the swaps in order to place items in the correct spot.\u00a0 In order to perform the chaining you end up needing to do the corresponding front swap for a back swap or vice versa (or simply repeat the same swap again, either way it seems obvious that the number of swaps is increasing).\u00a0 In some scenarios mixing the swaps doesn’t make things worse, but it does not provide ways to make things better.<\/p>\n","protected":false},"excerpt":{"rendered":" Again a late night, and again a poor performance. I was faster on the 250pt question this week, but I probably spent more time testing than I needed to.\u00a0 Still 217 is acceptable.\u00a0 Unfortunately, at the prior to systest phase, the top 600 lowest score is 300 and I failed to get the 500pt.\u00a0 So … Continue reading TCO 2012 R1B<\/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-492","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\/492","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=492"}],"version-history":[{"count":0,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts\/492\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=492"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=492"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=492"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}