Friday 15 June 2012

InterviewStreet Flowers Challenge Solution : C++


InterviewStreet Flowers Challenge


Problem Statement


There are k friends who want to buy N flowers. Each flower has some cost ci. But there is condition that the price of flowers changes for customer who had bought flowers before. More precisely if a customer has already bought x flowers, he should pay (x+1)*ci dollars to buy flower number i. What is the minimum amount you have to pay to buy all N flowers?

Ex Input :                                       Output :
      3 3                                              13
      2 5 6


So first line contains n and k and next line contain ci, cost of ith flower.



Algorithm

1) Arrange all the cost in an increasing sequence...d1,d2..dn
2) Allot from end nth flower to friend 1, n-1 flower to friend 2 and so on..until k after which cost factor would be 2 and hence flower n-k would cost 2*d(n-k) to friend 1 and n-k-1 flower will cost 2*d(n-k-1) to friend 2 and so on until all flowers are bought by somebody.

If you have a different approach in mind, please share it in comments section.


Solution

#include<iostream>
#include<set>
using namespace std;


int main()
{
int n,k;
cin >> n >> k;
if(k > n) k=n;
int i,x;
multiset<int> s;
multiset<int>::iterator it;
for(i=0;i<n;i++) {
    cin >> x;
    s.insert(x);
}

//start calculating cost
int factor = 0;
unsigned long long int cost=0;
int count = 0;
it = s.end(); it--;
while(count!=n)
{
    if(count%k==0) factor+=1;
    cost+=(*it * factor);
    it--;
    count++;
}
cout << cost << endl;
cin >> cost;
}


Time Complexity

O(nlogn) to sort n cost numbers and O(n) to calculate the cost.
O(n+nlogn) => O(nlogn)
Hence time complexity will be O(nlogn)

1 comment:

  1. Question is not clear...please elaborate the connection of friends with output

    ReplyDelete