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 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
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.
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??
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…
Why does codechef not make test cases public after the contest? - general - CodeChef Discuss … Will CodeChef provide test cases - help - CodeChef Discuss …
@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.
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.