Seems low turn out is normal now – 1214 registered out of a possible 1950. 6 Australians braving the 2am start.
Tough round again, top 50 was determined by having solved the 250 and 500pt, with a couple of 250pt only thrown in through large challenge success rates. Despite throwing away some points with an obviously wrong challenge of a correct solution and getting off to a slow start with multiple silly bugs in my 250pt code, I managed to get top 400 placing and my TC rating went back over 1700 again. But still not in the running to get a t-shirt.
Q1) Given 3 infinite arithmetic series which you can freely slide to different integer offsets determine the maximum minimum gap between any 2 numbers amongst the 3 series. The 3 infinite series are defined by their spacings a,b,c which are all between 1 and 2000 inclusive.
A1) Initial guess was GCD(a,b,c)/3 rounded down – but that doesn’t work for cases like 20,30,40 (which was one of the given test cases helpfully).
As it turns out, the answer is either min(GCD(a,b)/2, GCD(b,c)/2, GCD(a,c)/2) or GCD(a,b,c)/3 (both cases, rounding down) – the determining factor being whether all 3 pairwise gcds are equal or not. Equal results in the second case, not equal results in the first case.
But since the problem states that the maximum range is 1 to 2000, you can find the solution with a bit less smarts and a bit more brute force. (As I did.) Firstly you observe that offset of one of the arrays doesn’t matter, it can be fixed at offset 0 – since it is an infinite scenario, the origin is meaningless. Secondly, it is obvious that an offset greater than the sequences spacing adds no value, since again the sequences are infinite.
This leaves 4 million scenarios to evaluate. So long as we can do so quickly, we are done. So for a pair of infinite sequences (with spacings s1 and s2) with a relative offset of i – what is the closest approach? Turns out this isn’t too difficult to work out – it is min (i % gcd(s1, s2), gcd – (i % gcd(s1, s2)). So calculate this for all 3 pairs and take the minimum then return maximum of those across all scenarios. My implementation (mostly pointlessly) went a bit faster than this by skipping the inner loop if the outer loop gave a pair of sequences which was worse than the current best. Also the outer loop can be simplified to between 0 and gcd(a,b) rather than 0 and b. However a mistake I made at first was trying to make the same range reduction for the inner loop – which isn’t valid as it doesn’t fully explore the combinations of modulus.
Q2) Given a directed graph of up to 50 vertices, where edges can come in 3 different flavours (and any given pair of vertexes can therefore have up to 3 edges in each direction between them) a game is played. This game involves one person choosing a starting location and announcing the flavour of each transition made to move to a new location. The second person then tries to state with certainty where the first person currently is. If the first person reaches a dead-end, they must declare as such, and the game is over (even if there are multiple dead-ends). Game is scored by the number of moves the first player makes before the game is over. Given the graph, and assuming optimal play by player 1, return how long the game is – or -1 if the game is infinitely long.
A2) So it isn’t too hard to write a solution to this problem (which I did) – it is however much more difficult to write one which isn’t too slow in some corner cases. I actually tried to construct a large test case to break my solution, and failed – but the system tester did not. My solution approached the problem from player 2’s perspective. At the start the ‘possible space’ is the set of all locations. Each called out transition maps the possible space to a new possible space. If that space consists of a single location – the game is over. If that space is empty, the optimally playing player could not have called that transition out. A simple dictionary approach lets you store how many moves remain for a given state. When you first see a state you store -1 – thus if you see a state on your current path you can immediately return -1, but if not you can replace that -1 with the actual best number of turns possible. Running cost of this is worst case O(n^2*2^n) – which for n=50 is way too slow. (Using bitwise operations like I did its O(n*2^n) 64bit integer operations, but that is only valid till n=64, and its not a significant improvement anyway.) But constructing this worst case is non-trivial – so I gave it a shot (and failed).
It appear the correct approach is to consider that for player 2 it doesn’t matter whether there are 2 or 22 possible locations, anything greater than one rules out the game ending. So if you take any pair of locations, and consider the possible ways to map that pair to another pair and so on and so on – if you ever find the same pair again, you’ve created a loop and the game can continue forever, but if your search always terminates (no mapping for pair, or only mapping is to them both going to the same node) it isn’t too far of a stretch to see that the best number of turns you find in this search (starting from each possible starting pair) is the same as the best number of turns from the more extensive search.
Q3) Given an initially empty rectangle of size x, y – and the ability to perform 2 operations where you select a sub-rectangle sx, sy and fill 0 or more of the squares in the sub-rectangle – determine how many possible different final states there (modulo large prime) x and y bounded to at most 40.
A3) Only 2 solvers for this problem. Answers look like serious combinatorics – adding and subtracting numerous cases. Seems to break it down into rectangle size where changes are made. For each rectangle size where changes are made count how many possibilities, and multiply that by number of possible offset locations of that rectangle in the larger rectangle. That somehow makes the counting of possibilities a bit easier. Seems that for each of these rectangles you consider the case where the 2 sub-rectangles are fixed to opposite corners – and then subtract off the overlap between the 2 cases of opposite corner. Then there is some magic to do with the edges of the rectangles which must be to avoid some kind of double-counting – its all way too complicated for me at 5am in the morning…