Over 12000 qualifiers could have turned up for R1A, but given time zones that was always unlikely. 5032 positive scores, over 300 perfect scores, and the advancing cut off was a fast time on the first 2 problems completely solved. 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.
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). What is the minimum number of items the second person removes under each mode of item removal. 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.
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. Removing discretely is a much different question, which is quite a bit harder. (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.)
To see where this is different consider the example 1 1 1 0. Under the continuum removal case the number of items removed per 10 second period must be an integer, as all observations are integer. Hence 1 item per 10 seconds is the minimum removal rate, and 3 items are removed. 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.)
Given the continuum restriction this problem is trivial. 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. In the second mode the minimum number removed is described by the minimum rate – and the minimum rate is given by the largest drop. 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.
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.
Q2) A list of barbers each have a well defined customer processing rate. When will the nth customer be served? Assume that if multiple barbers are free, they are filled earliest in the list first.
A2) Nice problem. The size of N may be huge meaning simulation is out of the question, even for the small input. 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.
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. The same formula given T – 1 gives how many people had started being served before this time. 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. To find which T-1 to T contains N, binary search on T. 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.
Q3) Determine, for each vertex, how many other vertexes need to be removed, for the specific vertex to be on the convex hull. Consider co-linear points to form a convex hull which touches all of them. All input vertexes will be distinct integer coordinates.
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. 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. 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.
The large input is much harder – 3000 obviously can’t be done with an exponential cost algorithm. 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. Consider each pair of nodes gives N(N+1)/2 options. These 2 nodes define a line of the form ay + bx + c = 0 (or a dx,dy vector). 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 used to create the dx,dy vector). Count the number of positive, negative and 0 outcomes (from either case). 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. For the edge to be part of the convex hull, either all the positive, or all the negative points must be removed. Thus the size of the smaller of the two options is a potential minima for both of the original two points. Calculating the line formula is 2 products and 2 additions, then 2 conditional increments to classify. 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. The cross product approach is 3 subtractions instead of 2 additions, but should also be reasonable.
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.
For each point sort all other points by angle relative to that point. 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. Once the points are sorted O(N log N) the minimum removal of the original point can be calculated in O(N) time. 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. 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. 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. 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.)
The above algorithm is simply repeated for every input point, giving a total of O(N^2 log N)