You are not logged in. Please login at www.codechef.com to post your questions!

×

TWODOGS-Editorial

PROBLEM LINK:

Practice
Contest

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

DIFFICULTY:

Easy

PREREQUISITES:

Ad-hoc

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

TIME COMPLEXITY:

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

asked 17 Feb '14, 15:00

djdolls's gravatar image

6★djdolls
2.2k518484
accept rate: 0%

edited 26 Feb '14, 21:25

admin's gravatar image

0★admin ♦♦
19.8k350498541

Why I am getting WA for my solution

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

@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) ricola861★
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) xpertcoder4★

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

(17 Feb '14, 21:17) delta20132★

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

link

answered 17 Feb '14, 21:45

bugkiller's gravatar image

3★bugkiller
8.7k194898
accept rate: 9%

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

link

answered 17 Feb '14, 17:26

r3gz3n's gravatar image

4★r3gz3n
52128
accept rate: 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

link

answered 18 Feb '14, 01:56

bournecoder's gravatar image

3★bournecoder
206135
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) bugkiller3★

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

link

answered 18 Feb '14, 18:14

abcdexter24's gravatar image

2★abcdexter24
309212
accept rate: 3%

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

link

answered 18 Feb '14, 20:15

delta2013's gravatar image

2★delta2013
1122
accept rate: 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?

link

answered 21 Feb '14, 20:24

wittyceaser's gravatar image

2★wittyceaser
3.4k194377
accept rate: 16%

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<iostream>
using namespace std;
int main()
{
    int n,k;
    cin>>n>>k;
    int a[n];
    for(int i=0;i<n;i++)
        cin>>a[i];
    int arr[n+1];
    for(int i=1;i<n+1;i++)
        arr[i]=n+1;
    for(int i=0;i<n;i++)
    {
        int p=min(i+1,n-i);
        arr[a[i]]=min(arr[a[i]],p);
    }
    int time=n+1;
    for(int i=0;i<n;i++)
    {
        int p=a[i];
        if(p!=k-p&&p<k)
            time=min(time,max(arr[p],arr[k-p]));
    }
    if(time==n+1)
        cout<<"-1";
    else
        cout<<time;
}
link

answered 26 Feb '14, 19:25

insaynasasin's gravatar image

1★insaynasasin
1054811
accept rate: 0%

@admin please answer the question!!!

(28 Feb '14, 19:40) insaynasasin1★
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) kcahdog3★

Can any one please explain why this solution gives a wrong answer?

solution

link

answered 30 May '14, 15:07

pandeymht's gravatar image

5★pandeymht
-3148
accept rate: 0%

how to solve this problem pls tell me @admin

link

answered 28 Sep '14, 00:22

vickycod's gravatar image

2★vickycod
21112
accept rate: 6%

why this Solution get WA

APPROACH : Two pointer

MY SOLUTION FOR TWODOGS

link

answered 12 Sep '15, 21:12

rcsldav2017's gravatar image

5★rcsldav2017
1.1k1229
accept rate: 6%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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