Codejam 2014 - Round 3 - Magical, Marvelous Tour

1 Dec 2015

First, we have to know that:

It's always better for Arnar to segment the devices into 3 segments (better than 2 segments)

There are exceptions: if there's only 1 device, then Solveig gets it. The answer is 0.0. If there are only 2 devices, Arnar will get the smaller device.

Now let's look at the cases where there are 3 or more devices.

The brute-force solution is obvious. We can loop with i and j to compute all combinations of 3 segments and get the maximum probability. That's O(n^2).

But it's not fast enough for the large dataset.

The gist of the game is that Arnar should segment an array into 3 segments in order to minimise the maximum number of transistors among 3 segments.

We can definitely iterate through i and use binary search to get the optimal j. The binary search here is the interesting part because the binary search wants to search for j that minimises the maximum between 2 segments.

The binary search is very tricky. I spent a lot of time to get it right. Let's reduce the problem to finding a partition that minimises the sum values of 2 segments.

For example, [1, 1, 1, 1, 1, 10] would be partitioned to [1, 1, 1, 1, 1] and [10].

We can compute sum[i] beforehand, so the cost of computing the sum from i to j is O(1).

Let's start with the binary search. We start with start=0 and end=N-1. The middle is (start + end) / 2). Let's say middle is included in the first segment.

If the 1st segment's sum is greater than the 2nd segment's sum, then we should move the middle to the left. Therefore, end=middle.

If the 2nd segment's sum is greater then the 1st segment's sum, then we should move the middle to the right. Therefore, start=middle.

There are 2 problems:

  1. If start=1 and end=2, then the middle will stay the same. So, we fix this by checking if middle stays the same. If it does, we end the search.
  2. The optimal middle might not yield the equal sum. For example, you arrive at the optimal middle early, but the 1st segment's sum is greater than the 2nd segment's sum. Therefore, the middle is recomputed.

The twist here is that we don't use binary search to get the optimal middle. We use it to scope down the possibility. Then, after the binary search ends, we iterate from start to end to find the optimal middle.

There's another solution that flips how we think about how we should search for the optimal answer.

We can simply say that K is the optimal number of transistors that Arnar will get. Then we do binary search for K.

This solution is fucking amazing. We start with start=0 and end=[total number of transistors]. Then, we ask if middle is a possible solution by segmenting the array into 3 segments whose sum is not more than middle. If it's possible, we reduce middle because we try to minimise the maximum sum among 3 segments. If it's not possible, we increase middle.

That is such a great solution.