1
$\begingroup$

Suppose given an array $A[1..n^2]$ that contains positives real values. Also we have a black box that have two input numbers $a,b$ and return true or false, also i know that, for any input, the black box return true for at least one pair. The goal is, we find two vales $a,b\in A$ such that $a+b$ minimized also the black box return true. Note that, each time i use the black box, it cost will be $O(n^2)$.

A simple brute force algorithm is as follow:

We check number of ways choose two numbers from $A$ (i.e. $\binom{n^2}{2}$) and give them to black box. The running time will be $O(n^6)$ that isn't efficient.

Are there an idea that work in $o(n^3)$? Or proof that show us the lower bound $\Omega(n^3)$?

$\endgroup$
6
  • 3
    $\begingroup$ If the black box returns false for every pair of numbers, how do you find it out without trying all the pairs? $\endgroup$ Commented Sep 11, 2021 at 7:57
  • $\begingroup$ @DmitriUrbanowicz The black box return true for a least one pair. $\endgroup$
    – ErroR
    Commented Sep 11, 2021 at 11:29
  • $\begingroup$ Can you at least compare a&b or sort wrong answers?or is it just some black box fn that we don't know and is only true for 1 pair (a,b)? $\endgroup$
    – ShAr
    Commented Sep 11, 2021 at 12:20
  • $\begingroup$ I mean if you can compare a,b for example, maybe you can do something like merge sort in O(n² log n); ie, for all the false pairs you only need to check the min and the problem size is reduced to half $\endgroup$
    – ShAr
    Commented Sep 11, 2021 at 12:46
  • $\begingroup$ @ShAr The black box can return True from some pair $(a,b)$, but we seek for a pair $(a,b)$ that $a+b$ minimized. Also the black box return true for at least one pair. Can you explain more about your idea? Thanks $\endgroup$
    – ErroR
    Commented Sep 11, 2021 at 21:08

1 Answer 1

3
$\begingroup$

You didn't specify if $a$ and $b$ can be the same element or if the black box is allowed to return different answers on inputs $a,b$ and $b,a$ therefore I'm going to conservatively assume that the both the above things are not allowed.

Let $m=n^2$. You need at least $\frac{m(m-1)}{2} - 1 = \Omega(m^2) = \Omega(n^4)$ queries to the black box in the worst case. If this was not the case then it is possible that: (i) all values in $A$ are distinct, and (ii) all the answer from all the queried pairs were "false". Since there are at least two distinct unordered pairs of unqueried elements, your algorithm cannot decide which of them to return.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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