- Practice
- Algorithms
- Greedy
- Greedy Florist
- Discussions

# Greedy Florist

# Greedy Florist

cgnicholls + 8 comments I think this problem is poorly worded. It should say that as a group you have to buy one flower of each type. As stated, it could mean you simply want to buy N flowers; in this interpretation, you would only ever buy the cheapest type of flower. The example shows that it is the other interpretation that is correct, but the problem statement is ambiguous.

david_guijarro + 1 comment +1, totally correct it is really poorly written...

iainws + 1 comment Thanks, good problem. Hard to understand at first.

edrouwendaal + 0 comments also starting programme for C# does not have initial size of array

FaxMachin3 + 7 comments # C# Code:

**O(n + nLogn)**int n = c.Length; int minCost = 0; int tempCount = 0; int previousPurchases = 0; Array.Sort(c); if(k >= n){ for(int i = 0; i < n; i++) minCost += c[i]; } else{ for(int i = n - 1; i >= 0; i--){ if(tempCount == k){ tempCount = 0; previousPurchases++; } minCost += (previousPurchases + 1) * c[i]; tempCount++; } } return minCost;

2017uee1085 + 1 comment you can keep a track of purchases of individual customers in an array by initialising default values with zero and access them by %k in iteration of cost loop.

sigmasys + 0 comments no need. if only c[i]+n<=c[i+1], continue by c[i]. unitle the whole c list done.

99abhii + 0 comments [deleted]99abhii + 0 comments [deleted]abieleck + 0 comments Instead of keeping track of the number of purchases, one can just multiply each price by j / k + 1, where j / k is in integer arithmetic. j is the purchase number, starting from 0 for the first purchase.

aburduk + 0 comments What the others said, except you need to sort descending and iterate forwards in order for it to work.

nikolicav + 0 comments C# solution with Dictionary, Pass 100%.

