Category Archives: greedy

Billing algorithm

This problem is from Codechef. I am re-wording it for more clarity.

A garments shop has “Buy 2, Get 2” offer for it’s customers. Whatever the items may be, they charge for costliest items from an order and give the cheapest ones free.
However we can divide the items into multiple orders to save more.

For example, Let us say we have 6 items with prices 200, 600, 100, 900, 800, 700. If we take them as one order, we will have to pay 3000.

6 items are divided into two groups {900,800,200,100}, {700,600} because they charge for highest price items. So the total bill would be 900+800+700+600 = 3000
Suppose we divide the items into two groups {900,800,700,600}, {200,100} we need to pay only 900+800+200+100 = 2000

Now the problem is, given a list of prices, how do we calculate the minimum amount we need to pay?

This is a simple greedy algorithm. We just need to sort all the prices in descending order and group them into 4 per order. The last order might contain less than 4 items.

Here is the C++ code for the same

Minimum number of jumps to reach top

There are N steps in a staircase, and a person can jump 5 steps at max, i.e he can jump any number of steps between 1 and 5.
What is the minumum number of jumps he has to make to reach the top?

A simple math problem which can be solved using a simple greedy approach. Try to make as many maximum jumps as possible before reaching the top. Take a smaller jump if needed at the end.

For example if there are 10 steps, he can make two maximum jumps of 5 steps each to reach the top.
If there 8 steps, First he can jump 5 steps and then jump 3 steps. So within 2 jumps, he can reach the top.

The code for this very simple. This problem can also be generalized by customizing the jump capacity to any number instead of a fixed number 5.

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

int main()
{
int loc;
scanf("%d", &loc);
printf("%d\n",loc/5 + (loc%5 == 0?0:1));
return 0;
}

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.


Minimum number after removing K digits

Given a number N, and a number K, find the minimum number that can be formed by deleting K digits. The order of the digits should not be changed.

For example consider N = 234987, K = 2, we can remove 9,8 and the resulting number is 2347.

The solution is based on the following observation, consider the above case. 

Let us delete a digit from 234987
Deleted Digit – Result
—————————
2             – 34987
3             – 24987
4             – 23987
9             – 23487
8             – 23497
7             – 23498
If we remove 9 we will get the minimum number. Observe that in the given number, 9 is the first digit which is greater than the next digit.

What if all the digits are in ascending order? 

Let us walk through an example.
N = 12345, K = 3. If we remove 4,5 we will get the minimum number. The observation is that we need to keep on removing right-most digits in this case.

[This is a re-post after correcting my incorrect approach. Thanks to Jeff Senecal for pointing out the mistake.]

Here is the C++ implementation of the above approach.