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:

- 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. - 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.