# Greedy Florist

This problem comes from HackerRank.

You can see my full solution in the GitHub repo.

## Problem Summary

This problem is poorly written, so I advise you to refer to my
summary. A group of `k`

people want to work together to buy flowers
`f1, f2...fn`

, which have base prices `p1, p2...pn`

. The florist
works with a single customer at a time, and each time a customer
buys a flower a multiplier associated with that customer is
increased by one. So if `customer1`

buys flowers `f1, f2, and f3`

then `customer1`

's total cost will be `p1 + 2*p2 + 3*p3`

.

Furthermore if `customer2`

buys flowers `f4 and f5`

, then the total
price for the group is `p1 + 2*p2 + 3*p3 + p4 + 2*p5`

.

Your objective is to determine the minimum cost for the group of customers to buy all of the flowers.

## Naive Approach

After working through some small examples you might sense that it's best for the group to take turns buying the most expensive flower, until they've bought them all.

This is a greedy algorithm; one where optimization occurs by way of a single decision policy without looking ahead. A good programmer is wary of greedy algorithms because they are rarely optimal and often a distraction from the dynamic programming solution that's actually required.

But in this case, try as you might, you cannot devise a case where this greedy policy is suboptimal. But before you can totally trust it, you must prove it.

## Proving the Greedy Algorithm

Our approach here is simple: state what we know as facts, then transform what we think we know into those facts. We should end up with a clear confirmation or contradiction of the facts.

Earlier we described our approach as the group "taking turns". We
will call one set of turns a *round*, so in `round1`

all purchases
occur with multiplier 1, in `round5`

all purchases occur with
multiplier `5`

, and generally in `roundM`

all purchases occur with
multiplier `M`

.

We want to prove that buying the maximum-price flower in an early
round *always* yields a cost smaller than buying the maximum-price
flower in a later round.

Assume `p1`

is the maximum flower price and `p2`

is sub-maximum,
i.e. `p1 > p2`

. Assume `r1`

is the early round multiplier and `r2`

is the later round multiplier, i.e. `r1 < r2`

. We want to show that
`p1*r1 + p2*r2 < p1*r2 + p2*r1`

, so we simplify

Original: p1*r1 + p2*r2 < p1*r2 + p2*r1 Subtract p1*r2: p1*r1 + p2*r2 - p1*r2 < p2*r1 Subtract p2*r2: p1*r1 - p1*r2 < p2*r1 - p2*r2 Factor out p1 and p2: p1(r1 - r2) < p2(r1 - r2) Divide by (r1 - r2): p1 < p2

But wait, that contradicts our assumption `p1 > p2`

. What has gone
wrong?

If you're comfortable with proofs, then you already know my
mistake. I had to go through the stages with real numbers before I
noticed it, and I felt dumb for it. Remember when we stated ```
r1 <
r2
```

? Well that implies `r1 - r2 < 0`

, and whenever you multiply or
divide by a negative on an inequality, you must flip the
sign. Therefore the correct last step in the proof is

Divide by (r1 - r2): p1 > p2

This confirms our intuitions and we can confidently implement the algorithm.

## Implementation

In deciding how to store flower costs we need random insertion, maximum access, and maximum deletion: this sounds just like a max-heap!

To determine the price multiplier for the `ith`

flower, we need only
calculate `floor(i / k) + 1`

. This is a clever translation of what
1-based *round* the purchase belongs to.

Besides I/O the meat of the thing is only a couple lines

long long cost{0}; int count{0}; while (!costs.empty()) { cost += costs.top() * ((count / k) + 1); costs.pop(); ++count; }

## Final Complexity

Given `n`

flowers, each max-heap insertion is `O(log(n))`

, so
ingestion is `O(nlog(n))`

(i.e. we had to compare-sort the costs).

Purchasing a flower requires one max-access (`O(1)`

), one
max-deletion (`O(log(n))`

thanks to reheapification), and some
constant arithmetic. Therefore purchasing all `n`

flowers is
`O(nlog(n))`

.

We could use a Fibonacci heap which has constant insertion cost,
making ingestion a `O(n)`

operation, but we can not alleviate the
`O(nlog(n))`

bottleneck in the purchasing loop with heap variants.