 # 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:

Tester’s solution

Setter’s Solution redirecting to dpraveen profile page.

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.

@dpraveen: is there any link for test cases ?

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

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…

1 Like

https://discuss.codechef.com/questions/17437/why-does-codechef-not-make-test-cases-public-after-the-contesthttps://discuss.codechef.com/questions/491/will-codechef-provide-test-cases

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

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

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

1 Like

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.

In the above pseudocode,
Test Case:- 100 and coordinates as 1 5 6,
The answer comes out to be 4 .

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

Hello I am doing exactly same as the editorial dont know why i am getting WA

import java.io.IOException;

/*

• 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 {
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++) {

 		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') {
for (int j = 1; j < n; j++) {
if (ls[j] == '1') {
preCnt = Integer.parseInt(vl[j]) - Integer.parseInt(vl);
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 == '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) {
}


}
}

Hello,codechef team will respond to this issues or not?

the logic is brilliant

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.

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.

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.

Hi pratyusg2013 please let me know why it is giving WA

//