So, having been knocked out in Round 2, I didn’t have to wake up at 2am to do this round, which is good because I’m not sure I would have gotten any points anyway… As usual, there were 3 questions, but no one solved question 3 and only 5 people successfully solved question 2, meaning you could advance to the finals with just by solving Q1 quickly and a successful challenge or 2.
Q1) Given a set of 32bit numbers, determine whether each of a second set of 32bit numbers is in the resultant of K rounds of expanding the the set using the bitwise and operation. Specifically, every pair in the set is anded and the result is added to the new set, the input and output sets can contain duplicates.
A1) So, my initial thoughts were around that the and operation is rather limiting, so the total count of numbers will never get very large, so you could just simulate the problem, collecting duplicate outputs into counts. But that would be mistaken. using an appropriate set of initial numbers you can generate a very large set of outputs even once you apply distinct, and as a result simulation will take too long.
So, K=1 is easy, you just consider every pair. K=2 there are 2 cases, the 2 input numbers are either from distinct original pairs (N choose 4) or they are from overlapping original pairs (N choose 3). K=3 there are more scenarios. 8 distinct original numbers anded together is the maximum, you can obviously do scenarios for 7, 6, 5, 4. What is interesting is that you can still do 3. In the K=2 case, each scenario of N choose 3 can be created 3 different ways. ((1,2) (2,3)) ((1,3) (2,3)) ((1,2) (1,3)). Since all duplicates are kept this means that these would be anded together pairwise to create another 3 new copies of each case of (N choose 3). From there on it follows that every possible combination involving at least 3 and at most 2^K distinct original numbers will be in the output. And since the original input is at most 16 numbers, we can consider every subset easily enough. We just need to remember to special case K=1, as it is the only case where you can choose pairs.
Q2) Given a NxN array with 3 specified positions on the edge being important, determine the minimum number of filled in positions which need to be added (some may already be filled in) such that there is no path of connection between any pair of the 3 original specified points (path consists of horizontal and vertical only, no diagonals). If there is no way to do this is less than 100 positions, return 100.
A2) The ‘100’ limit is a misdirection, other than when any 2 of the specified positions are adjacent (and hence cannot be blocked) the maximum answer is 6, 3 for each of 2 of the original positions required to surround them against an edge – the 3rd position doesn’t matter of course once 2 of them are blocked in. However, considering the cases of placing 1-5 options on a 20×20 grid, and for each case performing a connection check is 400^6 operations in the worst case, which is far too many to complete in the few second time limit. It is quite feasible to check each single location, or even each pair, but beyond that is pushing your luck.
Looking at the 5 successful solutions they all seem to use the same kind of approach. The idea is to think about the minimum cost to create a wall between 2 points. Then the final result is either 2 walls which each block in 1 edge location, or 3 walls which meet in the middle. The minimum cost to create a wall between 2 points is a graph problem where a block already filled in creates 0 cost edges for the paths it blocks, a block not filled in creates 1 cost edges instead. The net result is you can run all pairs shortest path. Once you have the all pairs shortest path, you can then consider each centre location, and for each of those consider the shortest paths to create three walls from there to any location on the edge between each pair of the 3 selected edge locations. Finally you can choose each pair of edge positions and choose the cheapest 2 walls which go from one side of a selected location to the other. (The 2 cheapest selected must obviously be for different selected locations.) Choose the best result out of all of these scenarios and, presto you have the answer. In the worst case of a large empty map with 3 spread out selected edge locations the 2 walls will always win out, but on a map which is already filled in much more significantly, the 3 walls meeting is more likely.
Q3) There is a set of m positive integers , n of which are between 1 and t inclusive, and the sum of all m is less than or equal to s. Determine how many sets satisfy these requirements (returning count modulus large prime). Constraints, n is at most 100 less than m, t is at most 10^5, m is at most 10^9 and s is at most 10^18 and is at least n*t.
A3) So I don’t have any answers to fall back on here, what I find most interesting is the constraints, they are rather detailed – s being at least n*t for instance is suspicious. Looking at this problem I see possible approaches with running times of at least O(s) which is obviously out of the question. The combinatorics certainly seems beyond me at the moment.