Ice Cream Shop
Contest: SWERC 2021-2022 - Online Mirror (Unrated, ICPC Rules, Teams Preferred)
Tags: brute force, implementation, sortings

On a beach there are $$$n$$$ huts in a perfect line, hut $$$1$$$ being at the left and hut $$$i+1$$$ being $$$100$$$ meters to the right of hut $$$i$$$, for all $$$1 \le i \le n - 1$$$. In hut $$$i$$$ there are $$$p_i$$$ people.

There are $$$m$$$ ice cream sellers, also aligned in a perfect line with all the huts. The $$$i$$$-th ice cream seller has their shop $$$x_i$$$ meters to the right of the first hut. All ice cream shops are at distinct locations, but they may be at the same location as a hut.

You want to open a new ice cream shop and you wonder what the best location for your shop is. You can place your ice cream shop anywhere on the beach (not necessarily at an integer distance from the first hut) as long as it is aligned with the huts and the other ice cream shops, even if there is already another ice cream shop or a hut at that location. You know that people would come to your shop only if it is strictly closer to their hut than any other ice cream shop.

If every person living in the huts wants to buy exactly one ice cream, what is the maximum number of ice creams that you can sell if you place the shop optimally?

Input format:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 200\,000$$$, $$$1 \le m \le 200\,000$$$) — the number of huts and the number of ice cream sellers.

The second line contains $$$n$$$ integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le 10^9$$$) — the number of people in each hut.

The third line contains $$$m$$$ integers $$$x_1, x_2, \ldots, x_m$$$ ($$$0 \le x_i \le 10^9$$$, $$$x_i \ne x_j$$$ for $$$i \ne j$$$) — the location of each ice cream shop.

Output format:
Print the maximum number of ice creams that can be sold by choosing optimally the location of the new shop.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first sample, you can place the shop (coloured orange in the picture below) $$$150$$$ meters to the right of the first hut (for example) so that it is the closest shop to the first two huts, which have $$$2$$$ and $$$5$$$ people, for a total of $$$7$$$ sold ice creams.

In the second sample, you can place the shop $$$170$$$ meters to the right of the first hut (for example) so that it is the closest shop to the last two huts, which have $$$7$$$ and $$$8$$$ people, for a total of $$$15$$$ sold ice creams.

Example input:
3 1
2 5 6
169

Example output:
7

Example input:
4 2
1 2 7 8
35 157

Example output:
15

