Over 12000 qualifiers could have turned up for R1A, but given time zones that was always unlikely.\u00a0 5032 positive scores, over 300 perfect scores, and the advancing cut off was a fast time on the first 2 problems completely solved.\u00a0 If I had of been doing this round I think I would have advanced, but maybe not having completed the easiest question – as I think the wording is incomplete, leaving the question open to being interpreted as a much harder question.<\/p>\n
Q1) Given a list of observations of the number of items on a plate at 10 second intervals and knowledge that there is someone who can add items at any time, and another person who removes them either whenever, or at a constant rate if the plate is not empty (but not both).\u00a0 What is the minimum number of items the second person removes under each mode of item removal.\u00a0 Presume that constant rate item removal is a continuum, if removing 1 per second, there is half of the item still on the plate at 0.5 seconds.<\/strong><\/p>\n A1) So I’ve changed the wording for this question to be what was actually marked correct, there is no statement regarding whether items are removed from the plate discretely or gradually across the period of constant rate of removal.\u00a0 Removing discretely is a much different question, which is quite a bit harder.\u00a0 (And given the persons ability to remove arbitrary numbers of items at any point in time in the first mode, my mind gravitated towards discrete.)<\/p>\n To see where this is different consider the example 1 1 1 0.\u00a0 Under the continuum removal case the number of items removed per 10 second period must be an integer, as all observations are integer.\u00a0 Hence 1 item per 10 seconds is the minimum removal rate, and 3 items are removed.\u00a0 But if removing is a discrete event, you can choose a removal rate of 1 every 25 seconds, in which case only 1 item is removed. (Assuming that the discrete removals happen at the end of each removal period rather than the start – the start you have to remove one immediately, so the total is 2.)<\/p>\n Given the continuum restriction this problem is trivial.\u00a0 In the first mode of removal you remove items only if the count goes down from observation to observation, so just sum the neighbour differences where they go down.\u00a0 In the second mode the minimum number removed is described by the minimum rate – and the minimum rate is given by the largest drop.\u00a0 Once largest drop is found the answer becomes simply a sum of all the values (excluding the last) except if the value is above the largest drop, then you just add the size of the largest drop instead.<\/p>\n The non-continuum problem is much harder as you have a search space which is not limited to integer values per 10 seconds, and its not clear that it is even a single transition from too slow to fast enough which would allow it to be binary searched.<\/p>\n Q2) A list of barbers each have a well defined customer processing rate.\u00a0 When will the nth customer be served?\u00a0 Assume that if multiple barbers are free, they are filled earliest in the list first.<\/strong><\/p>\n A2) Nice problem.\u00a0 The size of N may be huge meaning simulation is out of the question, even for the small input.\u00a0 For the small input it might be possible to find a period of repetition of patterns of when barbers become available and skip ahead as appropriate, but the large input clearly rules that approach out as well.<\/p>\n While a simulation is not feasible, it is possible given a time T to determine quickly how many people each barber has started serving by the end of that minute, its just (T \/ barbers_time_to_cut) + 1.\u00a0 The same formula given T – 1 gives how many people had started being served before this time.\u00a0 This gives a range, which if it contains N, you’ve found the minute N starts being served and all that remains is to determine which barbers changed state between T -1 and T (which comes from the same formula), and choose between them based on how far N is from the start of the range.\u00a0 To find which T-1 to T contains N, binary search on T.\u00a0 If N is before the value at T – 1 T needs to be lower, if its greater than the value at T it T needs to be higher, otherwise you’ve found the value.<\/p>\n Q3) Determine, for each vertex, how many other vertexes need to be removed, for the specific vertex to be on the convex hull.\u00a0 Consider co-linear points to form a convex hull which touches all of them.\u00a0 All input vertexes will be distinct integer coordinates.<\/strong><\/p>\n A3) The small input only has 15, so a brute force trial of every subset using the standard O(N log N) convex hull algorithm (like in TMD.Algo) – would work.\u00a0 However the one in TMD.Algo throws exceptions if you give it a subset smaller than 3 or perfectly co-linear points, so those cases have to be handled separately.\u00a0 For each node on the convex hull from each subset, it gets a new potential minimum based on the size of the subset vs the original input size.<\/p>\n The large input is much harder – 3000 obviously can’t be done with an exponential cost algorithm.\u00a0 However with a fast computer and lots and lots of cores… an O(N^3) approach might work, if it has a sufficiently low constant.\u00a0 Consider each pair of nodes gives N(N+1)\/2 options.\u00a0 These 2 nodes define a line of the form ay + bx + c = 0 (or a dx,dy vector).\u00a0 Now every other point can be substituted into the formula (or cross product with dx2,dy2 vector formed by subtracting the point from original point\u00a0 used to create the dx,dy vector).\u00a0 Count the number of positive, negative and 0 outcomes (from either case).\u00a0 Since we are considering every possible point pair, then obviously one of those pairs will be an edge on the ideal convex hull, for one of those points.\u00a0 For the edge to be part of the convex hull, either all the positive, or all the negative points must be removed.\u00a0 Thus the size of the smaller of the two options is a potential minima for both of the original two points.\u00a0 Calculating the line formula is 2 products and 2 additions, then 2 conditional increments to classify.\u00a0 Giving a constant for N^3 of 1 multiply, 1 add and 1 conditional increment, each of which is potentially only a clock cycle on a modern cpu.\u00a0 The cross product approach is 3 subtractions instead of 2 additions, but should also be reasonable.<\/p>\n But if your programming language doesn’t optimize well, or you don’t have a bunch of cores available there is an O(N^2 log N) approach, which can be considered slightly inspired by the standard fast convex hull algorithm.<\/p>\n For each point sort all other points by angle relative to that point.\u00a0 This can be done by first dividing the points into left\/right and using a standard sort algorithm on each side using cross product of each point’s vector relative to the starting point as the comparator function.\u00a0 Once the points are sorted O(N log N) the minimum removal of the original point can be calculated in O(N) time.\u00a0 For each sorted point, it defines an edge with the starting point, and the rest of the sorted points are either left\/right or equal of that edge.\u00a0 The counts of these left\/right\/equal can be efficiently calculated in general, by first doing a linear scan of the sorted list for the first candidate edge, then to do the rest of the candidate edges you just have to advance the the indexes in the sorted list that mark the interesting areas, left, right, equal but on same side of starting point as candidate point, equal but on opposite side of starting point as candidate point.\u00a0 In the process of going through all candidate edges each marked index will never need to backtrack more than one index per step, so they all have a maximum of O(N) operations each to maintain, giving a total of O(N) operations. (An alternative to all this state maintenance is to for each candidate edge binary search to find each of the 4 transition points.\u00a0 Its O(log N) rather than O(1) per candidate edge, but given the original sort is O(N log N), this is not significant.)<\/p>\n The above algorithm is simply repeated for every input point, giving a total of O(N^2 log N)<\/p>\n","protected":false},"excerpt":{"rendered":" Over 12000 qualifiers could have turned up for R1A, but given time zones that was always unlikely.\u00a0 5032 positive scores, over 300 perfect scores, and the advancing cut off was a fast time on the first 2 problems completely solved.\u00a0 If I had of been doing this round I think I would have advanced, but … Continue reading GCJ15 R1A<\/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-778","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\/778","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=778"}],"version-history":[{"count":0,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts\/778\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=778"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=778"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=778"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}