Last on-line round of the TCO\/GCJ ‘season’.\u00a0 138 people eligible to compete, 125 turned up.\u00a0 Unlike last time the first 2 problems were completed by a significant proportion, so advancing required a fast time for both the first 2 problems.\u00a0 Only one person solved all 3, the same person also had the only solution to the 3rd problem.<\/p>\n
Q1) Given a sequence of numbers where each element is between 1 and n, determine how many sequences of equal length with each element also between 1 and n are a ‘match’ with the original sequence if you remove one element from each sequence.\u00a0 Since the answer is large, return modulo large prime.<\/strong><\/p>\n A1) At first glance this doesn’t seem too complicated, consider the original sequence, remove each element in turn, and count how many sequences you can create by adding one element.\u00a0 The problem is of course that this double counts.\u00a0 Even just considering a single case, if you insert the same value before\/after a given number, the sequences are the same.\u00a0 So either we need to determine how many double counts occur and subtract them off, or use a different approach entirely.<\/p>\n Looking at a solution (because I feel lazy today) scenarios can be divided in to 2 cases. Where the number we insert is a member of the original sequence, and where it is not.\u00a0 If it is in the original sequence, we have complicated possibility of double counting, if it is not, then it is much simpler.\u00a0 So for each element removed (up to 50 cases) for each insertion position ( up to 50 places) for each distinct original value (up to 50 values) we have something which needs checking for duplicates.\u00a0 This is a fairly small sample size, so we can easily use a set.\u00a0 For each of the element removed, for each insertion position, we can also insert the n-distinct_count_options other values.\u00a0 There is still the ability to double count here, but these cases can be grouped by what the inserted value is (regardless of whatever that value is), so we can use a place holder (0 for instance) and the same set, and each time we get a non-match we add n-distinct_count_options to the final result.<\/p>\n Q2) Given pairs of values, determine the minimum number of individual value swaps (swapping one value from one pair with one value from another pair) is required such that all pairs have a maximum difference of k.\u00a0 If it is impossible, return -1.<\/strong><\/p>\n A2) There is only a maximum of 16 pairs here, which suggests bit-masks may play a role.<\/p>\n But again, I am feeling lazy today, so I went straight to a solution.\u00a0 The first step is to determine whether the problem is possible at all.\u00a0 It seems that if you take all the values from the set of pairs, put them together, and sort them, they must fall out pairwise into values which are close enough.\u00a0 The logic behind this seems to be rather straight forward – if you consider the smallest value you need a value close enough, and if there are multiple which work, choosing anything other than the smallest of those, can only potentially make it harder to form the next pair.<\/p>\n To find the minimum number of swaps we can look at this problem from a different angle.\u00a0 Any solvable situation can easily be done in at most n-1 swaps, if we look at the sorted order pairing, we can swap the second to be next to the first, the 4th to be next to the 3rd, and so on, until the final number is already in the right place, the question is how much can we short cut that.\u00a0 If we have a solvable scenario which can be divided into 2 solvable subsets, worst case we can do the first in k-1 steps and the second in n-k-1 steps, giving n – 2 steps.\u00a0 What remains is to determine the most number of steps which can be saved, by following this down recursively.\u00a0 The maximum number of steps which can be saved by a scenario is the best sum of the maximum number of steps that can be saved over each partition into 2 solvable subsets.\u00a0 With a minimum of 1.\u00a0 Since we already have worked out how to determine if a situation is solvable, we can perform that for every subset, then considering every subset, of every subset (which is not a small number, but is achievable), determine if that subset and its compliment are both solvable, and use that as the framework to build up a recursive cache of maximum number of steps to be saved for a given subset.\u00a0 Then the final answer is n – maximum number of steps saved for the full set, assuming it is solvable.\u00a0 If it isn’t the answer is of course -1.<\/p>\n Q3) Determine the minimum number of jumps to get from 0,0 to x,y if each jump can’t be more than a distance sqrt(d) in a straight line, and jumps may only be to\/from integer coordinates.<\/strong><\/p>\n A3) Unusual bit here is that rather than just asking this question once, each test case can be up to 50 of these questions, which you have to answer all at once.\u00a0 For d=1 the answer is |x| + |y|.\u00a0 For d=2 the answer is max(|x|,|y|).\u00a0 From there the question that first needs to be asked I think is whether a greedy solution is correct.\u00a0 If so we should be able to find a pattern in the jumps which repeats and use that to ‘accelerate’ to the finish.<\/p>\n Looking at the solution again, it appears some fancy maths comes into play.\u00a0 Given d, you start off by determining the pair of maximal distance jumps which are either side of the angle connecting 0,0 to |x|,|y|, do this by constructing each possible maximum distance jump and watching the crossproduct change signs as we go from one side to the other. (May want to take care of the x= 0 or y = 0 cases separately just to be sure you don’t screw that up.)\u00a0 Once you have this pair of vectors it just becomes a question of how many of one and how many of the other to add together to give the right destination.\u00a0 This is where the maths seems to get a bit fancy.\u00a0 Taking directly from the solution, the answer is crossproduct((x,y),V2-V1) \/ crossproduct(V1, V2-V1), rounded up.\u00a0 I’m not quite sure how to derive this exactly, but at first glance I wouldn’t say it was wrong.<\/p>\n","protected":false},"excerpt":{"rendered":" Last on-line round of the TCO\/GCJ ‘season’.\u00a0 138 people eligible to compete, 125 turned up.\u00a0 Unlike last time the first 2 problems were completed by a significant proportion, so advancing required a fast time for both the first 2 problems.\u00a0 Only one person solved all 3, the same person also had the only solution to … Continue reading TCO13 R3B<\/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-710","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\/710","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=710"}],"version-history":[{"count":0,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts\/710\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=710"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=710"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=710"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}