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
j to compute all combinations of 3 segments and get the maximum probability. That's
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.
[1, 1, 1, 1, 1, 10] would be partitioned to
[1, 1, 1, 1, 1] and
We can compute
sum[i] beforehand, so the cost of computing the sum from
j is O(1).
Let's start with the binary search. We start with
(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,
If the 2nd segment's sum is greater then the 1st segment's sum, then we should move the
middle to the right. Therefore,
There are 2 problems:
end=2, then the
middlewill stay the same. So, we fix this by checking if
middlestays the same. If it does, we end the search.
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
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
This solution is fucking amazing. We start with
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
That is such a great solution.