2
$\begingroup$

There's a famous problem these days in the interview prep community (particularly in PRAMP) called the awards budget cut problem.

The problem gives you an input of $n$ integers called grants $g_1 ... g_n$ along with an integer budget $B$. We are then asked to find an integer $C$ (which we refer to as the cap) which has the following property:

$C$ minimizes the number grants $g_i$ that are greater than it WHILE also ensuring that $\sum_{g_i} \lbrace{ \min(g_i, c)\rbrace} \le B$

Note that the value $C$ is not necessarily unique, there are multiple values that satisfy the condition above. Any such value is desirable.

Now theres a pretty simple $O(n \log n)$ solution to this, which involves sorting the grants-array and then identifying the largest grant (usually through binary search or linear serach) such that the sum of all grants capped at this value end up being less than the budget.

Now the question is, is it possible to asymptotically do better? I'm reminded of the median problem which has a very similar "relative-cut" definition and whose optimal algorithm for a while always required sorting but then the exotic median-medians algorithm revealed that one could actually pull off $O(n)$ time.

I am very suspicious that a similar exotic awards grant algorithm should exist here.

See the following for more information:

https://kobejean.github.io/algorithms/2020/03/08/the-award-budget-cuts-problem/

https://codereview.stackexchange.com/questions/194272/award-budget-cuts-implementation-in-java

https://leetcode.com/discuss/interview-question/351313/Google-or-Phone-Screen-or-Salary-Adjustment

$\endgroup$
2
  • 1
    $\begingroup$ Just as a note, integers can be sorted faster than $O(n \log n)$ (Yijie and Thorup. "Integer Sorting in 0 (n sqrt (log log n)) Expected Time and Linear Space." FOCS. 2002.), so that gives a better algorithm :). Though I quess that in this context the relevant question is if we have some clever $O(n)$ algorithm. $\endgroup$
    – Laakeri
    Jan 23 '21 at 21:10
  • $\begingroup$ I wasn't aware of that, let me check it out $\endgroup$ Jan 23 '21 at 21:18

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.