# Find minimum pair number based on selection algorithm

If we have n balls in a red box (each ball is assigned a different number from 1 to n) and n balls in a green box (again each ball is assigned a different number from 1 to n). Lets say we have a player that chooses randomly a ball from each box and throws it on the floor. If we can predict exactly the time when a pair (red ball and green ball) given their numbers will be chosen (ex. input: red ball 5, green ball 6 output: 5sec ) , can we find the pair that will be chosen first in O(n) time?

The predictions costs: O(1) for each pair we input. We can predict as many pairs as we want

I have thought the simple solution: Predict every pair and then choose the minimum time, but that would cost $$O(n^{2})$$. I cannot optimize this further

• The balls presumably go back in the box after being "thrown on the floor"? Otherwise, once you've thrown out the red 7 with the green 3, the red 7 can't ever be thrown out with any other green ball. – j_random_hacker Nov 9 '19 at 15:25
• If so, dividing the balls into red and green gives no additional structure that can be exploited. By that I mean: If I have $m$ objects, each with an associated number, and I want to find the object with the lowest number, I can easily turn this into an instance of your problem using $\sqrt m$ red balls and $\sqrt m$ green balls by using any arbitrary 1:1 object-to-ball-pair mapping; if there is a way to solve your problem in $o(n^2)$ time then there is a way to solve my problem in $o(m)$ time, which would be surprising to say the least. – j_random_hacker Nov 9 '19 at 15:31