A quick look at how people performed in this round shows it to be a very tricky round.\u00a0 No perfect scores this round, but with only 25 people advancing to the finals, unless you solved question 4 large (which was worth 31 points and only had 1 person solve it correctly), you needed everything else and a decent time to advance. Representing Australia, tikitikirevenge came close in 48th place.<\/p>\n
Q1) Given an irregular shape defined by two poly-lines with identical start and end x coordinates, and continuously increasing x coordinates in between (but each poly line itself may have a different number of points) and these poly lines do not intersect.\u00a0 Determine G – 1 x coordinate positions where cuts with dx=0 (vertical) divide the shape into G equal parts.<\/strong><\/p>\n A1) First thing to do is to break the shape into trapeziums, at each x coordinate specified in the 2 poly lines, taking care for the case where the x-coordinates are identical, and otherwise having to determine the y coordinate for the other side using interpolation. Area of a each trapezium is easy, so we can then work out the total area, and the G equal sub divisions of that total area.\u00a0 Iteration easily finds which trapezium contains each division point, all that is left is determining where in the trapezium the appropriate point is.\u00a0 This could be done using a binary search, or simply derive the equation (which will be quadratic) and solve for the position given the target area (second solution will be outside the trapezium).<\/p>\n All in all, this question is fiddly but very doable.\u00a0 Not surprisingly then this was the question with the highest success rate.<\/p>\n Q2) Given a set of N numbers each between 1 and 10000 inclusive, with possible repetition, you want to organize them into sets of consecutive integers such that the smallest such set is maximal.\u00a0 What is the size of that maximal smallest set?<\/strong><\/p>\n A2)\u00a0 Small input size is 10, and so a brute force approach is plausible there.\u00a0 Large input is up to 1000, which is much less friendly.<\/p>\n Firstly I think it is useful to break the problem down.\u00a0 If you sort the numbers, you can then break the problem into sections based on where there is a gap in the sorted sequence.\u00a0 The answer is then the minimum of the answer for each section.<\/p>\n Now all we need is the answer to a given section.\u00a0 Where ‘all’ is pretty much the entire problem.\u00a0 Obvious cases first.\u00a0 Same number of repetitions for every value; answer equals set size.\u00a0 If the repetition of a single value is greater than the sum of the repetitions of its neighbours, the answer is 1. In any case that we get an answer of 1, we can avoid looking at all other sections.<\/p>\n That still leaves a fair bit to consider.\u00a0 Anywhere that the repetition count increases has to be the start of at least a number of sequences equal to the difference.\u00a0 I am wondering if the greedy approach of starting no more sequences than required, and when the count decreases, stopping the oldest sequences, will produce the ideal answer.\u00a0 It certainly seems sound on the first glance. A quick check of the answers shows this to be the solution.<\/p>\n Definitely a lot more thinking than the first problem, but again doable.<\/p>\n Q3) There is an RxC grid where each square contains a conveyor belt which points either vertically, horizontally, or one of the 2 diagonals.\u00a0 Each conveyor belt has an individual direction control.\u00a0 Determine how many out of the 2^(R*C) possible scenarios result in the conveyor belts pointing only in loops. (I.E. No cell can have 2 cells pointing to it.)\u00a0 The grid wraps around on to itself ‘by the miracle of science’.\u00a0 Answer modulo 1000003 to avoid huge answer problems.<\/strong><\/p>\n A3) Small input RxC is up to 4×4, so only 2^16 scenarios to investigate, and each scenario can be checked relatively quickly, simply by counting how many cells point to each cell.\u00a0 So, small input is trivial (and it receives a tiny number of points too).\u00a0 Large input is 100×100 – hence why we need that modulo.<\/p>\n Special cases – a cell might have nothing that can possibly point to it, causes a result of 0.\u00a0 Also a cell might have only one thing pointing too it, hence the direction of that conveyor is ‘defined’. A straight line loop of conveyors has 4 possibilities if length even, 2 if length odd.\u00a0 Any such loops can be removed from the graph as a multiple of the answer obtained otherwise.\u00a0 Otherwise the puzzle contains no reversible loops.\u00a0 Which is a bit of a pain really, because it means decomposition appears infeasible.<\/p>\n At this point I’m pretty sure I’m out of my league, so I shall consult the answers.\u00a0 Interesting!\u00a0 Having repeatedly forced conveyors where a cell has only one option pointing to it, and exiting if there is ever no options for a cell, an interesting thing occurs.\u00a0 Every remaining partially (or complete) undecided cell has either exactly 2 options for how conveyors point to it, or away from it (or both), due to conservation of edges.\u00a0 This implies that choosing one direction, always results in forcing a direction, which in-turn forces another until you come round in a loop, and since you come round in loops, the problem is decomposable after all.\u00a0 Each of these ‘loops of force’ is entirely independent and contributes exactly 2 independent ways to solve the problem.\u00a0 So count the loops, and keep doubling modulo 1000003 to get the answer.<\/p>\n In competition I doubt I would have gotten this out.\u00a0 The fact that the ‘loops of force’ aren’t constructed of consecutive cells makes it hard to observe by accident.<\/p>\n Q4) Given a binary representation of a square number, where some of the bits have been replaced with question marks (but not the highest set bit), determine the original number. (Only one answer will be possible.)<\/strong><\/p>\n A4) Small input constraints of maximum 60 digits and at most 20 question marks made brute force an obvious and trivial course of action.\u00a0 This was actually answered more frequently than the easy answer to question 3.<\/p>\n The large input only had one person successfully solve it it, so I don’t feel too bad that nothing springs to mind.\u00a0 Constraints were 125 digits and up to 40 question marks.\u00a0 My first thoughts are, maybe fill in the highest 20 question marks with each possibility, and then get the bounds of the 64bit integer which matches the lower 20 question marks, and then try each one.\u00a0 Problem is, in the worst case scenario, that appears to be even worse than brute forcing all 2^40 scenarios.<\/p>\n A few little trivial cases to get started.\u00a0 If the right most digit is 0, it and the digit to its left can be removed and ’00’ appended back onto the answer afterwards.\u00a0 If the second right most digit is a 1, something is wrong because all squares either end in 01 or 00.\u00a0 If second right most digit is a question mark, it must be a 0.\u00a0 This leaves last 2 digits are ’01’ or ‘0?’.<\/p>\n The winning approach was to divide the number into half, if most of the question marks are in the top half, try each possibility for the bottom half, and use that to infer the top half (somehow).\u00a0 Otherwise try each possibility for the top half, and use that to determine the bottom half.<\/p>\n Lets look at the second option first, since it is easiest.\u00a0 If we calculate the square root of the maximum value which matches the specific pattern for the top half, round down and then square – we have our answer (assuming that it matches the pattern.)\u00a0 Only trick is to acquire the square root of a 125bit number.\u00a0 Binary search using BigInteger will do the trick.<\/p>\n This leaves the first option.\u00a0 Lets put aside the possibility of the answer being even.\u00a0 Above it was mentioned that the last 2 digits we actually work with are 01 or 0?, we can use this as justification for ignoring the possibility of the answer being even, because 0? can be broken into 00 or 01 sub cases, 00 causes recursion, 01 does not.\u00a0 (Since only one side of the question mark ever causes recursion, there is no exponential run time problem to worry about.\u00a0 Another important point is to only consider whether the low or high bits have the most question marks after ensuring the last 2 digits are 01, otherwise the algorithm can be easily tricked into running too slow.)<\/p>\n So, since the answer is odd, it ends in 01, but how does this help us?\u00a0 Well if the answer is odd, then the square root is odd, so it either ends in 01 or 11.\u00a0 IE it is 4A+1 or 4A+3.\u00a0 If it is the former than the square is 16A^2+ 8A + 1 = 8A+1 mod 16, if our input is a specific mod 16, we can determine whether A is odd or even, which gives us one more digit of the square root.\u00a0 Similar applies to 4A+3.\u00a0 In both cases, this continues.\u00a0 Given the right half digits of the original number, we can slowly build 2 possibilities for the same number of digits of the square root, which either ends in 01 or 11.\u00a0 Since the number of digits in the square root is no more than half the number of digits in the input and we’ve filled in all question marks in the right hand half we have 2 complete possibilities for the square root.\u00a0 Given these two possibilities we can then check which either actually matches the input.<\/p>\n Thinking about this problem, in hindsight I believe I’ve previously been shown this approach of determining the square root of a number given only its right hand half, but I doubt it would have helped me in the heat of competition, not even if it was the only problem I did.<\/p>\n Final analysis<\/strong> – the small inputs are generally all pretty easy to implement, the first 2 large inputs were in my doable category, this leaves my ‘feasible ideal placement’ between 160th and 90th – which matches with where I get eliminated in my best days.\u00a0 Would have been nice not to screw up round 2 so badly \ud83d\ude42<\/p>\n","protected":false},"excerpt":{"rendered":" A quick look at how people performed in this round shows it to be a very tricky round.\u00a0 No perfect scores this round, but with only 25 people advancing to the finals, unless you solved question 4 large (which was worth 31 points and only had 1 person solve it correctly), you needed everything else … Continue reading GCJ11 R3<\/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-400","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\/400","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=400"}],"version-history":[{"count":0,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts\/400\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=400"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=400"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=400"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}