PROBLEM LINK:Author: 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 unelectrified 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 unelectrified 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 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$. $$i >k \quad (k + 1)< j$$ Note that length of this wire will be total distance between village $i$ and $j$ minus the distance between village $k$ and $k + 1$. $$i.e. \text{length of wire} = (x_j  x_i)  (x_{k + 1}  x_k)$$ 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 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)$. Tester's Solutions:
This question is marked "community wiki".
asked 19 Jul '16, 21:38

I am a new comer.. My logic is correct but It is giving TLE... and given me 30 points during contest.. please help me and tell me why it is giving TLE... https://www.codechef.com/viewsolution/10813875link text answered 20 Jul '16, 03:27
Your code is really complicated. I think its time complexity might be $\mathcal{O}(n^2)$. Just check again whether the inner loop runs around $\mathcal{O}(n)$ or not.
(22 Jul '16, 00:09)

In an array/string the indexing is 0,1,...,n1 for n number of elements .Here i and j are acting like keys so they will always access the complete array and this will be hence a O(n) solution. answered 24 Jul '16, 15:09

I think this approach will give wrong answer for the test case 1000000 1 2 3 4 5 7 8 as its answer should be 7 but according to given editorial will come to be 5 ? Please can anyone explain the mistake! answered 04 Aug '16, 11:17

Setter's Solution redirecting to dpraveen profile page. Tester's Solution access denied answered 19 Jul '16, 23:30
@dpraveen: is there any link for test cases ?
(20 Jul '16, 00:02)
@the_run testcases are not provided... Read these for more info.. https://discuss.codechef.com/questions/17437/whydoescodechefnotmaketestcasespublicafterthecontest ... https://discuss.codechef.com/questions/491/willcodechefprovidetestcases ...
(20 Jul '16, 10:54)

Is this something wrong with this approach: for any 0 < i < n1, check the distance for first 1 in left side and also in right side, which ever is less, connect wire to that side. Any village in between will be electrified in the process. answered 19 Jul '16, 23:52
Yes, this is wrong. Because, sometimes you might want to break in the mid way (say some $i$, $i + 1$ because distance between $i$th and $i+1$th village is quite large, it is better to not to put a wire between them). e.g. Let us say $10001$ describe the electrification status of villages, i.e. only 1st and 5th villages are electrified. Say x coordinates of the villages are $[1, 2, 3, 10^9, 10^9 + 1]$ respectively. Now, it does not make any sense to retain the wire from village 3 to 4 (it requires length $10^9  3$).
(20 Jul '16, 00:54)
2
@dpraveen: It would look at the left and it would look at the right, which ever is small in distance to get the wire, it will connect to the smallest distance. For the given eg. 10001 and 1, 2, 3, 100, 101 In this case, for 2nd village with no electricity, it can get electricity from left by using 1 wire, from right by (101  2) = 99, so it would connect to the left. for 3rd village, it can get electricity from left by using 1 wire, from right by (101  3) = 98, so it would connect to the left.
(20 Jul '16, 19:47)
for 4th village, it can get electricity from left by using (100  3) = 97 wire, from right by (101  100) = 1, so it would connect to the right. So, in total it would only need 3 wire, which is the correct answer. It is able to handle cases like this, I guess, I am missing something else in this approach.
(20 Jul '16, 19:48)
Oh, this is what you meant. Actually, both of the approaches are precisely the same. If you see that if you from left to right, initially, you will be connecting to left village and then at some point you will start connecting with right village. The village at which you switch from left to right is precisely the village $k$.
(22 Jul '16, 00:03)
yeah thats true, but for some reason my solution is not accepted. Could you help me with some corner case I might be missing. https://www.codechef.com/viewsolution/10866465 One case may be is, when both left and right side needs same wire length, consider the side which can connect to more villages, usually it would mean connecting to the right side, as towards left as there would be only one village without electricity.
(23 Jul '16, 15:00)

Initially I tried to sovled the problem by doing binary search between two cities which had electricity but I have no clue why it was failing.Here is my solution https://www.codechef.com/viewsolution/10668698 Can anyone help me with it answered 20 Jul '16, 11:07
You can actually do binary search. But your implementation should be careful. Your code fails on all the test cases. I think you are probably missing something very important. Try debugging it on very small cases. If still not able to debug, let me know, I will try to give you input files on which you can debug.
(22 Jul '16, 00:11)

please look into my solution, I'm not able to identify the test cases that are causing it to fail https://www.codechef.com/viewsolution/10813479 answered 20 Jul '16, 19:26

I am doing exactly same and its working correctly with my own test cases but still its coming WA, Can anyone help me?? https://www.codechef.com/viewsolution/10864228 answered 21 Jul '16, 12:35

Hello I am doing exactly same as the editorial dont know why i am getting WA import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; / * To change this license header, choose License Headers in Project Properties. * To change this template file, choose Tools  Templates * and open the template in the editor. / / * @author samuel / public class Main {
} answered 21 Jul '16, 14:36
