I’ll only cover the take 2 questions here, even though I thought the take 1 questions were better…<\/p>\n
Q1) This question was a convoluted way of asking ‘what is the minimum number of neighbour swaps to sort a list containing 2 unique (but potentially repeated) elements’.\u00a0 It was phrased a bit to confuse, but that is what it boiled down to.<\/p>\n
I implemented this by hand writing a bubble sort and counting every swap, which was simple and for the input size, easily going to perform in time.\u00a0 A more optimal solution (which takes advantage of there only being 2 entry types)\u00a0 is to step through each entry, keeping a counter of how many of the type of element you want to be first you have seen so far.\u00a0 Each time you encounter an element of that type, increase your result field by the difference between the current position and the number of elements of that type already seen.\u00a0 This computes the result in O(N) rather than O(N^2). Oddly enough I swear I’ve seen this question somewhere else recently…<\/p>\n
Q2) This one was a bit more tricky.\u00a0 The question was, given a short (up to 10) list of UDLR direction commands, and a number of times to repeat them, and assuming every move is unit size, how many unique locations will you end up visiting?\u00a0 The trick being the number of times to repeat them was up to 100 million…<\/p>\n
The solution to this comes from realising that after the first few repetitions of the direction commands the number of new unique spots per repetition will always be the same.\u00a0 I didn’t bother proving a minimum number of repetitions before it stabilises, which I suspect may be quite low, I just chose 20 to be on the safe side (current estimate is that 4 repetitions is sufficient for a command list maximum length of 10).\u00a0 Use a set (dictionary since topcoder still only supports .Net 2.0) to store the locations you have visited, and simulate the the first few replications, storing how many new are added for every attempt. Then simply multiply the last number of new spots by the number of repetitions left, and add that to receive your final total.\u00a0 I simplified my code by storing my location as a single integer rather than a pair, using 15 bits for one axis and the rest for the other.\u00a0 Since the number of repetitions simulated is only 20 and the number of steps per reptition is 10, 15bits is overkill, but whatever…<\/p>\n
Q3) This of course was the hardest question, and I didn’t get it completed in time. This question was a bit complicated, but it involved up to 50 different ‘lists’ being unioned together and sorted.\u00a0 The lists themselves could be distinct values (stored in 50 characters, so at most 24 numbers) or a description of an arithmetic or geometric sequence.\u00a0 The sequences were defined with start number, step\/multiplier, number of elements in the sequence.\u00a0 The program had to take this sorted union and return what element was at a given position in the list (for up to 50 positions).\u00a0 Where that position was anything up to 1billion.\u00a0 To simplify things a bit if the value at a position was over 1 billion, you were to return -1, and if the position asked was beyond the end of the sorted union, also return -1.\u00a0 However to annoyingly complicate things, the input numbers were not gauranteed to fit in 64bit integers, although it was guaranteed that they would all be greater than 0.<\/p>\n
Parsing the input was really much of the problem.\u00a0 The restriction that values over 1billion return as -1 and positions beyond the end of the sorted union return -1 means that because it is sorted, you can ignore every value over 1billion and pretend it is not in the list.\u00a0 Therefore int.TryParse and a check that the result if valid was less than or equal to 1 billion was sufficient for each field of the input.\u00a0 Depending on which field what to do with the fact that the value is > 1billion you did have to treat it differently.\u00a0 For the exact lists you could just throw each excessive element away.\u00a0 For the sequences if it was the starting value, you could throw the entire sequence away.\u00a0 If it was the multiplier\/increment then you could replace the sequence with an exact list containing just one value.\u00a0 However if it was a sequence length, you need to treat it as at least 1 billion.<\/p>\n
Another side step which can be performed to reduce the problem space a bit is to realise that geometric sequence with a multiplier greater than 1 will all exceed 1 billion in 30 repetitions or less – so you can expand them into exact element lists.\u00a0 With a multiplier of 1, you can replace them with an arithmetic sequence with step 0.\u00a0 Therefore the rest of the code only has to handle arithmetic sequences and exact lists.\u00a0 All of the exact lists can be combined and sorted so all that is left is a single exact list (might be empty) and up to 50 arithmetic sequences.\u00a0 If you wanted all arithmetic sequences with length less than 30 or so could be treated as exact lists as well, but it doesn’t really help anything.<\/p>\n
Finally now that the data is all prepared you have to find the actual values at given indexes.\u00a0 This cannot be done by generating the first 1 billion entries, for one thing it would exceed the time limit, but for the other it most certainly would exceed the memory limit.\u00a0 The solution comes from performing a binary search.\u00a0 A binary search on what? A binary search on the ranges of positions which have a given value.\u00a0 If the position we are after is in a range, it has the value for that range.\u00a0 The function we need to implement the binary search is ‘how many numbers are less than n’.\u00a0 We then binary search on n over the range 0 to 1billion asking the function for n and n+1. If the answer to the first question is greater than our required index, the answer must be smaller than n.\u00a0 If the answer to the second question is less than or equal to our required index the answer must be greater than n.\u00a0 Otherwise the answer is n.<\/p>\n
Answering how many numbers are less than n for the exact list is trivial, since we sorted it.\u00a0 You can even use a binary search, since the number of elements may be as high as 1500.\u00a0 For the arithmetic sequences you can take n+1 subtract the start value, if result is negative return 0 else divide by the step size (using integer division) and add 1. Unless the step size is 0, which we introduced when getting rid of the\u00a0 geometric sequences, in which case the answer is infinity (aka 1 billion) if n+1 is greater than or equal to the start value.\u00a0 Whatever answer found has to be capped by the maximum number of entries for the sequence as defined previously. Finally the answer for each sequence and the exact list are summed, being careful not to overflow integer (since you could be adding the number 1 billion 50 times).\u00a0 For an added performance kick this function can be memotized in case the different position queries end up passing in the same values.\u00a0 It won’t make a huge difference to performance since the input values can be spaced such that only 5-6 out of up to 30 binary search steps will overlap for each query.<\/p>\n
I ran out of time when I was just about to start implementing that final paragraph – but there was plenty of opportunity for off by one errors which I probably would have wasted a good 10 minutes fixing.<\/p>\n","protected":false},"excerpt":{"rendered":"
I’ll only cover the take 2 questions here, even though I thought the take 1 questions were better… Q1) This question was a convoluted way of asking ‘what is the minimum number of neighbour swaps to sort a list containing 2 unique (but potentially repeated) elements’.\u00a0 It was phrased a bit to confuse, but that … Continue reading TCO10 QR1 Analysis<\/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-127","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\/127","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=127"}],"version-history":[{"count":0,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts\/127\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=127"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=127"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=127"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}