So, out of 500 qualifiers, only 311 positive scores. And no perfect scores.
Cut-off to advance to the world finals was having solved the first and last problems. But given only 3 people fully solved the last problem, a safer grouping was having solved first, 3rd and the small input of the last.
Interestingly solving Q1 and small inputs of the rest got between 29th and 54th, which was a reasonably achievable score if you gave up and didn’t get bogged down on any of the tougher large inputs.
Q1) In a rigged game of roulette where the ball always lands on one of the values with minimum payout, given how everyone else has already played, determine your maximum profit you can make with your money.
A1) So for this question it seems likely that we can enumerate the scenarios of maximum winnings. The small input certainly is trivial, with a maximum budget of 1000, you can use the strategy that placing money on an outcome which is not currently one of the lowest payout outcomes, is a wasted bet. Furthermore when there are multiple equal, you choose the one which has the least of your money on it. Then just apply that strategy by placing each bet of size 1, one at a time, and find which is best. The large input however we need to enumerate the ideal scenarios more efficiently as you could have up to 10^12 to spend.
So, rather than going 1 by 1, we need to skip ahead by chunks at a time. Specifically, any scenario which is profitable, will be more so, if we can raise all the minimum payout outcomes by 1, without increasing the number of minimum payout scenarios. So we can seed with a few scenarios, and push them as high as we can, without reaching equality with another players bet or running out of budget. Each time we reach another players bet, we start again assuming having brought everything up equal to that. I think that the scenarios to seed with are the 37 equal or above equality with a bet (or equal or above 0 if there are less than 37 player bets). Running time is thus 37*37 divisions/minimum/maximum calculations – easily running in time.
I think this would work, but I see solutions instead using binary search to find the best scenario rather than division. It seems that there is a more aggressive strategy which always spends as much of the budget as possible for each of 37 scenarios, rather than 37*37 scenarios spending up to the next price threshold.
Q2) Given a set of vertices construct a non-self intersecting polygon which uses all the vertices with at least half the area of the convex hull.
A2) Just like Round 2, another problem where it doesn’t state maximum area, just at least half, and any satisfying result can be returned. Being a computational geometry question, it isn’t my favourite. So I think the approach would be to start by calculating the convex hull. Then it becomes a question of where to insert the contained points into the order described by the convex hull. Small input however is limited to 10 vertices, so it can be brute forced, just consider every polygon, build them up to rule out self-intersection, then calculate the area that remains. Large input has 1000 vertices, and I want to say a greedy approach will work, where for each vertex not in the current border you calculate its minimum cut-out location to add it to the list, and perform that cut-out. Problem is doing this in better than O(N^3) time seems like it would require some fancy spatial data structures.
Looking at the answers there is a far simpler approach which avoids the whole question of maximum and just dives straight at the ‘at least half’ criterion instead. It is not at all obvious though… If you calculate the convex hull, and consider connecting all the internal points in a left-to-right sequence to the outside of the hull (choosing an orientation to ensure that internal points can be strictly ordered left-to-right, you create 2 areas (both of which are valid non-self-intersecting polygons), which together add to give the area of the convex hull. Hence one of them must be at least half. So if you take half the convex hull, and all the other points ordered left-to-right, that can only be larger than the previous area, so one of those 2 must be more than half the area. Since all coordinates are integer, you can select a very slight fractional angle, which will ensure they all have a distinct left-to-right order. Calculate the convex-hull, and the left/right most coordinates of the convex hull under this order then serve as the split points to divide the hull into 2 parts, try both versions, calculate the maximum area. Since the polygons are known to be non-self intersecting, the running cost is O(N log N) for sorting on a slant, and then O(N) to implement convex hull on sorted data and O(N) to calculate the area, so 1000 is easy.
Q3) Given a set of one direction edges on a graph and an ordered subset of them which represents a path from vertex 1 to vertex 2, determine the first edge of that subset which is definitely not on the shortest path, if any, given a range of possible costs for each edge. When considering each edge for whether it can be on the shortest path, the shortest path must include all previous edges.
A3) This is a very strange question, on my first reading I didn’t understand it very well and thought it was about ensuring each edge specified was on a shortest path, not only on a shortest path prefixed by a given set of edges. I think the small input can be brute forced by trying each combination given by choosing one of the extreme values for each edge and calculating the shortest path for each of these 2^20 scenarios. Whichever one goes furthest down the specified path will define the answer. Large input certainly needs a different approach. I am thinking that we start with every edge at minimum value, then apply all source shortest path, then for each edge on the route we take the specified previous edges, and from the end of the edge to vertex 2 we use the previously calculated shortest path to the destination, then every edge not on that list has its cost set to maximum, and we determine if the shortest path goes through our selected edge. Running time should be okay, O(N^2 log N) or so, but I am not certain it is actually correct.
Looking at the solution I am still not entirely sure, but I am pretty sure there are corner cases it breaks where the shortest path back from end of prefix allows for a short-cut that skips the selected prefix edges but there exists another ‘short path’ back which doesn’t cause that problem. The solution does a simultaneous 2 starting point shortest path by priority first search. One starting point is vertex 1 with initial cost 0, the other is the end of the current prefix being considered, with a cost implied by the minimum for each edge in that prefix (minus a half to give it priority since equally fast is still on the shortest path). Each of the prefix edges are forced to have weight minimal. If we are at a vertex which has a fractional best cost, we use minimal weight for outgoing edges, because our prefix shortest path got there first, so its always good. Otherwise we use maximal weight for outgoing edges, since the raw search got there first, which is bad. If the destination vertex ends up being fractional, shortest path has succeeded with the prefix.
Q4) Given a starting list of boolean values, determine the average sum of the number of consecutive true values starting from randomly selected locations until the first false to the right (wrapping back to the beginning if needed), if each found false location becomes true, and the process repeats until every value is true.
A4) Again this is a problem where the small input is quite easily achieved. With only 20 entries in the list, the problem can easily be recursively defined with a cache over the possible states in the list. Each state has 20 random approaches which have to be averaged to give the final value of that state.
Large input, I had no clue, so I went straight to the solutions. The solution is an O(N^3) approach by calculating the probability of filling a consecutive subsequence (including wrapping) of values with a specific member being last, and the expectation value of the same. Each of these calculations can be expressed in terms the items before the specific last entry to fill, and the ones after it and using some fancy combinatorics for the probability calculation. I won’t go into it here, you can always read the official contest analysis for more details.