Massive Algorithms: Infinite house of pancakes - Google Codejam 2015 Qualification round problem 2

Problem solving with programming: Infinite house of pancakes - Google Codejam 2015 Qualification round problem 2
https://code.google.com/codejam/contest/6224486/dashboard#s=p1

There is a dinner house of infinite number of guests but finite number of pancakes. Each of them hold a plate which is either empty or has some pancakes in them. Every minute, one of the following actions can happen.

Each guest eats one pancake per minute.
The server will declare it as a special minute during which all guests stop eating, and the server will choose a guest with non-zero pancakes and transfer some cakes from that guest to the another guest.

The problem is to optimize the number of special minutes so that the total time to finish all the cakes is minimum.

T test cases follow. Each consists of one line with D, the number of diners with non-empty plates, followed by another line with D space-separated integers representing the numbers of pancakes on those diners' plates.

1 ≤ D ≤ 1000.
1 ≤ P_i ≤ 1000.

[1, 2, 4] - If we don't declare any special minutes, all the cakes will be finished in 4 minutes which is the maximum cakes.

What is we declare a special minute and take out 2 cakes from the 3rd guest and keep it in an empty plate?

[1,2,2,2] - Now we can finish all the cakes in 2 minutes + 1 special minute. So we can finish all the cakes in 3 minutes itself.

Note that we can not reduce the time any further because if we do so, we have to declare 3 special minutes (for moving one cake from each of the plate with 2 cakes) which outweigh the actual eating time which is 2 minutes.

A simple brute force algorithm would suffice because the restriction on the input is small (1000).

Let us calculate the frequency of pancakes in each plate.

For each of the sizes between 1 and 1000

Move the excess cakes (p[i] - size) in each plate to an empty plate and sum up the number of moves required.

Add the size to the number of moves, you will get the time required to finish.

Update the minimum time.


  for( j = 0; j < d; j++ )


   cin >> cakes[j];


 


  cout << "Case #" << i+1 << ": " << min_time(cakes) << endl;


int min_time(const vector<int>& cakes)


{


 vector<int> counts(1001);


 int i,j;


 //calculate the frequencies of each number


 for( i = 0; i < cakes.size(); i++ )


 {


  counts[cakes[i]]++;


 }


 


 int mintime = INT_MAX;


 for( i = 1; i < 1001; i++ )


 {


  int moves = 0;


  for( j = 1; j < 1001; j++ )


  {


   //moves required to divide the cakes into groups of size i


   moves += (j-1)/i * counts[j];


  }


  //Keep track of the minimum time


  mintime = min( mintime, moves+i ); //moves: special minutes, i: time to eat


 }


 return mintime;


}