The problems in this round were just a tiny bit easier and it showed – qualifying required 2 whole problems, or a good time on 1 whole and 2 smalls.<\/p>\n
Q1) Given a rectangular array where some tiles are marked with a hash, replace it with a new array where the same tiles which were marked with a hash are marked with 2×2 arrangements of ‘\\’ and ‘\/’ which look like diamonds.\u00a0 This may not be possible, if not then return as much.<\/strong><\/p>\n A1) Pretty straight forward question, the key is to identify that if a hash mark has nothing to its left or above, it has to be the top left corner of a 2×2.\u00a0 So replace the whole 2×2 immediately.\u00a0 If this overlaps with the edge of the array, or any of the 2×2 aren’t marked, fail immediately.\u00a0 Once done, repeat until complete or fail.\u00a0 A simple left to right, top to bottom walk solves the problem quickly and efficiently enough.<\/p>\n Q2) Given a sequence of stars, and a distance between each you want to travel from the first star, to the final star in as short of time as possible while stopping at every star in the exact order given.\u00a0 To slightly complicate things your engineers can build up to L speed boosters on stars.\u00a0 These speed boosters take a time t to be built, but once built all travel between the star it was built on, and the next star in the chain is performed at double speed.\u00a0 This even applies if the space craft is between those stars when the building completes.<\/strong><\/p>\n A2) With the large input claiming up to 1million stars, this problem looks a bit scary at first.\u00a0 However a quick think and you should realize that a greedy algorithm applies.<\/p>\n The answer is (sum of the distances)\/speed – (sum of speed boost benefits).\u00a0 Since the first part is a constant, and the second part has a constant number of components – the minimal time comes from maximising each component in the sum of speed boost benefits.<\/p>\n So, simply calculate the speed boost benefit for each star, if a speed boost was built there, and then sort the array descending (no problem for 1 million entries using merge sort), and sum the first L elements.<\/p>\n Only things to watch out for are using 64bit integers and ensuring that your speed boost benefit formula correctly uses t and covers all 3 scenarios – ‘useless’, ‘full benefit’, ‘space craft in mid-flight when building completes’.<\/p>\n Q3) Given a list of N integers, determine the smallest integer in the range L to H which either divides or is a multiple of each integer in the list, if such an integer exists.<\/strong><\/p>\n A3)\u00a0 I solved this one on my own for a change, but the implementation for the large input is a bit hairy – so high risk I would have failed during competition.\u00a0 The small input constraints allowed a trivial brute force so many people submitted that on its own.<\/p>\n The key is to sort the integers, then the answer is either smaller than the smallest, or larger than the largest, or part of one of the segments now described by each consecutive pair.<\/p>\n Lets treat each case separately for now.\u00a0 Less than the smallest, determine the GCD of all numbers, and find the smallest divisor of that GCD which is in the range L-H.\u00a0 If L>GCD – nothing, otherwise can generate all divisor pairs by walking the integers 1 to Sqrt(GCD). Larger than the largest, determine the LCM of all numbers, and if less than L use a quick division to determine the first multiple of the LCM which is in the L-H range.\u00a0 If greater than H, obviously no answer.<\/p>\n This leaves the gaps.\u00a0 Based on these two cases above it should become apparent what is required.\u00a0 Determine the LCM of the first numbers, and the GCD of the rest.\u00a0 Then the answer is a multiple of the LCM which also divides the GCD.\u00a0 Obviously this won’t work if the LCM doesn’t divide the GCD, so that is a quick check.\u00a0 Next L<->H must overlap with the LCM<->GCD range or there is no point trying.\u00a0 If LCM is in the L<->H range, obviously we are done.\u00a0 Otherwise we walk the integers 1 to Sqrt(GCD) again, checking to see if any divisor pairs contain a multiple of the LCM in the L-H range.\u00a0 Choosing the smallest if there are multiple options.<\/p>\n So putting it all together, generate the LCMs starting from the left, and the GCDs starting from the right, try the less than smallest, then walk each consecutive pair of the sorted order, and finally the greater then largest and if at any time a solution is found in any of these parts, return it.<\/p>\n So I mentioned that the large input was a bit hairy and this is because of the LCM calculations involving numbers which are up to 10^16.\u00a0 Using BigInteger saves you from overflow risk, but unless you realize that there is no need to continue calculating LCMs once they exceed 10^16 (since they are greater than the maximum H value) you run the risk of performance being a problem as BigInteger becomes slower as the size of the data increases.\u00a0 Using a 64bit integer is okay, but you need to hand code or otherwise check for overflow in multiplication, and you need to apply the GCD division before the multiplication!<\/p>\n Performance wise the biggest cost is the walk from 1 to Sqrt(GCD) as this can be up to 10^8 modulo operations.\u00a0 Luckily this can only happen for at most 1 segment, but in case 100million modulo operations is too scary, an improvement to the average case is to divide the L<->H range and the GCD by the LCM.\u00a0 With the L<->H range round inwards, the GCD will divide cleanly.\u00a0 Then you can start with ceil(L\/GCD), walking up wards to Sqrt(GCD\/LCM), then jump back to just below ceil(L\/GCD) and walk down to the first divisor for which the other side of the pair exceeds H\/LCM.\u00a0 This doesn’t improve the worst case, but does give you early out and reduced calculation space in the average case.<\/p>\n","protected":false},"excerpt":{"rendered":" The problems in this round were just a tiny bit easier and it showed – qualifying required 2 whole problems, or a good time on 1 whole and 2 smalls. Q1) Given a rectangular array where some tiles are marked with a hash, replace it with a new array where the same tiles which were … Continue reading GCJ11 R1C<\/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-387","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\/387","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=387"}],"version-history":[{"count":0,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts\/387\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=387"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=387"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=387"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}