We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
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.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Greedy Florist
You are viewing a single comment's thread. Return to all 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.