So, I didn’t compete in this, but plenty of people did.
20595 people qualified with the minimum 25 out of 90 points. 1737 people got 90 out of 90. ~25500 people submitted at least one solution.
Q1) Given 16 distinct numbers arranged in a 4×4 grid, and a selected row, and the numbers after a reshuffle and another selected row that was picked, determine either the one number in common, or return ‘Bad magician’ if there is more than 1, or ‘Bad volunteer’ if there is less than one.
A1) I remember learning this magic trick as a child, although it was in the context of a deck of playing cards rather than 16 numbers. But that seems neither here nor there – the code looks like it should be pretty simple either way. You don’t even have to parse the 4×4 grids into 2 dimensional arrays, since the input gives you the selected row before the grid, so you can just only read in the one row which matters. Then given the 2 4 element arrays, you can calculate the result using a pretty straight forward nested loop – or you can be lazy and just add the arrays to standard Set data types and ask it for the intersection.
Q2) If you have a base earn rate of 2 cookies per second, and buying a cookie farm costs C cookies and increases your earn rate by F cookies per second, and have a target of X cookies, what is the shortest possible time to get to your target. Earn rates and buy times are not based on integer time, can be any real number.
A2) So my first instinct looking at this question was pretty poor – I saw finding a minimum on a function which seems to fairly obviously only have a single turning point in the range of positive numbers of cookie farms bought. This naturally made me think ternary search. Which would work, but is completely pointless – because calculating the time to win for a large number of farms does almost all the same work as calculating the time to win for every smaller number of farms, so performing a ternary search is just a waste. Also the upper bound of the ternary search needs to be defined, which is not trivially obvious.
So the simple solution is to have a running total of how long it takes to build n farms, and for each one, compute how much additional time to get to the target. Once the total starts getting worse, just return the best found. The running time of this is O(B) B is the number of farms which need to be built.
The size of B is an interesting question itself. We can determine when the turning point is going to be by an equilibrium equation. X/(BF+2) = C/(BF + 2) + X/(BF+ 2 + F) For B smaller than this, it is faster to build another one, and for B greater, it is slower (for constraints of X/C/F all being positive at least…)
Solving for B:
X (BF + 2 + F - BF - 2)/(BF + 2 + F) = C BF + 2 + F = XF/C B = X/C - 1 - 2/F
Interesting here is how insignificant F is. This is because a high F lets you build everything quicker, not just the final target, so if the starting rate had of been F rather than 2, it would have been completely irrelevant except as a scaling factor of the total time.
Since C is >= 1 in the problem statement, O(B) is practically O(X).
However, now that we have exact number of farms to build, interest turns to whether the solution can be done in O(1). This becomes a problem of evaluating the sum of 1/(ax+b) for x = 0 to x = B. This seemed vaguely related to the Harmonic sequence sum (a=1, b=1), which I provide a reasonably fast implementation in TMD.Algo, so I suspected it was possible. Wolfram alpha told me that it was (digamma(b/a + B + 1) – digamma(b/a))/a. So if you happen to be programming in a language which provides digamma evaluation, you are set. If not, you will need to write it yourself. Wolfram alpha provides formulas for small and large X, the large X one bearing a striking resemblance to the Harmonic sequence sum I implemented for TMD.Algo. The trick here is that digamma(b/a) is digamma(2/F) which can easily be in the range of 1 to 2 which is probably its most tricky area to approximate. This is especially difficult because the digamma passes through 0 in this vicinity, so the recurrence relation digamma(x+1) = 1/x + digamma(x) is going to end up subtracting very similar numbers, resulting in significant relative error. But since that is only near 0, and if small B is handled separately the digamma(b/a + B + 1) term should be dominant enough to swamp the error. So yes, O(1) is plausible, if you are happy considering digamma as O(1) when its implementation will probably involve at least 5th order approximation functions to get sufficient places to fill a double precision float.
Q3) Given an RxC board and M mines, determine if they can be placed such there exists a location where a single click reveals all non-mine squares, using classic minesweeper rules where 0’s auto expand in a cascading fashion.
A3) This problem by far had the lowest success rates. Which is interesting because the a maximum of 5×5 it is actually plausible to brute force the small input. Try each of the 2^25 patterns, throw away the ones which don’t have M mines (to avoid implementing a combination generator), then for each of the rest, calculate the numbers and ensure all numbers are adjacent a 0 and all 0’s are connected (flood fill count vs total 0 count for instance), return the first one you find, with any one of the O’s marked as the click location. This is worst case >125million instructions, which is quite a few given the 200 test cases, but given the memory locality it should be plausible for any language without excessive overhead.
More interesting is doing the problem without brute force, as is needed for the large input. This isn’t hugely difficult, but the number of corner cases is significant. It is convenient to write a transpose function so you only have to deal with the cases of R >= C. (And remember to transpose back if needed when you are done.)
From there there are several cases which need special handling.
- M = RC – 1. Here the solution is, fill in everything and overwrite one of the mines with the click location. Handling this scenario first is useful.
- C = 1. Fill all the rows until you reach M, and then put click location in the last row (or anywhere not next to the mines).
- C = 2. Here M must be even and RC-M must be at least 4. If those are true, then simply fill every row until you have M mines, and place click location in the last row (or again anywhere not next to the mines).
Which leaves the general case C >= 3. C = 3 itself has some specialness but it can be treated under a single code path with the rest easily enough as far as I can tell. For convenience, define L as RC-M – the left overs. If leftovers (L) is >= 3C it is almost as simple as just filling from the top, left to right. The one case which needs handling is L % C = 1, in this case the one left over on the right is not adjacent to a 0. This can be solved by moving the mine next to it, down one row and all the way to the left. This newly placed mine is fine so long as it is on the 3rd last row or earlier, hence the condition of >= 3C. In fact we can extend this condition to L >= 2C + 2, since the first problematic scenario is L = 2C + 1.
In fact, L=2C is trivial, so our first step is to fill everything except the last 2 rows. If L = 2C+ 1, we remove 3 from the 3rd last row, and put 1 in each of the first column of the last 2 rows. This pattern of switching 3 for 2 is one of the basic steps we can use from here on. However, this only makes sense if C >= 4 which brings us to how this code path can be made to work with C = 3.
So, what values of L are clearly impossible? L=1 is fine, we covered it first up. L=2 is bad, there is no way that only 2 spots can exist with either of them being a 0 (excluding C = 1 as all of this discussion here will). L=3, same. L=4, this is possible in a corner so long as C >= 2. L=5, again no way. L=6 works with an edge which allows the 3×2 empty rectangle. L=7, again impossible. L=8 has two options 4×2 on an edge or a 3×3 in a corner with the opposite corner taken out of it. So why is this important? Because if C = 3, L = 2C + 1 = 7, which is a known impossibility, so we can test for known impossible values of L before starting the general case logic.
So, this leaves handling of L < 2C and L != 2, 3, 5 or 7. Starting from having filled in all but the last 2 rows, the first operation is remove 3 from row 3 and add 2 each to the last 2 rows. This gives 2C – 1, although it only is in a valid state if C is at least 5, but again C = 3 this is 5 and C = 4 this is 7, both of which have been excluded. Now put the 3 back in the 3rd row, and remove the right most one for each of the last 2 rows. This moves us to 2C – 2, and this time it is valid for C >= 2, which is all those under consideration. Repeating the first step gets to 2C – 3, but this time only valid for C is at least 6, but again smaller C values are excluded by the L being 3 or 5 or 7. These steps can continue to be alternated, decreasing L by 1 until the desired target is reached. In every case the click target is the bottom right corner.
Q4) There are 2N distinct numbers selected from 0-1 exclusive, half the numbers are given to player 1 and half to player 2. A turn consists of player 1 announcing a number, player 2 selecting a number, and player 1 winning a point if their number is actually greater than player 2’s. Player 1 is it a disadvantage obviously, so they are considering cheating. They would cheat by first looking at all of player 2’s numbers at the start of each game, and then potentially lying when announcing the number, knowing that in this specific game the number comparison is confidential, only the result is public, not the specific values that went in, and that player 2 will be playing to maximise their score.
A4) This questions problem statement is a bit of a mouthful, you would be better to just go and read the original…
So this problem is interesting, in that what I think is the hardest part of this problem is also the easiest, and that is ‘what is the ideal strategy’ for the non-cheating version. Its the hardest in that I can’t come up with a viable proof in the time I allotted to considering it, but it is seemingly pretty easy to guess. So first off player 2’s strategy is pretty obvious. If they can win, they will play the smallest number which wins, if they can’t win, they will play their smallest number remaining. Player 1’s strategy, I don’t know, does it even matter? Just playing them in sorted order seems reasonable.
Speaking of sorted order, sorting all the numbers for each player is a good starting point. For calculating the non cheating version consider each of player 1’s numbers in order, and walk up player 2’s as needed. Once you find a player 2 value greater than player 1, player 1 loses that point and increment both indexes. Once you run out of player 2 values, player 1 wins all remaining plays.
For the cheating version first we need to identify how you can cheat. There are 2 ways, one which is more obvious to me than the other. The first is that you can increase the number you announce until it is just smaller than the opponents greatest number, to force them to beat you using their largest value, rather than potentially a smaller value. The second is that if you can beat their smallest value you can announce a value of 1 minus epsilon (since the values are all 0 to 1 exclusive, you can always announce a value higher than their actual highest value) and your opponent then plays their smallest value, which you beat, just as you stated you would. They are both important, but this second one has the most obvious consequences.
To calculate the cheating win, take the sorted lists and compare the first values. If player 1 is greater than player 2, player 1 wins this round and both indexes advance (by using cheat method 2). Otherwise player 2 wins this round, but by using cheat method 1, player 2’s largest value is the one which will be discarded, so only player 1’s index advances. Repeat until all player 1 numbers have been considered.