public int getMinimumCost(int k, int[] c) { Array.Sort(c); IDictionary<int, int> dict = new Dictionary<int, int>(); int sum = 0; // first sell most expensive flower to each person for (int i = c.Length - 1; i >= c.Length - k; i--) sum += c[i]; // current person int current = 0; for (int i = c.Length - k; i > 0; i--) { // counter how many flowers every person // alredy bought if (dict.ContainsKey(current)) dict[current] += 1; else dict.Add(current, 1); // calculate sum with current price and count of // flower current person already bought sum += (dict[current] + 1) * c[i - 1]; // move to next person current++; // if all persons bought same number of flowers // reset current person to first if (current == k) current = 0; } return sum; }

Chevy_Li + 0 comments Easy to understand code. Thanks!

muthangyamusyoka + 0 comments Yap, also finding it very ambigous.

gurunars + 0 comments Yes. It is very badly written.

hamid_mayeli + 0 comments Also, it the samples the prices are sorted but in testcases not. So consider sorting them.

martindevillers + 0 comments Thank god this is the top comment. If this was an actual coding interview this would be the part where they throw incomprehensible requirements at you and you have to parry them with lots of "What do you mean with ..." questions

pamirghimire + 0 comments Thanks for the explanation. My implementation followed from this naturally. The greedy question I asked was : "Which member of the group can make the next most expensive purchase most cheaply".

ailhahc + 4 comments The problem statement is wrong. In problem statement it's written More precisely, if a customer has already bought x flowers, he should pay (x+1)/ci dollars to buy flower number i.

It should be he should pay (x+1)*ci

sagioto + 0 comments Why is this not being corrected?

rgevorky + 0 comments The problem is also just written poorly, like MANY others on this website. The author writes of flower number i, where he/she presumably means flower type i, since we also have N, the number of flowers we want to buy. The problem further does not state the implicit assumption that the group can buy any N flowers (type doesn't matter).

vikasgandhi003 + 0 comments YEAH YEAH I AGREE WITH THAT

andepzaifggg + 0 comments haha

phillm6 + 4 comments Just to clarify, as some people seem to be having a few problems. If Anne and Bob go to buy flowers [1,2,7,9,100], then the minimum price is 130. Why?

Assume only one person buys the flowers in the given order. So, she pays (1)1+(2)2+(3)7+(4)9+(5)100 = 562. From this we can see that order matters; for example, if she buys them in the opposite order, we get (1)100+(2)9+(3)7+(4)2+(5)1 = 152! Even without a second person, we can see that an opportunistic order drastically improves the price.

So, hopefully without giving the problem away, what we would want to do is assign the flowers to Anne and Bob in such a way not only to reduce the total number each person purchases [so that no person will buy an ith flower larger than is necessary (so that their ith multiplyer will be no larger than is necessary for any given flower)], but to assign the order they buy their flowers responsibly as well.

Note: the oder of the*people*does not affect the price, only the order of flowers purchased by each person.dalmia_anmol + 1 comment Hello. Could you show the distribution of purchases that results into 130 cost?

phillm6 + 4 comments A purchases (1)100 + (2)7 + (3)1 = 100 + 14 + 3 = 117

B purchases (1)9 + (2)2 = 9 + 4 = 13

P(A) + P(B) = 130 (this is one possible distribution)

Remember that we have

*two*people, so we can repeat coefficients up to*two*times each. We can therefore construct any permutation of the list [1,1,2,2,3] to multiply elementwise with the prices. It's simply a matter of choosing the most advantageous order to purchase.dalmia_anmol + 1 comment Ok, thanks. But I am unable to understand then how Greedy comes into the picture.

phillm6 + 3 comments Well, what are we doing, and is what we're doing greedy?

Because the coefficients are constantly increasing (at a rate of 1 per k purchases), we purchase the most expensive flowers first in order to minimize cost, rotating people to hold coefficients down as long as possible.

Assuming this rotation of customers, the algorithm

*optimizeses at each step*by choosing to purchase the most expensive remaining flower.Recall that this is the definition of a greedy algorithm.

dalmia_anmol + 0 comments Kudos. Apologies for not observing the rotation part. Thanks for the help.

beezerbtt + 0 comments Thats the answer basically.

azaystudy + 0 comments I think this is the most helpful comment. I was not able to understand the problem until I read this comment. As soon as I read this comment, I solved the problem pretty quickly.

sheelnidhi + 1 comment Hi,I am unable to understand how the distribution works?If there is two friends and they have to buy total 3 flowers then who will buy two.Someone can buy only single flower.

phillm6 + 3 comments It doesn't really matter.

Call the flowers [3,2,1]. A or B takes the most expensive flower, say A for argument. A pays (1)3 = 3. Now the next most expensive flower could be purchased by A or B. If A purchases it, it will cost (2)2 = 4, but if B does it will cost (1)2 = 2, so B should purchase.Now we need to buy the 1 flower, and both A and B have a coefficient of 2 now, so it doesn't matter who does. (You don't even have to keep track of people to solve the problem!)

dont_know_me + 0 comments thank you so much.. I got the solution only after reading this.

lalithnani + 0 comments thanks

da182 + 0 comments Thanks for such a concise explanation!

Akshita_Sood + 0 comments thanks a lot.this was helpful.

simonsatoshi + 0 comments Thank you! 15 minutes to understand the question. 2 minutes to code it.

shshnk28 + 0 comments Now this is a nice description. It made understanding the problem easier.

rwan7727 + 1 comment `int n; int k; cin >> n >> k; vector <int> c(n); for(int i=0;i<n;i++) cin >> c[i]; vector <int> p(k); // stores how many times a person has bought flowers int pIndex=0; int minCost=0; sort(c.begin(),c.end()); // rotate people to buy from the costliest to the cheapest flowers for (int i=c.size()-1;i>=0;i--) { minCost+=(p[pIndex]+1)*c[i]; p[pIndex]++; // goto next guy pIndex++; if (pIndex>=k) pIndex=0; } cout << minCost << endl;`

jnordwick + 5 comments Not even that complex:

int main() { int n, k; cin >> n >> k; vector<int> v(n); for(int i = 0; i < n; ++i) cin >> v[i]; sort(v.begin(), v.end()); reverse(v.begin(), v.end()); int tot = 0; for(int i = 0; i < n; ++i) { tot += ((i / k) + 1) * v[i]; } cout << tot << endl; return 0; }

fynx_gloire + 1 comment Hello can you explain your code for the Greedy Florist here: m = floor(i/K)+1;

Why are you dividing the i by number of customers?

veden_joshua + 0 comments they divide i by k in order to figure out the number of flowers the person has purchased before purchasing the ith flower. For example, if there are 3 friends (k = 3) purchasing from 5 flowers (n = 5), then on the 3rd iteration (i = 2) this person will be purchasing their first flower (2/3 + 1 = 1),. This can be thought of as the 3rd friend purchasing their first flower. On the fourth iteration (i = 3), this person will be purchasing their second flower (3/3 + 1 = 2). This can be thought of as the 1st friend purchasing their second flower. Hope this helps.

rams_m02 + 0 comments so simple and elgant. thanks!

satyamskillz + 0 comments `def getMinimumCost(k, c): c.sort(reverse=True) l=len(c) t=0 for i in range(l): t=t+(int(i/k)+1)*c[i] return t`

This can become more simple in python

rafat_joy0707 + 0 comments gives wrong answer .

soheshdoshi + 0 comments Grt Man

Aakash8250 + 0 comments its simple brother, first buy=100(1)+9(1) second buy=7(2)+2(2) third buy=1(2) add all = 130

sheldonrong + 7 comments def getMinimumCost(n, k, c): cost = 0 c = sorted(c, reverse=True) for i in range(0, n): cost += (i // k + 1) * c[i] return cost

metazilla + 1 comment Nice, here's a one-liner based off your solution:

def getMinimumCost(k, c): return sum([cost * ((i // k) + 1) for i, cost in enumerate(sorted(c, reverse=True))])

it_henrik + 1 comment I would recommend to skip the listcomprehension and go for a generator expression instead to save some time and memory:

def getMinimumCost(k, c): return sum((v * (i // k + 1) for i, v in enumerate(sorted(c, reverse=True))))

or for readability:

def getMinimumCost(k, c): c.sort(reverse=True) return sum((v * (i // k + 1) for i, v in enumerate(c)))

qayum_khan_usa + 0 comments Both the one-line

**Python3**solutions of`metazilla`

and`it_henrik`

are beautiful. My independent**two-liner**also doesn't assume that`c`

is sorted. My code's advantages:- no use of
`enumerate`

(and indeed a generator is used in the outer sum) - roughly
`n//k * 3`

multiplications/divisions versus`n * 2`

.

def getMinimumCost(k, c): c.sort(reverse=True) ; n = len(c) return sum(r*sum(c[(r-1)*k:r*k]) for r in range(1,(n-1)//k+2))

If one wanted to get it down to

`n//k`

multiplications, one would insert a line that creates a memo-ization array of the start/stop indices`r*k`

from`0`

to`n`

by incrementing by`k`

.- no use of

angelopolotto + 0 comments Less pythonic but my solution work too:

`def getMinimumCost(k, c): c_len = len(c) total = sum(c) if k >= c_len: return total c_s = sorted(c, reverse=True) total = sum(c_s[:k]) c_diff = c_s[k:] i = 1 j = 1 for c_i in c_diff: total += c_i * (1 + i) if j < k: j += 1 else: i += 1 j = 1 return total`

hacker_jkjffjha + 0 comments javascript 1-liner implementation:

function getMinimumCost(k, c) { return c.sort((a, b) => b - a).reduce((acc, cost, index) => acc + (parseInt(index / k) + 1) * cost, 0) }

pamuditha_i + 0 comments Nice!

switchoffking + 0 comments [deleted]switchoffking + 0 comments [deleted]josiahtpz + 0 comments What's the reason behind i//k ? How does it link to number of previously bought flowers

renolu + 1 comment Simple Java approach by buying the flowers backward from the most expensive to least expensive:

import java.io.*; import java.util.*; public class Solution { public static void main(String[] args) { /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */ Scanner s = new Scanner(System.in); int n = s.nextInt(); int k = s.nextInt(); int[] flowers = new int[n]; for(int i=0;i<n;i++){ flowers[i]=s.nextInt(); } System.out.println(CalculateMinPrice(flowers,k)); } static int CalculateMinPrice(int[] flowers,int k){ //sort all flower prices in ascending order Arrays.sort(flowers); int i = flowers.length-1; int bought = 0; int total=0; //start backwards from the most expensive flower, stop when there is no more flowers left while(i>=0){ //Calculate total //increment bought by 1 when everyone in the group has bought equal number of flowers for(int j=0;j<k && i>=0;j++){ total+=(1+bought)*flowers[i]; i--; } bought++; } return total; } }

ray10mathew + 1 comment I feel so stupid looking at your solution. Took me ages to try and come up with a logic.

saisuneela24 + 0 comments hoo really

Sort 365 Discussions, By:

Please Login in order to post a comment