So I barely managed 615th out of the 1439 people who registered out of the 2500 potential people. My rating didn’t move down much as a result, but I was disappointed with my result all the same. Getting the second problem out was good for a guaranteed t-shirt, and solving the 1000pt was a guaranteed advancement. Advancement cut-off was 442 points.
Q1) Given 16 values arrange them into a 4×4 grid such that sum of all edge values + double the corners + the absolute difference between neighbour pairs is maximal. Return the maximal sum.
A1) I am not a fan of this question. I solved it quickly, but accidentally, with a poor solution which is not at all obviously correct. I then spent far too long trying to convince myself as to whether I was missing something critical, getting a low score in the process.
So the trick to this question is to convince yourself that the values given do not matter, if you sort them and place them the same as you would place 1 through 16 optimally, you still get an optimal solution. One such ordering is as follows:
16 3 15 8 4 14 1 13 12 2 11 5 7 10 6 9
The idea is that if you choose to have your largest 8 numbers in a checker board pattern the sum becomes 4 * sum of largest 8 – 4 * sum of the middle 2 (because they are surrounded) – 2 * sum of those on the edges (because their being on the edge offsets one of their 3 neighbours) – 0 * sum of those in the corners (because corner offsets both of the 2 neighbours). So it smallest 2 numbers go in the middle, next 4 smallest on the edges, and the next 2 in the corners, and the rest are checker boarded is optimal for the checker board scenario. A small inspection shows that the formula still holds if some of the smallest 8 are equal to some of the largest 8. All that remains is to prove that there is no scenario where 2 elements of the largest 8 are neighbours produces a better result. But I have no idea how to do that and the checker board pattern is somewhat ‘obviously’ good.
As a demonstration of why this problem was ‘broken’ – placing the numbers into the 4×4 square in sorted order (but not for all random orders) and them performing a greedy pairwise swap until no pairwise swaps improve the sum, would pass system tests, despite having practically no relation to the actual greedy arrangement.
Q2) Given a set of positions in a long narrow hallway, determine the minimum they have to move in order to get to a different set of positions, if they can only pass each other at either end of the hallway.
A2) This is where I am really disappointed with my self. Even with all of the time wasting I did on the first problem I still had > 25minutes left after my submission. However because I had become convinced that I was missing something with that first question, and no one else in the room had submitted the 500pt, and one person had skipped it in favour of the 1000pt, I decided it was a better investment in my time to try and come up with a killer test case to break my (and hopefully others) 250pt question. Which was both a) futile since everyone else’s code passed system tests and b) unsuccessful, since my solution passed system tests…
So this problem really isn’t that difficult. Sort by starting locations to get an ordered set of indexes, sort by ending locations to get another ordered set of indexes. Now there are 2 basic scenarios.
First up, some sub-range of the starting indexes which all have the same destination indexes directly shifts to their destinations while everything to the left shifts via the left end, and everything right shifts via the right end. This is only valid if every item to the left has a destination on the left, and every item on the right has a destination on the right. This has O(N^2) scenarios each with an evaluation time of O(N) to give O(N^3).
The second is a bit more complicated and I might have gotten it wrong (if there wasn’t a practice question which would have picked it up). In this case no elements move directly to their destination, everything moves either via the left or the right ends. So for every possible partition point you can consider everything going left and right, and getting to their destinations via the corresponding end points. However this doesn’t work if the set of destination indexes of the left and right sections aren’t also on the left and right. The trick is that these scenarios can all work, just that some items have to visit both ends.
So having partitioned the starting indexes into left and right groups, you also have to partition the destination indexes into left and right groups, and if they change groups, you have to add the extra distance of having visited both ends. This gives O(N^2) scenarios each with an evaluation time of O(N) to add an addition O(N^3). Input constraints were at most 50 items, so the result is easily managed.
Q3) Given a tree with black disks on some (non-root) nodes and a red disk on the root node, determine which nodes the red disk can visit by sliding along edges, if disks cannot pass through each other, but are otherwise all free to move along edges.
A3) Only 6 people solved this successfully, and none of the solutions are trivial to read and understand. General idea seems to be that you cache the number of black disks and the number of nodes for each sub-tree and then use that to determine whether the black disks can be shuffled out of the way to let the red disk to visit. If a node has multiple children and can be visited by the red disk, and not all of those children are filled, the red disk can visit some of the children, and potentially the black disks in the other children can be shifted up and into available spaces else where on the tree, allowing the red disk to reach even more locations. I think this logic gets applied repeatedly until no more red disk reach locations can be found. Without the cache the solution would be too slow.