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