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

  • $\begingroup$ 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. $\endgroup$ – j_random_hacker Nov 9 '19 at 15:25
  • $\begingroup$ 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. $\endgroup$ – j_random_hacker Nov 9 '19 at 15:31

Your Answer

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

Browse other questions tagged or ask your own question.