This was a round of relatively tough problems. In the end solving the first and the small of the second was sufficient to advance, so long as your time penalty wasn’t excessive.
Q1) Given the increment and reverse digit order operations, what is the minimum number of steps to get from 1 to x?
A1) So the small input can be brute forced using a breadth first search, but why this is true is one of the key points towards the large input which cannot be brute-forced.
The danger with any breadth first search is that the search space might explode. But in this case a quick inspection finds that a search to find x never considers values greater than 10^(ceil(log10(x))). Of the operations available, only the increment can increase the number of digits. Therefore in order to get to a value in the next tier, you have to first get to 9999… It is therefore interesting to see how many steps it takes to get to each tier. Inspecting the bfs it takes 1 to get to 1, 9 more to get to 10, 19 more to get to 100, 109 to get to 1000, 199 more to get to 10000. This pattern leads to the insight of what the minimum number of steps involved is to get from one tier to the next. First increment until the last half of the digits are all 9, then reverse, then increment until next tier is reached.
Having made this observation it is natural to jump to a greedy approach, calculate number of steps for each tier, then on the last tier increment until the last half of the digits match the start of the desired number, reverse and then increment until the desired number is reached. There is one corner case however. If the target number ends in zeros, reversing leaves you with a number ending in 1, and you can’t go backwards. The natural fix here is to aim at the first half of the digits – 1, reversed, as the last half of the digits. So for 9900 the first step is to get to 1089.
This just leaves proof the approach is right. The greedy algorithm is pretty obviously the minimum number of steps which stays within a tier, but we need to rule out going up a tier, reversing a number ending in zero. This falls out from the number of steps the greedy algorithm takes to get to a number worst case within a tier. For anything that doesn’t end in half zeros, the number of steps is obviously less than the number of steps to get to the next tier, since each sub part of the algorithm has less steps. This leaves 90, 900 and 990 as a potential worst case scenarios. First takes 18 steps (less than 19) from 10. The second takes 108 steps (compared to 109) from 100. Finally the last takes 99 steps (compared to 109) from 100. So going up and then down is never going to be cheaper.
Q2) Given RxC grid and N filled in squares, what is the minimum number of shared edges.
A2) The small input is only 15, so brute force simulation is nice and easy. Conveniently 15 is also 3×5, which ensures good coverage of the main corner case.
The large input seems a natural ‘greedy’ approach scenario. Checker-board coverage, then fill in any empty corner locations (for 2 edges each) then any empty edge locations (for 3 edges each), then the centre (for 4 edges each). But this fails. Inspecting brute-force vs greedy the differing scenario is in 3×5.
Greedy for N=12 gives:
xxxxx xx.xx x.x.x
Brute force on the other hand gives:
xxxxx x.x.x xx.xx
Greedy scores 12, brute force scores 11.
At this point I have to say I was stumped, I started to consider DP style approaches, but they were all very very computationally expensive, the large input was not plausible. So I looked at one of the submitted solutions. And now staring at the cases I presented above it seems obvious, but maybe it would have been more obvious if I had of presented N=11.
Greedy vs Brute-force for N=11.
xxxxx xx.xx xx.x. x.x.x x.x.x xx.xx
For an odd by odd grid, there are 2 ways to tile checker-board style and the maximal one is not always the best option as a starting point for the greedy algorithm. A single extra spot has a cost of 3 in maximal grid, but in the inverted grid the first 4 extra spots cost 2. The inverted grid fills one less spot, so at 2 spots at 2 each vs cost of 3 is a loss, but 3 spots at 2 each vs 2 cost of 3 is a draw, and 4 spots of 2 each vs 3 of 3 is a win for the inverted grid. Ultimately the inverted grid starts losing again because it has more interior points which cost 4, but while its edges are still being filled in, it gains and then holds the advantage.
Ultimately 3×5 is not required to force the inverted grid, 3×3 has a win for the inverted grid at N=8. But 3×5 does cover the full progression of cases better.
Q3) Given a bunch of people walking endlessly at constant speeds around a circular track, with varying starting points, determine the minimum number of times to meet up with anyone else in order for you to do one loop of the track, if you can do any speed you want whenever you want.
A3) So I think that your super powers with regards to speed means the problem can be turned into one of arrival time. If you arrive at the destination at time x, you have to have gone past anyone who hasn’t yet completed a lap (for 1 meeting each) and have one additional meeting for every time you have been ‘lapped’ by someone who has completed 2 or more laps. Trivially infinite speed with an arrival time of 0 gives you an upper bound which is equal to the number of walkers. It also seems obvious that an arrival time larger than that of the slowest walker’s first arrival is not worth considering, it is a possible minimum, but any longer you can only be lapped by more walkers, so it can’t be any lower. The trick is to determine the potential arrival times of interest and calculate the number of meetings in time.
It is easy enough to sort everyone by their first arrival time, this gives a bunch of ranges to calculate the number of times you get lapped, but the naive approach of calculating number of times you get lapped is O(N) for each arrival time. And O(N^2) is not going to cut it for N=500000.
In between each arrival time the number of meetings can only go up, when you get lapped, the instant after an arrival time is the only time it can go down, and it only goes down by one. This leads to an observation. Arrival time 0 gives an upper bound on the answer of 0 and if you are considering arrival time of the kth earliest first arrival and the number of meetings which have occurred is greater than N+(N-k), there is no way the remaining meetings can get the total meetings below N. Therefore there is no value in continuing once you have reached 2N-k meetings, or more simply 2N. 2N is 1 million. So if we can simulate ‘every’ arrival time (not just the first arrivals) in O(log N) time each, and early out once we hit 2N, we can run in time. Simply putting walkers in a heap ordered by their next arrival time, and putting them back in with their next arrival time, will give the desired behaviour. Just need to track whether its first arrival or not in order to decrement or increment the times.
Oh and there is likely a corner case to do with equal arrival times, they have to be processed as a group because you can’t arrive in between them, only before or after. And getting accurate equal arrival times requires using fractions rather than floating point.