Looks like there was a big turn out again, all 2000 registration slots used.\u00a0 12 Aussies seems the biggest turn out so far – with 4 advancing. (I think that gives 7 Aussies in to round 2.)<\/p>\n
1000pt obviously wasn’t as easy as last week, but a fast time on the 250pt wasn’t enough to get through again, so the 500pt can’t have been too difficult.<\/p>\n
Q1) Given a sequence length, maximum step size, start and end values, determine the maximum possible sequence element.<\/strong><\/p>\n A1) Appears pretty straight forward, the key thing to realise is that the answer will either be a multiple of the step size above the start value, or the end value (or both).\u00a0 With a maximum sequence length of 1million, you can even try both with brute force without running out of time (so long as for any given reached value, you calculate the number of steps back to the other end using division rather than repeated subtraction).\u00a0 More efficient methods include an inclusive binary search on the range max(start, end) to max(start, end)+(length*maxstep) and checking feasibility by using division to calculate the minimum number of steps required to get there from each and and comparing the sum to the sequence length.\u00a0 There is also probably a closed form formula involving the difference between the start and end values which does the problem in O(1) – but I haven’t bothered to derive it.<\/p>\n In any case you have to remember to handle a maximum step size of 0, which breaks all the division calculations.\u00a0 So treat it as a trivial special case and return start before running any of the above code.<\/p>\n Q2) Given a set of integers which are each formed from the sum of an unknown number of non-negative integer sub-components, determine the smallest number for which it is guaranteed that there is no more than k sub-components which are greater.\u00a0 Number of integers provided will be <50, but the values and k itself may be up to 1 billion.<\/strong><\/p>\n A2)\u00a0 This is a binary search problem – since as you increase the comparison value, the maximum number of sub-components greater than it never increases.\u00a0 The answer will always be in the range 0 to 1 billion and 1, and each binary search step needs only perform a division calculation for each input value.<\/p>\n Specifically if we are considering whether n is a feasible solution, we divide each sum value by n+1 (since they have to score greater), and take the integer division result as the maximum number of sub-components that there could be which are greater. Add all of these answers together, and if it is no more than k then it is a feasible solution.\u00a0 Binary search until you find the minimal feasible solution. (As usual, this binary search is technically implemented to find a value between true and false, so you need one which returns the first value above when equality is not found.)<\/p>\n Q3) Given an NxN grid and assuming uniform random allocation of a pair of cells (not coincident), determine the expectation value for the number of cells of the grid ‘selected’ using a pattern which is centred on each of the randomly allocated cells.\u00a0 The pattern being up to 9 cells relative to the centre of (0,0), (a,b), (b,a), (-a, b), (-b, a), (-a,-b), (-b,-a), (a,-b), (b,-a).\u00a0 If the pattern falls off the edge of the grid, the corresponding member of the pattern is ignored.\u00a0 If any two pattern elements are for the same cell, a given cell can only be selected once. N, a and b are all no more than 1 billion.<\/strong><\/p>\n A3) So yes, this is definitely harder than last week.\u00a0 With such a large value for N, obviously brute force is out of the question.<\/p>\n It isn’t too difficult to calculate the expectation value for a single randomly allocated centre, using N, a and b there is fairly trivial formulas for what area of the grid the centre can be in, compared to the total area to allow each of the 9 points to be valid, then those fractions can be added together, taking care that the areas are up to 10^18 in size, so even if you take advantage that each fraction has the same base you may even overflow a 64bit integer unless it is unsigned when you add them together.\u00a0 Also you need to handle the case where a equals b, and not double count the pattern elements which are then equal.\u00a0 Double this gives a first approximation for the expectation value for 2 randomly selected centres, we just need to subtract off the expectation of coincident pattern elements.\u00a0 And handle the fact that the 2 pieces will never be placed in the same place.<\/p>\n There are 3 cases of coincident pattern elements.\u00a0 The centres are coincident, which has an easily calculated chance of 1 in the area size, and cancels out an entire pattern contribution – the expectation value of which we just calculated before. \u00a0 In fact since centres co-incident is not allowed, we need to cancel out 2 entire pattern contributions.\u00a0 The remaining 2 cases are more complicated – first is centre is coincident on a non-centre element – this cancels out exactly 2 cells (I think), but the probability is related to a subset of the area divided by the area squared (considered for each of the up to 8 different directions).\u00a0 Finally we have to deal with the case of non-coincident centres where the pattern elements match.\u00a0 This appears to have 2 sub-cases, straight and bent.\u00a0 In straight, the line between the centres passes through the overlap cell, and there is exactly 1 cancelled out cell.\u00a0 Again the probability is a subset of the area divided by area squared (this time reduced by 2a, 2b or 2b, 2a – for up to 8 different relative arrangements).\u00a0 In bent, the centres end up a+b apart horizontally\/vertically or a+b, a+b apart diagonally.\u00a0 In the diagonal case, exactly 2 elements are cancelled out, and each of the 4 cases can be handled like straight scenario.\u00a0 The horizontally\/vertically cases are another question though – this time you have to consider up to 3 different scenarios.\u00a0 Because each of the 2 elements to be cancelled out may not actually fit on the NxN grid.\u00a0 But you can calculate an area where the ‘left\/top’ element exists to be cancelled out, and another with the ‘right\/bottom’ element exists to be cancelled out – and use those as individual 1 cancelled out cell cases like the straight scenario.<\/p>\n Once all these adjustments are made, I think a further adjustment of area\/(area-1) needs to be made to compensate for the fact that co-incident centres could never be selected in the first place.<\/p>\n All in all, it isn’t an impossible problem if you’ve done some expectation value calculations before – but it is so fiddly, so many cases to code up, and so many chances to overflow\/lose precision.\u00a0 And correctly handling the no-coincident of centres is a bit tricky.<\/p>\n Looking at some solutions, it appears that it is possible to avoid special casing this so much, by considering each pair of elements from the patterns.\u00a0 For the pair to be co-incident the centres have to be in a certain place relative to each other, which combined with the overlap position gives you the subtraction component as a fraction of area squared.\u00a0 Each of these single subtraction components all combined, should give the same sum as all the subtraction scenarios I mentioned above.<\/p>\n","protected":false},"excerpt":{"rendered":" Looks like there was a big turn out again, all 2000 registration slots used.\u00a0 12 Aussies seems the biggest turn out so far – with 4 advancing. (I think that gives 7 Aussies in to round 2.) 1000pt obviously wasn’t as easy as last week, but a fast time on the 250pt wasn’t enough to … Continue reading TCO13 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-619","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\/619","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=619"}],"version-history":[{"count":0,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts\/619\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=619"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=619"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=619"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}