Editorial:
Suppose there are ice cream shops located $$$a$$$ and $$$b$$$ meters to the right of the first hut, such that $$$a < b$$$. If we place our ice cream shop in any location in the interval $$$[a, \, b]$$$ it can only be strictly closer to huts located in the interval $$$(a, \, b)$$$, since any hut located at or before $$$a$$$ will be closer to the ice cream shop located at $$$a$$$ and any hut located at or after $$$b$$$ will be closer to the ice cream shop located at $$$b$$$. We now present two approaches to solve the problem starting from this observation.
First solution
Let $$$a < b$$$ be the positions of two ice cream shops, and let us further assume that there is no other ice cream shop between $$$a$$$ and $$$b$$$. Of course, it is never convenient to put the new shop at $$$a$$$ or $$$b$$$. What happens if we place our new shop at $$$s \in (a, \, b)$$$? It is easy to see that the only huts whose people will buy ice creams are those in the open interval $$$\left(\frac{a + s}{2}, \, \frac{s + b}{2}\right)$$$. Notice that this interval has length $$$\frac{s + b}{2} - \frac{a + s}{2} = \frac{b - a}{2}$$$, i.e., half the length of $$$(a, \, b)$$$, which is independent of $$$s$$$.
On the other hand, consider an interval $$$(l, \, r)$$$ such that $$$a \le l < r \le b$$$ and $$$r - l = \frac{b - a}{2}$$$. If we choose $$$s = 2l - a$$$, the interval $$$\left(\frac{a + s}{2}, \, \frac{s + b}{2}\right)$$$ is exactly $$$(l, \, r)$$$. This means that for every interval $$$(l, \, r)$$$ of length $$$\frac{b - a}{2}$$$ which lies entirely in $$$(a, \, b)$$$, it is possible to achieve a total number of ice creams given by $$$$$$ f(l, \, r) := \sum_{100i \, \in \, (l, \, r)} p_{i + 1}. $$$$$$ (Recall that the position of the $$$i$$$-th hut is $$$100(i - 1)$$$.)
Thus the answer is the maximum of $$$f(l, \, r)$$$, over all intervals such that there exist $$$a$$$ and $$$b$$$ as above and $$$r - l \le \frac{b - a}{2}$$$. Also notice that we can restrict our search to the intervals with $$$l = 100k - \frac{1}{2}$$$ for some $$$0 \le k \le n - 1$$$. We can therefore proceed as follows.
• Iterate over $$$k = 0, \, \dots, \, n - 1$$$.
• For each $$$k$$$, find the greatest $$$x_j < 100k$$$. This can be done in amortized constant time — or via binary search — after sorting the $$$x_j$$$'s.
• Compute $$$f(l, \, r)$$$, where $$$l = 100k - \frac{1}{2}$$$ and $$$r = \min\left(x_{j + 1}, \, l + \frac{x_{j + 1} - x_j}{2}\right)$$$ (assume the $$$x_j$$$'s are sorted). This is easy to do having precomputed the prefix sums of $$$p_1, \, \dots, \, p_n$$$.
• Return the maximum of all these values.
One must be careful with "boundary conditions", that is, values of $$$k$$$ such that $$$100k$$$ lies to the left or to the right of all ice cream shops. These are best handled by introducing two dummy shops at positions $$$-\infty$$$ and $$$+\infty$$$.
The solution has $$$\mathcal O(n + m\log m)$$$ time complexity and $$$\mathcal O(n + m)$$$ space complexity.
Second solution
Pick again two ice cream shops at $$$a < b$$$, with no other ice cream shops in between, and consider a hut located at $$$h$$$ such that $$$a < h < b$$$. If we place our shop in $$$s$$$ such that $$$s$$$ is between $$$a$$$ and $$$h$$$, then we will always be closer to $$$h$$$ than the ice cream shop located at $$$a$$$. However, we are only closer than the ice cream shop at $$$b$$$ if the distance from $$$s$$$ to $$$h$$$ is smaller than the distance from $$$h$$$ to $$$b$$$. Formally this means $$$h - s < b - h$$$. If we rearrange this expression, we conclude that we will be closer to $$$h$$$ if $$$s > 2h - b$$$. Analogously, if we place our shop in $$$s$$$ such that $$$s$$$ is between $$$h$$$ and $$$b$$$, we will be closer to $$$h$$$ if $$$s < 2h - a$$$. Hence, we conclude that if we want to be closer to $$$h$$$ then we have to place our shop in the interval $$$(2h - b, \, 2h - a)$$$ (note that this is an open interval since we want to be strictly closer to $$$h$$$).
Using this idea, we can now compute for every hut $$$h$$$ an interval such that if we place our shop in any point in that interval then our shop will be the closest to hut $$$h$$$. Let us assume we have all these intervals, how do we determine the optimal solution from this information? Notice that the optimal solution is a point that maximizes the sum of the $$$p_i$$$ of all the intervals it is contained in. We can find this maximum sum efficiently using a sweep-line approach. Picture a vertical line that is going to sweep through all of these intervals from left to right. As this line moves we want to keep the sum of the $$$p_i$$$ corresponding to the intervals it currently intersects, so we store that value in a counter and whenever the line reaches the starting point of an interval we add its value to the counter, conversely whenever it reaches the endpoint of an interval we subtract its value from the counter. The solution is the maximum value the counter achieves during this process.
To implement this efficiently, the only thing we need to observe is that the only relevant "events" to this procedure are the start- and endpoints of intervals. So our sweep-line algorithm can be implemented as follows: for every interval $$$(l_i, \, r_i)$$$ corresponding to hut $$$p_i$$$ add a point $$$(l_i, \, p_i)$$$ and a point $$$(r_i, \, -p_i)$$$ to a list of points. Sort this list according to the first component. Iterate through the sorted points and store a counter (initially $$$0$$$). Whenever we reach a point $$$(a, \, b)$$$ add $$$b$$$ to the counter. This requires time $$$\mathcal O(n \log n)$$$ since we have to sort all of the $$$2n$$$ "event" points and then iterate through them once.
Before doing that, however, we need to compute each hut's interval. To do so we have to determine the closest ice cream shops $$$a$$$ and $$$b$$$ such that $$$a < h$$$ and $$$b > h$$$ and then the interval is given by $$$(2h - b, \, 2h - a)$$$. If we sort the $$$x_i$$$ locations of all the ice cream shops we can find this using binary search or by iterating through the huts and ice cream shops simultaneously (this is also known as a two pointers technique). The time complexity of the binary search method is $$$\mathcal O((m + n) \log m)$$$, since we first sort the $$$x_i$$$ and then for each hut we perform one binary search. The time complexity of the two pointers method is $$$\mathcal O(m \log m + n)$$$, since we first sort the $$$x_i$$$ and then iterate through all the $$$n$$$ huts and $$$m$$$ ice cream shops once.
Combining all of this we get a solution that runs in $$$\mathcal O(m\log m + n \log n)$$$ time.