Loading page…
Practice problem · medium
A Kestrel Ads page has three ad slots, and each slot goes to a different bidder. Some publishers set a page budget: the three bids shown together must add up to less than it.
Before a publisher picks a budget, the campaign planner estimates how easily the page will fill. The estimate is one number: how many triples of different bidders have bids that add up to less than the budget. Bids are integers in units, and the list is in no particular order. Two bidders can bid the same amount and still count as different bidders.
Write count_under(bids, budget).
bids[i] is the bid of bidder i in units. The list is not sorted and may hold equal bids.budget is the page budget in units.i < j < k with bids[i] + bids[j] + bids[k] < budget.budget does not fit: the total must be strictly less.0.Input: bids = [4000, 1000, 7000, 3000, 2000, 6000], budget = 10000
Output: 5Sorted, the bids are [1000, 2000, 3000, 4000, 6000, 7000]. The trace works on that sorted copy.
| i | First bid | left | right | Total | Under 10000? | Triples added | count |
|---|---|---|---|---|---|---|---|
| 0 | 1000 | 1 | 5 | 10000 | no | 0 | 0 |
| 0 | 1000 | 1 | 4 | 9000 | yes | 3 | 3 |
| 0 | 1000 | 2 | 4 | 10000 | no | 0 | 3 |
| 0 | 1000 | 2 | 3 | 8000 | yes | 1 | 4 |
| 1 | 2000 | 2 | 5 | 12000 | no | 0 | 4 |
| 1 | 2000 | 2 | 4 | 11000 | no | 0 | 4 |
| 1 | 2000 | 2 | 3 | 9000 | yes | 1 | 5 |
| 2 | 3000 | 3 | 5 | 14000 | no | 0 | 5 |
| 2 | 3000 | 3 | 4 | 13000 | no | 0 | 5 |
| 3 | 4000 | 4 | 5 | 17000 | no | 0 | 5 |
When 1000 + 2000 + 6000 fits, 1000 and 2000 also fit with 3000 and 4000, which are lower than 6000. That is 3 triples counted in one step. The totals 1000 + 2000 + 7000 and 1000 + 3000 + 6000 equal the budget, so they do not fit.
Input: bids = [2500, 2500, 2500, 2500], budget = 8000
Output: 4Every three of the four bidders total 7500. There are 4 ways to choose three bidders, so the count is 4, even though the bids are equal.
Input: bids = [5000, 5000], budget = 20000
Output: 0Two bidders cannot fill three slots.
1 ≤ bids.length ≤ 3,000 (the bidders for one page)1 ≤ bids[i] ≤ 10^91 ≤ budget ≤ 3 × 10^9Checking every triple costs n × (n − 1) × (n − 2) / 6 checks: about 4.5 × 10^9 at n = 3,000. That is far over the budget of about 10^8 simple operations a second. An O(n^2) solution makes about 4.5 × 10^6 steps, which fits easily.
Read the sizes too. Three bids can total 3 × 10^9, and budget can be 3 × 10^9, both above the 32-bit limit of 2,147,483,647. When every triple fits, the count is 4,495,501,000, also above it. Use long in Java and long long in C++ for the total, the budget and the count.
count_under · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.