So I wasn’t in this round since I already advanced to round 2, and I was too late getting back to the topcoder website to see the scoreboards, so this will just be a problem discussion.<\/p>\n
Q1) Determine the first prime found in a sequence starting with N, or return -1 if not found in N steps. \u00a0Sequence is to replace X with the sum of the squares of its digits.<\/strong><\/p>\n A1) \u00a0One terminal is if you get to the value 1 you can immediately return -1, because it will never change again. \u00a0However more generally it is not difficult to observe that once X is less than 200, it never goes over 200 again, and regardless of X (at least for up to 1 billion), it will be less than 200 in at most 3 steps. \u00a0Therefore if there is any repetitive loop other than reaching one, the number of steps to identify the cycle is no more than 200. \u00a0So just keep a hashset of values seen so far, and if you see something you’ve seen before, return -1. \u00a0Otherwise its just testing primality and breaking up digits and summing their squares in a loop. \u00a0Possibly also be careful for small starting N that you don’t run your loop more than N times looking for a cycle, but given the density of small primes, its not obvious there is such a scenario to worry about.<\/p>\n Q2) Given the ability to replace digits using a pool of specific counts of digits (no zeros) and an original list of numbers, determine the maximum sum that can be created by modifying the original list of numbers using the pool of replacement digits.<\/strong><\/p>\n A2) This is a straight greedy problem. \u00a0The final sum depends on which digits are replaced with what values in what positions in the numbers, but not the order you make the changes. \u00a0Therefore for each digit available you replace them with the highest available digit that increase the number, and you prioritize the ones which provide the greatest increase in local value, since that increase is the same increase applied to the final sum. \u00a0As there are only 350 digits at most to consider, you could just do an O(N^2) algorithm to find the greatest increase, apply it, then try again until the pool runs dry or there are no more possible increases to the sum.<\/p>\n For an improvement to the run time you can sort the candidate digits by their place, descending power of ten, breaking ties by their digit, ascending. \u00a0Then you just walk through them replacing each with the best available improvement.<\/p>\n So I kind of glossed over why this works, it isn’t perfectly obvious since if your pool consists of only 9’s and 2’s and you use up all the 9’s on large numbers starting with 1, and the rest of the numbers don’t have any 1’s in them, those 2’s are going to waste. \u00a0However when you use a number, the number of digits which go to waste is at most 1. \u00a0Because the wastage is further down the sorted sequence, it either has a lower place (and hence even at 0-9 its 90% of the improvement that just increasing the current place one higher that is the minimum you get when invoking the wastage) or the same place but with a smaller difference, in which case the ideal is to take the 2 highest digits which is exactly what happens in the wastage scenario.<\/p>\n Q3) Given a sequence of values and multiple ranges that it costs 1 unit to increase value by 1 and one range that covers the full sequence that it costs T units to increase the value by 1, determine the minimum cost to create a sequence of values which is never less than the original sequence.<\/strong><\/p>\n A3) The number of ranges, length of the sequence, and potential range of values in each spot are all at least up to 10^5, so its clear that you need a very efficient solution. \u00a0This problem is a clear step up in difficulty from the previous two.<\/p>\n So due to the high data input sizes my mind immediately went to a minimum find search on the number of units to spend on the range that costs T, then for each potential number of units spent under consideration we need to solve the minimum cost to spend on the other ranges in linear time.<\/p>\n As it happens solving the inner problem isn’t trivial either, to run in linear time you need some pre-computation. \u00a0Sort the ranges by their start points, breaking ties by the end point descending. \u00a0Then\u00a0walk through and discard any ranges that don’t increase the end point, these ranges are fully contained by the current element, so are useless. \u00a0Now that we’ve got a more useful set of ranges (in O(N log N) time), we still need to do more pre-computation to allow for the inner loop of the search to be linear time. \u00a0The aim is to compute for each sequence position the end of the right most range which covers it. \u00a0(The reason this is useful I’ll explain below.) \u00a0First fill the list with -1 to represent places that aren’t covered at all. \u00a0With our sorted list the covered bits are easy, if the next element’s start is lower than the current end point, fill from this start to that start with the current elements end point, otherwise fill from start to end with that end point. \u00a0Then move onto the next element and repeat. \u00a0This is linear because no place is written more than twice.<\/p>\n So now that we’ve got this computed table minimum cost isn’t so hard to calculate in linear time. \u00a0Consider the left most position which isn’t already satisfied – everything to its left is all good, so there is no point increasing values in that area any more. \u00a0So the ideal range to increase is the one which covers this point, and covers at much to the right as possible. \u00a0Conveniently that’s what we already calculated. \u00a0So we determine the number of points to spend then apply that till the end point? \u00a0Not so fast, if all the ranges are about half the length of the sequence one step after another, you’ll suddenly have an O(N^2) algorithm. \u00a0Instead you need to keep track of how much you are currently adding, and mark the end point to decrement that addition by how much you just added. \u00a0Then you just walk along, if there is more needed, increase the spend, apply to the current location, mark when to decrease it, if there was a mark on this position, decrease the spend. \u00a0Accumulate the total spend increases to give a final total. \u00a0If there are any places where you are short and there is no covering range (as indicated by -1) abort and return infinity as the cost.<\/p>\n So all that remains is the minimum find search. \u00a0A ternary search is one option to consider, but care is required because ternary search won’t survive a plateau which is not the minimum, and there could be multiple values where you return infinity for. \u00a0So you need to special case infinity to always cut off the low third\u00a0even if both of the probe points are equal. \u00a0Another alternative to the ternary search is to use a binary search on slope, looking for zero, if you don’t find zero, you can take the first element with positive slope to the right. \u00a0Again with the binary search on slope you have to take care of the infinities, they appear to have zero slope when next to each other, but should be considered to have negative slope.<\/p>\n","protected":false},"excerpt":{"rendered":" So I wasn’t in this round since I already advanced to round 2, and I was too late getting back to the topcoder website to see the scoreboards, so this will just be a problem discussion. Q1) Determine the first prime found in a sequence starting with N, or return -1 if not found in … Continue reading TCO16 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-827","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\/827","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=827"}],"version-history":[{"count":0,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts\/827\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=827"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=827"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=827"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}