×

CHEFELEC - Editorial

Author: Praveen Dhinwa
Tester: Mugurel Ionut Andreica
Editorialist: Praveen Dhinwa

Simple

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$.

$$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
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)$.

Tester's Solutions:

This question is marked "community wiki".

2.5k52135169
accept rate: 20%

19.5k348496535

 2 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 11 accept rate: 0% 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)
 2 In an array/string the indexing is 0,1,...,n-1 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 103●6 accept rate: 5%
 2 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 2★yash17ag 11 accept rate: 0%
 0 Setter's Solution redirecting to dpraveen profile page. Tester's Solution access denied answered 19 Jul '16, 23:30 2★the_run 16●2●4 accept rate: 0% @dpraveen: is there any link for test cases ? (20 Jul '16, 00:02) the_run2★ @the_run testcases are not provided... Read these for more info.. https://discuss.codechef.com/questions/17437/why-does-codechef-not-make-test-cases-public-after-the-contest ... https://discuss.codechef.com/questions/491/will-codechef-provide-test-cases ... (20 Jul '16, 10:54) an26093★
 0 Is this something wrong with this approach: for any 0 < i < n-1, 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 2★the_run 16●2●4 accept rate: 0% 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) the_run2★ 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) the_run2★ 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) the_run2★
 0 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 1 accept rate: 0% 2.5k●52●135●169 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)
 0 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 1 accept rate: 0%
 0 In the above pseudocode, Test Case:- 100 and coordinates as 1 5 6, The answer comes out to be 4 . @dpraveen Please Verify . answered 21 Jul '16, 12:15 103●6 accept rate: 5%
 0 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 1 accept rate: 0%
 0 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 { public static void main(String[] args) { try { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int t = Integer.parseInt(br.readLine()); int n = 0, preCnt = 0, postCnt = 0, preD = 0, left_Index = 0, right_Index = 0; long result = 0, aux = 0; char ls[] = null; String vl[] = null; for (int i = 0; i < t; i++) { n = Integer.parseInt(br.readLine()); ls = br.readLine().toCharArray(); vl = br.readLine().split(" "); if (n == 1) { System.out.println(0); continue; } result = 0; preCnt = 0; postCnt = 0; preD = 0; left_Index = 0; right_Index = 0; // =================================STEP-1======================================== /* * Finding the from extreme left unelectrified Village to First * Electrified Village that is preCnt */ if (ls[0] == '0') { for (int j = 1; j < n; j++) { if (ls[j] == '1') { preCnt = Integer.parseInt(vl[j]) - Integer.parseInt(vl[0]); left_Index = j; /* * skipping all continues electrified Villages */ for (int k = j + 1; k < n; k++) { if (ls[k] == '0') { left_Index = k - 1; break; } } break; } } } if (ls[0] == '1') { for (int j = 1; j < n; j++) { if (ls[j] == '0') { left_Index = j - 1; break; } } } // =========================================STEP-2===================================== /* * Finding the length from extrem right unelectified Village to * last Electrified Village and storing in to 'postCnt' */ if (ls[n - 1] == '1') { right_Index = n - 1; for (int j = n - 2; j >= 0; j--) { if (ls[j] == '0') { right_Index = j + 1; break; } } } if (ls[n - 1] == '0') { right_Index = n - 1; for (int j = n - 2; j >= 0; j--) { if (ls[j] == '1') { postCnt = Integer.parseInt(vl[n - 1]) - Integer.parseInt(vl[j]); right_Index = j; for (int k = j - 1; k >= 0; k--) { if (ls[k] == '0') { right_Index = k + 1; break; } } break; } } } // ==================================================================================== /** * Adding the Above 2 lengths in to 'result' result = preCnt + * postCnt; */ result = preCnt + postCnt; // ========================================STEP-3============================================ /** * Now we have first and last electified villages(with Indexes ) * we need to find the next electrified Village from the first * electrified village once it finds the second electified check * whether the last index reached or not to check whether it is * last electrified village or not find the Maximum distance * between any 2 unelectrified villages between first and next * Electrified Villages and remove that from the distance * between First and Next Ecectrified Village Alwyas skip all * contnues electrified villages */ int maxD = 0; if (right_Index != left_Index) { maxD = -1; for (int j = left_Index; j < right_Index; j++) { if (ls[j + 1] != '1') {// if it is 0 /** * Find max distznce between any of the consicutive * 2 un electrified Villages */ preD = Integer.parseInt(vl[j + 1]) - Integer.parseInt(vl[j]); if (maxD <= preD) { maxD = preD; } } else {// if it is 1 /** * Once it finds the Next Electified Village * caliculate the distance between fist and next * electrified Village and subtract the Max distance */ preD = Integer.parseInt(vl[j + 1]) - Integer.parseInt(vl[j]); if (maxD <= preD) { maxD = preD; } aux = Integer.parseInt(vl[j + 1]) - Integer.parseInt(vl[left_Index]); aux = aux - maxD; result += aux; maxD = -1; int k = j + 2; /** * Skip all contimnus electrified Villages */ for (; k <= right_Index; k++) { if (ls[k] != '0') { left_Index = k - 1; j = left_Index; j--; break; } } } } } System.out.println(result); } } catch (IOException ex) { } }  } answered 21 Jul '16, 14:36 24●1●2●7 accept rate: 0%
 0 Hello,codechef team will respond to this issues or not? answered 21 Jul '16, 15:00 24●1●2●7 accept rate: 0%
 0 the logic is brilliant answered 21 Jul '16, 23:19 1 accept rate: 0%
 0 Hi pratyusg2013 please let me know why it is giving WA answered 22 Jul '16, 10:26 24●1●2●7 accept rate: 0%
 0 Here, 'i' never reaches to n or above because i=j and j is always initialised to n-1. So it goes into infinite loop. Isn't it ? Help me if I am wrong anywhere ? answered 24 Jul '16, 01:14 2★rjspykar 1 accept rate: 0%
 0 Can some one tell me whats wrong in my solution? https://www.codechef.com/viewsolution/10736188 answered 24 Jul '16, 21:05 3★mohit_97 26 accept rate: 33%
 0 Can anyone tell me why my answer is wrong,i am not able to find why it shows wrong answer. https://www.codechef.com/viewsolution/10783010 answered 25 Jul '16, 00:06 1 accept rate: 0%
 0 i could not understand whats wrong in my code..please check this out https://www.codechef.com/viewsolution/10713327 answered 26 Jul '16, 00:53 2★kbrockz 1 accept rate: 0%
 0 Cc is not just checking the result and time it takes to produce results, they are looking any if condition present in the code, if it is they reject with WA, it is misdleading answered 20 Aug '16, 11:00 24●1●2●7 accept rate: 0%
 0 in the last for loop: for (int k = i + 1; k < j; k++) maxDiff = max(maxDiff, x[k + 1] - x[k]); K should start from i i.e. k=i, Please confirm my doubt answered 04 Jul '17, 20:45 1●1 accept rate: 0%
 0 Please can anyone find error in my code? I am not able to figure where it is failing? https://www.codechef.com/viewsolution/16029066 Task 2 and 3 of subtask 2 is showing AC but others WA. answered 01 Nov '17, 23:10 1●1 accept rate: 0%
 0 Can we do it like this?? We can map the distances to their respective value of '0' or '1'. After this we can apply sorting to map and for every value of '0' we need to find the rightmost 1?? answered 28 Sep, 18:54 0●1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,029
×1,084
×923
×142
×2

question asked: 19 Jul '16, 21:38

question was seen: 5,965 times

last updated: 28 Sep, 18:54