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

Improve this question
$\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, 2021 at 21:10
  • $\begingroup$ I wasn't aware of that, let me check it out $\endgroup$
    – Sidharth Ghoshal
    Jan 23, 2021 at 21:18

0

Reset to default

Your Answer

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