Category Archives: google codejam

Infinite house of pancakes – Google Codejam 2015 Qualification round problem 2

Here is the link to the original problem. Let us try to simplify the problem statement a little bit.

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.
  1. Each guest eats one pancake per minute.
  2. 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.

We are given the number of pancakes on each plate initially.

Let us walk through a small example.
[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.

Without the loss of generality we assume that we can minimize the number of pancakes to be eaten by moving them from the maximum plate to a zero plate.

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.
Let us trace the algorithm for the above example.
[1,2,4]
  • Divide them into size 1 chunks – [1,1,1,1,1,1,1] – 4 moves+ 1 = 5 minutes.
  • Divide them into size 2 chunks – [1,2,2] – 1 move + 2 = 3 minutes
  • Divide them into size 3 chunks – [1,2,3,1] – 1 move + 3 = 4 minutes
The minimum among them is 3 minutes. For simplicity I have not shown the division for size greater than 3. Even if we calculate they return the same output of 4.

The maximum time it takes for any combination is the maximum number of cakes in any plate.

Here is the C++ implementation of the same. 
Note: I did not solve this problem in the competition. But I got inspired by the solutions (user: kyc) who successfully solved the problem. I only composed the solution analysis. If somebody has a better solution, please feel free to post it in a comment.

Standing Ovation: Google codejam 2015 Qualification round problem

Every year Google conducts a competition called Codejam for programming enthusiasts. The qualification round for the year 2015 got finished yesterday. In this post, I am going to explain the solution approach for the first problem.

You can read the problem from this link. I will try to give the abridged problem statement below.

There are a group of N people in a stadium with their shyness levels represented by a String S of digits(0-9). The digit at each index represents the number of persons with shyness level equal to the index.

For example S[0] represents the number persons with shyness ‘0’.
S[1] represent the number of persons with shyness ‘1’ and so on.

Persons with shyness level ‘L’ will not standup and clap until ‘L’ other people standup and clap before them. For example, in order for a person with shyness level 3 to standup and clap, 3 other people must do that before him. 

Now the problem is to find whether the all the people in the given group gives a standing ovation on its own? or What is the minimum number of people to add to the group to ensure that they give a standing ovation.

Let us consider a couple of simple examples.

  1. [1, 1, 2]: There is one person with shyness level 0 who will clap first. After seeing him, the second person with shyness 1 will also clap. Then the last two people with shyness 2 will also clap. So there is no need to add any people to give a standing ovation.
  2. [1, 0, 1]: In this case, we need one person with shyness 0 or 1 to be added to the group because the last person will not standup until 2 other people clap.

A simple greedy approach will solve the problem. Here is the algorithm.

Start at the first person and count the number of people stood up before him. If this count is not enough for the current person to standup, count the difference needed.  Accordingly increment the people currently standing.

Here is the C++ implementation of the above approach. This runs in O(n) time.