×

# TWODOGS-Editorial

Author: A Surya Kiran
Tester: Hiroto Sekido, Gerald Agapov
Editorialist: Ajay K. Verma

Easy

# 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 i-th 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 i-th element is min(1 + i, N - i). We can denote this value by Si.

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(S3, S5, S9).

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]));
}
}


O (N)

# AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution will be put up soon.
Tester's solution will be put up soon.

This question is marked "community wiki".

6★djdolls
2.2k518484
accept rate: 0%

19.8k350498541

Why I am getting WA for my solution

(17 Feb '14, 15:47) 1★

@hrculiz It looks to me like you never check if the two apples are of the same type. I made the same mistake.

(17 Feb '14, 17:10) 1★
3

I think ans = min(ans,max( B[x],B[k - x]))...rather than their addition because both dogs leave at same time.

(17 Feb '14, 19:19)

Can you tell me why i got wa? http://www.codechef.com/viewsolution/3416902

(17 Feb '14, 21:17)

 3 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) http://www.codechef.com/viewsolution/3403591 answered 17 Feb '14, 21:45 8.7k●19●48●98 accept rate: 9%
 0 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 4★r3gz3n 52●1●2●8 accept rate: 0%
 0 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 206●1●3●5 accept rate: 40% 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)
 0 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 309●2●12 accept rate: 3%
 0 Can you tell me why i got wa? http://www.codechef.com/viewsolution/3416902 answered 18 Feb '14, 20:15 1●1●2●2 accept rate: 0%
 0 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 3.4k●19●43●77 accept rate: 16%
 0 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: #include using namespace std; int main() { int n,k; cin>>n>>k; int a[n]; for(int i=0;i>a[i]; int arr[n+1]; for(int i=1;i
 0 Can any one please explain why this solution gives a wrong answer? solution answered 30 May '14, 15:07 -3●1●4●8 accept rate: 0%
 0 how to solve this problem pls tell me @admin answered 28 Sep '14, 00:22 2★vickycod 21●1●1●2 accept rate: 6%
 0 why this Solution get WA APPROACH : Two pointer MY SOLUTION FOR TWODOGS answered 12 Sep '15, 21:12 1.1k●12●29 accept rate: 6%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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:

×15,678
×3,763
×19
×6

question asked: 17 Feb '14, 15:00

question was seen: 10,553 times

last updated: 12 Sep '15, 21:12