<p>There's a famous problem these days in the interview prep community (particularly in PRAMP) called the awards budget cut problem.</p>
<p>The problem gives you an input of <span class="math-container">$n$</span> integers called grants <span class="math-container">$g_1 ... g_n$</span> along with an integer budget <span class="math-container">$B$</span>. We are then asked to find an integer <span class="math-container">$C$</span> (which we refer to as the cap) which has the following property:</p>
<p><span class="math-container">$C$</span> minimizes the number grants <span class="math-container">$g_i$</span> that are greater than it WHILE also ensuring that <span class="math-container">$\sum_{g_i} \lbrace{ \min(g_i, c)\rbrace} \le B$</span></p>
<p>Note that the value <span class="math-container">$C$</span> is not necessarily unique, there are multiple values that satisfy the condition above. Any such value is desirable.</p>
<p>Now theres a pretty simple <span class="math-container">$O(n \log n)$</span> 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.</p>
<p>Now the question is, is it possible to asymptotically do better? I'm reminded of the median problem which has a very similar &quot;relative-cut&quot; 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 <span class="math-container">$O(n)$</span> time.</p>
<p>I am very suspicious that a similar exotic awards grant algorithm should exist here.</p>
<p>See the following for more information:</p>
<p><a href="https://kobejean.github.io/algorithms/2020/03/08/the-award-budget-cuts-problem/" rel="nofollow noreferrer">https://kobejean.github.io/algorithms/2020/03/08/the-award-budget-cuts-problem/</a></p>
<p><a href="https://codereview.stackexchange.com/questions/194272/award-budget-cuts-implementation-in-java">https://codereview.stackexchange.com/questions/194272/award-budget-cuts-implementation-in-java</a></p>
<p><a href="https://leetcode.com/discuss/interview-question/351313/Google-or-Phone-Screen-or-Salary-Adjustment" rel="nofollow noreferrer">https://leetcode.com/discuss/interview-question/351313/Google-or-Phone-Screen-or-Salary-Adjustment</a></p>

CC BY-SA 4.0
2021-01-23T21:10:57.733Z
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.
Laakeri
CC BY-SA 4.0
2021-01-23T21:18:32.810Z
I wasn't aware of that, let me check it out
Sidharth Ghoshal
<cc.complexity-theory><time-complexity><greedy-algorithms>
Does the awards budget cut problem support a sub $O(n\log n)$ time solution?
Sidharth Ghoshal
# Does the awards budget cut problem support a sub $O(n\log n)$ time solution?

(Asked by: username_0 on 2021-01-23)

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>

**Tags:** cc.complexity-theory, time-complexity, greedy-algorithms

> **Comments:**
> **username_1**: 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.  
> **username_0**: I wasn't aware of that, let me check it out  

---

## 0 answers

