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.

6 Likes

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). CodeChef: Practical coding for everyone

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

4 Likes

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 :slight_smile:
@bugkiller

Good question… got Ac, then wa CodeChef: Practical coding for everyone when new test files were added.
And then again Ac after checking logic CodeChef: Practical coding for everyone …

Can you tell me why i got wa? CodeChef: Practical coding for everyone

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?

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

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

solution

how to solve this problem pls tell me @admin

why this Solution get WA

APPROACH : Two pointer

MY SOLUTION FOR TWODOGS

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.

3 Likes

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

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.

1 Like

@admin please answer the question!!!

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

1 Like

i am getting runtime error…
plz help someone…

#include <bits/stdc++.h>
using namespace std;
int main()
{ // MAX
    long long int n, k;
    cin >> n >> k;
    unordered_map<long long int, vector<long long int>> tejus;
    unordered_map<long long int, bool> exist;
    for (long long int i = 0; i < n; i++)
    {
        long long int x;
        cin >> x;
        exist[x] = true;
        tejus[x].push_back(i);
    }
    long long int answer = INT_MAX;
    bool isthere = false;
    for (auto it = exist.begin(); it != exist.end(); it++)
    {
        long long int phela = it->first;
        long long int doosra = k - phela;
        if (exist[doosra])
        {
            if (phela == doosra)
            {
                if (tejus[phela].size() > 1)
                {
                    /*
                                        ( for equal phela & doosra )
                    index1 index2 ...             indexsecondlast indexlast
                    index1 , index2
                    index1 , n-indexlast-1
                    n-indexlast-1 , n-indexsecondlast-1        */
                    long long int index1 = tejus[phela][0];
                    long long int index2 = tejus[phela][1];
                    long long int indexsecondlast = tejus[phela][tejus[phela].size() - 2];
                    long long int indexlast = tejus[phela][tejus[phela].size() - 1];
                    long long int temp1 = max(index1, index2);
                    if (answer > temp1)
                    {
                        answer = temp1;
                        isthere = true;
                    }
                    temp1 = max(index1, n - 1 - indexlast);
                    if (answer > temp1)
                    {
                        answer = temp1;
                        isthere = true;
                    }
                    temp1 = max(n - 1 - indexlast, n - 1 - indexsecondlast);
                    if (answer > temp1)
                    {
                        answer = temp1;
                        isthere = true;
                    }
                }
            }
            else
            {
                /*
                    for different phela doosra
                    phelaindex1 ...      phelaindexlast
                    doosraindex1 ....    doosraindexlast
                    phelaindex1 , doosraindex1
                    phelaindex1 , n-1-doosraindexlast
                    n-1-phelaindexlast , doosraindex1
                    n-1-phelaindexlast , n-1-doosraindex1
                */
                long long int phelaindex1 = tejus[phela][0];
                long long int phelaindexlast = tejus[phela][tejus[phela].size() - 1];
                long long int doosraindex1 = tejus[doosra][0];
                long long int doosraindexlast = tejus[doosra][tejus[doosra].size() - 1];
                long long int temp = max(phelaindex1, doosraindex1);
                if (answer > temp)
                {
                    answer = temp;
                    isthere = true;
                }
                temp = max(phelaindex1, n - 1 - doosraindexlast);
                if (answer > temp)
                {
                    answer = temp;
                    isthere = true;
                }
                temp = max(n - 1 - phelaindexlast, doosraindex1);
                if (answer > temp)
                {
                    answer = temp;
                    isthere = true;
                }
                temp = max(n - 1 - phelaindexlast, n - 1 - doosraindex1);
                if (answer > temp)
                {
                    answer = temp;
                    isthere = true;
                }
            }
        }
    }
    if (!isthere)
    {
        cout << "-1\n";
    }
    else
    {
        cout << answer + 1 << "\n";
    }
}