PROBLEM LINK:
Author: Praveen Dhinwa
Tester: Mugurel Ionut Andreica
Editorialist: Praveen Dhinwa
DIFFICULTY:
Simple
PREREQUISITES:
greedy
PROBLEM:
There are n villages in a city. The positions of the villages are given to you in the sorted order of their x coordinates. Note that all the villages are in a single line. Also you can assume that a village will be denoted by a single point on the x axis. Recently some of the villages have been electrified. You are given this information by a string s, where s_i = '1' denotes that i-th village has been electrified. You want to electrify all the villages by a connecting un-electrified villages by connecting with some already electrified village by establishing a electricity line between the villages. Find out the minimum length of electric wire required.
EXPLANATION:
One very simple observation is that if you connect some un-electrified village i to some electrified village j > i, then all the villages k (between i and j, i.e. i \leq k < j) will be electrified too.
Observation
It does not make any sense to not connect to some un-electrified village k to some village other than its left electrified village i, or its right electrified village j.
This observation allows us to split the villages on a line into segments such that end points of each segment are electrified (except the boundary villages, in that case, you might have zero or one of its end points being electrified.). We can solve the problem individually for each segment greedily and their total will be amount of wire required.
Let us consider a segment of the villages between village i to j, such that villages i and j are electrified and no intermediate village i < k j is electrified. What should be the minimum length of write needed to electrify all the intermediate villages. Note that we can electrify the intermediate villages by connecting them to some nearby electrified village. Note that each village will either be connected (via an electric wire passing through intermediate villages) to electrified village i on the left or to village j on the right.
In the optimal solution, we will be putting electric wire in the following way. An electric wire from i to some village k, and from village j to village k + 1.
Note that length of this wire will be total distance between village i and j minus the distance between village k and k + 1.
Note that we want to minimize value of length of wire. So, our aim is to maximize the value of x_{k + 1} - x_k for some k from i < k < j. We can easily find this value by iterating over the segment i to j once.
Pseudo Code
ans = 0;
ans = 0;
for (int i = 0; i < n; )
int j = n - 1;
for (int k = i + 1; k < n; k++)
if (lights[k] == '1')
j = k;
break;
maxDiff = 0
for (int k = i + 1; k < j; k++)
maxDiff = max(maxDiff, x[k + 1] - x[k]);
ans += x[j] - x[i] - maxDiff;
i = j;
Note that the we are looping over the villages only once. If you look naively, you might think that complexity of the algorithm is \mathcal{O}(n^2). But, the complexity of the algorithm is \mathcal{O}(n), because the number of times, the inner loop over k runs, the value of outer loop variable i gets increased by that value (check carefully that the last line is i = j), making sure that overall the loop runs in total \mathcal{O}(n). You can see that none of the indices of the villages will be encountered more than once in the inner for loop and in the outer for loop too. So, time complexity of this algorithm is \mathcal{O}(n).