4
\$\begingroup\$

Problem Statement:

Watson gives Sherlock an array \$A_1\$, \$A_2\$ ... \$A_N\$. He asks him to find an integer \$M\$ between \$P\$ and \$Q\$ (both inclusive), such that, \$\min \{|A_i-M|, 1 \le i \le N\}\$ is maximised. If there are multiple solutions, print the smallest one.

Input Format:

The first line contains \$N\$. The next line contains space separated N integers, and denote the array \$A\$. The third line contains two space separated integers denoting \$P\$ and \$Q\$.

Constraints:

  • \$1 \le N \le 10^2\$
  • \$1 \le A_i \le 10^9\$
  • \$1 \le P \le Q \le 10^9\$

My code:

#include <bits/stdc++.h>
int main()
{   int size,print,dist=INT_MIN,answer,start,end,diff;
    std::vector <int> arr;
    std::cin>>size;
    for(int i=0;i<size;i++)
    {   int templ
        std::cin>>temp;
        arr.push_back(temp);
    }
    std::sort(arr.begin(),arr.end());
    std::cin>>start>>end;
    for(int i=start;i<=end;i++)
    {   
        dist=INT_MAX;
        for(int j=0;j<size;j++)
        {
            diff=fabs(i-arr[j]);
            if(diff>dist)
                break;
            dist=std::min(dist,diff);

        }
        if(dist>answer)
        {
            answer=dist;
            print=i;
        }
    }
    std::cout<<print;
    return 0;
}

My code is producing the output that I'm expecting, however it is failing with the hackerrank judge telling me that the time limit has been exceeded.

According to me its running time is O(n(p-q)). Then it should clear all the test cases in less than 2s (assuming computer can compute 10^9 problems in a second, I remember reading somewhere that that's how most online judges work). At most my program will work on 10^11 problems (n*p-q= 10^2 *10^11).

Do my timing predictions make sense?

How can I improve my code, particularly the performance so that it is able to pass this judge?

\$\endgroup\$
6
\$\begingroup\$

General Advise
Online coding challenges may not be timed as far as how long it takes to write them. Take the time to write better code rather than rushing through it. Don't make assumptions about the size of data or the run time that is allowed, on line research may be incorrect about this, because times won't be posted.

Big O Calculation
Does the Big O Calculation include the call to sort() if not, then that can be part of the timing problem.

Use Functions
The program is too complex and needs to be broken into functions. One function gets the array of numbers of input. Another function should do the calculation. The main() function should just control the program.

Declare Variables as Needed
There is a list of variables at the very beginning, this is more C like than C++. If the program is broken into functions this large list of variables at the top is not needed.

Meaningful Variable Names
The variable size is a good name, although the type might be size_t rather than int. The other variable names might be more meaningful if the were declared where they were needed.

Missing Includes
The code is missing some necessary include files:

#include <vector>
#include <iostream>
#include <algorithm>

std::sort()
The call to sort is missing the third argument, which should be the comparison to use in the sort.

\$\endgroup\$
  • 1
    \$\begingroup\$ There's no need to specify a comparison function as long as you're sorting items for which x < y is defined (and provides the ordering you want). \$\endgroup\$ – Jerry Coffin Jul 20 '16 at 15:58
  • \$\begingroup\$ @JerryCoffin Thank you, there are still things I need to learn. \$\endgroup\$ – pacmaninbw Jul 20 '16 at 16:03
  • 2
    \$\begingroup\$ You and me both! :-) I wouldn't bother posting here (questions or answers) if it weren't for the fact that I learn from doing so. \$\endgroup\$ – Jerry Coffin Jul 20 '16 at 16:16
5
\$\begingroup\$

You can achieve a tremendous speed-up by getting rid of that god-awful nested for-loop and simply thinking harder about the structure of the problem. This leads to the following observations:

Suppose that NONE of the elements of (sorted) arr[1 .. N] lie within the range [P .. Q]. Then either Q < arr[1] or arr[N] < P. In the first case, the min distance is clearly maximized by choosing M == P; in the second case, by choosing M == Q.

Otherwise find i (minimum) and j (maximum) such that each arr[k], for k in [i .. j], is in [P .. Q]. A little thought shows that the min distance is maximized by one of:

(a) P and arr[i]: Choose M = P

(b) arr[j] and Q: Choose M = Q

(c) M = (arr[k] + arr[k+1]) / 2 for some k in [i .. j]

I trust you can code that.

\$\endgroup\$
  • 1
    \$\begingroup\$ I joined codereview.se to upvote this answer. While the other answers tackle good coding practices, this one gets to the heart of the performance problem - finding a clever algorithm rather than brute force trying every possible value of M. \$\endgroup\$ – IanF1 Jul 20 '16 at 20:19
  • \$\begingroup\$ I was trying to guide OP to working this out himself so that he would learn something from the exercise. \$\endgroup\$ – Peter Taylor Jul 20 '16 at 21:35
1
\$\begingroup\$
    for(int i=0;i<size;i++)
    {   int templ
        std::cin>>temp;

Is that really the code you tested? I don't think it ought to compile...


As far as performance goes, it seems to me that with online judge questions in general you should assume that it's not required to iterate over 10^9 cases. I'm not going to describe an algorithm in detail, because that would IMO be missing the point, but ask yourself this: if the problem statement said \$1 \le N \le 1\$, would you still want to iterate over \$Q - P\$ cases or would there be a constant-time solution?

\$\endgroup\$
  • \$\begingroup\$ The OP seems to have cleaned up their code to remove the std namespace and minor other edits (revision 2 of the question) and made a few typos in the process... Nice catch. \$\endgroup\$ – forsvarir Jul 20 '16 at 17:26
1
\$\begingroup\$

Performance

You shouldn't rely only on big O notation to calculate real time. It is theoretical runtime scaling on some condition. There are a lot of conditions that come into play when you run on machine. Always measure.

push_back

You should use reserve() if its possible. In the current situation, you could easily write arr.reserve(size). It is implementation detail of the std::vector that it resizes every time it runs out of capacity. It usually increases exponentially, but multiplier is implementation defined (it's been 2 as long as I've seen).

Implementation defined

#include <bits/stdc++.h>

The contents of the header is totally implementation defined. You should never use it. I know that adding additional includes may take time, but generally you will get more feature complete versions if you include appropriate headers.

You do comparison to uninitialized variable:

if(dist>answer)

Seems like you're very lucky. You should initialize it to avoid undefined behavior. Also, increase level of warnings of the compiler, since it usually notifies about such parts of the code.

C++ way

For INT_MAX and INT_MIN you could as well use

std::numeric_limits<int>::max();
std::numeric_limits<int>::min();

Your inner loop could be replaced with range loop since you don't need the index.

   for(const auto& element: arr)
    {
        diff=fabs(i-element);
        if(diff>dist)
            break;
        dist=std::min(dist,diff);

    }
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.