PROBLEM LINK:Author: A Surya Kiran DIFFICULTY:Easy PREREQUISITES:Adhoc PROBLEM:Given a list of integers A and an integer k, pick two distinct elements from the list whose sum is k, and the sum of their shortest distance from the list ends is minimum. QUICK EXPLANATION:Create an array B such that B[x] is the shortest distance of an element with value x from the list ends. Now scan through values x in the array A, and return the minimum of max(B[x], B[k  x]) over all x (Do not consider the case when x = k  x). EXPLANATION:If we want to pick an element at the ith position in the list (i.e., A[i]), we need to travel either (1 + i) unit distance (if we start from the left end), or (N  i) unit distance (if we start from the right end). Hence, the shortest distance required to pick the ith element is min(1 + i, N  i). We can denote this value by S_{i}. If we want to pick an element whose value is x, then we need to find all occurrences of x in the array A, and take the minimum of S values of the corresponding indices. For example, if we want to find the shortest distance to pick an element with value 10, and the element 10 occurs at three times in array A (A[3], A[5], and A[9]), then the shortest distance to pick 10 would be min(S_{3}, S_{5}, S_{9}). Next, we discuss how to create these values using a single pass, i.e., create an array B, such that B[x] is the shortest distance needed to pick an element with value x. We initialize the array B with infinite (any number greater than N will suffice), and update it as we scan through the array A. B = {INF}; for (int i = 0; i < N; ++i) { int x = A[i]; int d = min(1 + i, N  i); B[x] = min(B[x], d); } Now, we have the shortest distance of each element. If one of the picked element is x, then the other picked element must be (k  x), and hence the time needed is max(B[x], B[k  x]) as both dogs start at the same time. We need to go through all possible values of x, and take the minimum of max(B[x], B[k  x]). If the minimum value turns out to be INF, then we have no solution, otherwise this minimum value is the desired answer. Since the picked element must be distinct, one should ignore the case when x = k  x. ans = INF; for (int i = 0; i < N; ++i) { int x = A[i]; if (x != k  x) { ans = min(ans, max(B[x], B[k  x])); } } TIME COMPLEXITY:O (N) AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution will be put up soon.
This question is marked "community wiki".
asked 17 Feb '14, 15:00

Those who are still not getting the idea or still confused why they are getting WA. I submitted a fully commented code for better readability. Feel free to see it and ask queries if you still have doubts. O(N) answered 17 Feb '14, 21:45

We can also solve it by start from both ends and keeping a track of all the numbers we scanned and simultanously checking if (k  A[i]) is in the numbers we are keeping track of(and break as soon as we find any). http://www.codechef.com/viewsolution/3351056 answered 17 Feb '14, 17:26

I am getting a WA for this question and even after spending quite some time on it i am unable to figure out why.. I generated some random test cases and tried comparing my WA soln(http://www.codechef.com/viewsolution/3435209) to this AC soln(http://www.codechef.com/viewsolution/3345479) and the answers seem to match(also I know this is not a good way to test, but still).. i probably am missing some test cases.so plz if someone can help me in figuring out what is wrong :) @bugkiller answered 18 Feb '14, 01:56
1
I don't know buddy. I tested it with some cases, it ran fine. I'll have a look again once I go back to my flat. I'm out right now.
(18 Feb '14, 17:50)

Good question... got Ac, then wa http://www.codechef.com/viewsolution/3435170 when new test files were added. And then again Ac after checking logic http://www.codechef.com/viewsolution/3410008 ... answered 18 Feb '14, 18:14

Can you tell me why i got wa? http://www.codechef.com/viewsolution/3416902 answered 18 Feb '14, 20:15

I am getting the correct answer for general test cases as well as corner cases (10^6). Does someone know a particular testcase where many programs may be failing? answered 21 Feb '14, 20:24

why am i getting a sigsegv error for the following program to the problem? I wnow specifically which instruction is creating the error. Here is the code:
answered 26 Feb '14, 19:25
@admin please answer the question!!!
(28 Feb '14, 19:40)
1
@insaynasasin The line causing SIGSEGV is arr[a[i]]=min(arr[a[i]],p); The reason you get the error is because the size of your array is a[n] and arr[n+1]. The limit for this n is 500000 while each element can be upto 1000000(10^6). So you might get some case where size of array is 100 and element is 1000 so you will try a memory access like a[1000] when size of your array is 100.
(28 Feb '14, 19:48)

answered 12 Sep '15, 21:12

Why I am getting WA for my solution
@hrculiz It looks to me like you never check if the two apples are of the same type. I made the same mistake.
I think ans = min(ans,max( B[x],B[k  x]))...rather than their addition because both dogs leave at same time.
Can you tell me why i got wa? http://www.codechef.com/viewsolution/3416902