CHEFELEC - Editorial



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.


Can some one tell me whats wrong in my solution?


Can anyone tell me why my answer is wrong,i am not able to find why it shows wrong answer.


i could not understand whats wrong in my code…please check this out


I think this approach will give wrong answer for the test case
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!


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


Please can anyone find error in my code? I am not able to figure where it is failing?
Task 2 and 3 of subtask 2 is showing AC but others WA.


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??


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


@the_run testcases are not provided… Read these for more info…


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


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.


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.