Subtask 1

In this subtask, ~N = 2~, so there are exactly two lights.

First, let us sort the friends by increasing position. If there are any friends to the left of the leftmost light, we can expand its range to the left until it illuminates the leftmost friend. Similarly, if there are any friends to the right of the rightmost light, we can expand its range to the right until it illuminates the rightmost friend. Now, all friends which still need to be illuminated are between the two lights.

Let the position of the leftmost light be ~l~, the position of the rightmost light be ~r~, and the positions of the friends in between the lights be ~x_1, x_2, \dots, x_k~, in sorted order (i.e. ~l < x_1 < x_2 < \dots < x_k < r~). Additionally, let ~x_0 = l~ and ~x_{k+1} = r~ for convenience.

If the range of the leftmost light is expanded rightwards up to position ~x_j~, then it is optimal for the range of the rightmost light to expand leftwards up to position ~x_{j+1}~, where ~0 \le j \le k~. This leaves the positions strictly in between ~x_j~ and ~x_{j+1}~ unilluminated.

The cost of illuminating the friends in between the two lights for a given ~j~ is thus ~(r - l - 1) - (x_{j+1} - x_j - 1)~. In common terms, this is the cost if we illuminated all positions in between the two lights, subtracting the positions strictly between ~x_j~ and ~x_{j+1}~ which we don't illuminate.

To minimize this cost, we should maximize ~x_{j+1} - x_j - 1~. In other words, we should choose the longest gap to be the one left unilluminated so as to minimize the cost.

Thus, we can simply loop over all pairs of consecutive items between the lights (including both friends and the two lights) in sorted order and calculate the longest gap to find the minimum cost of illuminating the friends in between the two lights.

Adding the cost of illuminating the friends to the left of the leftmost light and to the right of the righmost light gives us a working solution for this subtask.

Time complexity: ~\mathcal{O}(M \log M)~

Subtask 2

Let us sort lights and friends by increasing position.

Notice that it is never optimal for a light's range to expand far enough that it illuminates another light.

Thus, the cost of illuminating friends between two consecutive lights is independent of the cost of illuminating the friends between a different pair of consecutive lights.

This allows us to run our Subtask 1 solution for friends in between two lights on all pairs of consecutive lights.

Friends to the left of the leftmost light and to the right of the rightmost light can be handled separately. Alternatively, dummy lights can be added at positions ~-\infty~ and ~\infty~ so all friends are between two lights, while the two dummy lights are still guarenteed to not be used.

This can be implemented with a two pointer approach.

Time Complexity: ~\mathcal{O}((N+M) \log (N+M))~ or ~\mathcal{O}(N \log N + M \log M)~

Bonus

Reference Solution

https://dmoj.ca/src/7505376

Alternative Solution

An alternative solution involves building a weighted graph whose minimum spanning tree corresponds to the minimum cost of illuminating the friends.

1. Sort all positions in increasing order.
2. Create a node for all lights and friends
3. Connect a dummy node to all lights with edges of weight ~0~.
4. For all pairs of consecutive items (including both lights and friends) in sorted order, add an edge between them with weight equal to their distance.

Running a minimum spanning tree algorithm on this graph effectively reduces to the intended solution, eliminating the longest gaps.

Time Complexity: ~\mathcal{O}((N+M) \log (N+M))~