You are not logged in. Please login at www.codechef.com to post your questions!

×

CHEFELEC - Editorial

0
1

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

This question is marked "community wiki".

asked 19 Jul '16, 21:38

dpraveen's gravatar image

4★dpraveen ♦♦
2.4k52124164
accept rate: 21%

edited 20 Jul '16, 11:01

admin's gravatar image

0★admin ♦♦
16.9k347485513


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

link

answered 20 Jul '16, 03:27

saxenarishav's gravatar image

2★saxenarishav
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) dpraveen ♦♦4★

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.

link

answered 24 Jul '16, 15:09

vidit_123's gravatar image

2★vidit_123
1036
accept rate: 5%

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!

link

answered 04 Aug '16, 11:17

yash17ag's gravatar image

3★yash17ag
11
accept rate: 0%

Setter's Solution redirecting to dpraveen profile page. Tester's Solution access denied

link

answered 19 Jul '16, 23:30

the_run's gravatar image

2★the_run
1624
accept rate: 0%

@dpraveen: is there any link for test cases ?

(20 Jul '16, 00:02) the_run2★

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.

link

answered 19 Jul '16, 23:52

the_run's gravatar image

2★the_run
1624
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) dpraveen ♦♦4★
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) dpraveen ♦♦4★

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★

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

link

answered 20 Jul '16, 11:07

sujeetsawala's gravatar image

5★sujeetsawala
1
accept rate: 0%

edited 22 Jul '16, 00:12

dpraveen's gravatar image

4★dpraveen ♦♦
2.4k52124164

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) dpraveen ♦♦4★

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

link

answered 20 Jul '16, 19:26

zkhan1093's gravatar image

2★zkhan1093
1
accept rate: 0%

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

link

answered 21 Jul '16, 12:15

vidit_123's gravatar image

2★vidit_123
1036
accept rate: 5%

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

link

answered 21 Jul '16, 12:35

sachinkmr's gravatar image

3★sachinkmr
1
accept rate: 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) {
    }
}

}

link

answered 21 Jul '16, 14:36

jawa2code's gravatar image

3★jawa2code
24127
accept rate: 0%

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

link

answered 21 Jul '16, 15:00

jawa2code's gravatar image

3★jawa2code
24127
accept rate: 0%

edited 27 Jul '16, 12:23

the logic is brilliant

link

answered 21 Jul '16, 23:19

pratyush2013's gravatar image

1★pratyush2013
1
accept rate: 0%

Hi pratyusg2013 please let me know why it is giving WA

link

answered 22 Jul '16, 10:26

jawa2code's gravatar image

3★jawa2code
24127
accept rate: 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 ?

link

answered 24 Jul '16, 01:14

rjspykar's gravatar image

3★rjspykar
1
accept rate: 0%

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

link

answered 24 Jul '16, 21:05

mohit_97's gravatar image

3★mohit_97
26
accept rate: 33%

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

link

answered 25 Jul '16, 00:06

vipinrao9398's gravatar image

2★vipinrao9398
1
accept rate: 0%

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

link

answered 26 Jul '16, 00:53

kbrockz's gravatar image

2★kbrockz
1
accept rate: 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

link

answered 20 Aug '16, 11:00

jawa2code's gravatar image

3★jawa2code
24127
accept rate: 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

link

answered 04 Jul, 20:45

priyanshuvarsh's gravatar image

3★priyanshuvarsh
11
accept rate: 0%

edited 04 Jul, 20:47

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.

link

answered 01 Nov, 23:10

atharva_sarage's gravatar image

3★atharva_sarage
11
accept rate: 0%

edited 02 Nov, 13:36

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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:

×11,984
×795
×719
×142
×2

question asked: 19 Jul '16, 21:38

question was seen: 5,406 times

last updated: 02 Nov, 13:36