CHEFELEC - Editorial

PROBLEM LINK:

Practice
Contest

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.

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.
Tester’s Solution access denied

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.

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…
CodeChef: Practical coding for everyonelink text

1 Like

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

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

1 Like

I am doing exactly same and its working correctly with my own test cases but still its coming WA, Can anyone help me?? CodeChef: Practical coding for everyone

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) {
     }
    

    }
    }

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

the logic is brilliant

Hi pratyusg2013 please let me know why it is giving WA

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 ?

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.

1 Like

Can some one tell me whats wrong in my solution?
https://www.codechef.com/viewsolution/10736188

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

i could not understand whats wrong in my code…please check this out
https://www.codechef.com/viewsolution/10713327

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!

2 Likes

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

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