Roti Prata SPOJ Problem Solution | Binary Search

Hey everyone! Today we are going to discuss one of the most popular problems of binary search which is the Roti Prata SPOJ problem. We will discuss the Roti Prata SPOJ problem solution, its explanation, solution approach, and then C++ and Java code. There are many problems based on this particular pattern of binary search known as modified binary search or advanced binary search. Many product-based companies like Google, Microsoft, and Uber ask these types of problems in their coding round or online assessment tests. Let’s quickly jump to the problem.

Roti-Prata SPOJ problem statement
Problem Explanation
Roti Prata SPOJ Solution Approach
C++ Solution of Roti Prata SPOJ Problem
Java Solution of Roti Prata SPOJ Problem

Roti Prata SPOJ Problem Statement

There is an Independence day function at Harry’s school. The principal asked to serve prata after the event is done. The teachers and staff members are asked to go to a restaurant and get P (P<=1000) pratas packed for the Independence day function. The food stall has L chefs (L<=50) and each chef has a rank R (1<=R<=8). A chef with a rank R can cook 1 prata in the first R minutes 1 more prata in the next 2R minutes, 1 more prata in 3R minutes, and so on. A chef can only cook a complete prata and not partially.

For example, if a chef is ranked 2, he will cook one prata in 2 minutes then one more prata in the next 4 mins, and one more in the next 6 minutes hence in total 12 minutes he cooks 3 pratas. In 13 minutes also he can cook only 3 pratas as he does not have enough time for the 4th prata. Since the event at school is about to start so teachers are in hurry. The teachers and staff members want to know the minimum time to get the order done by the restaurant. Please write a program to help them out.

Input

The first line tells the number of test cases. Each test case consists of 2 lines. In the first line of the test case, we have P the number of prata ordered by the teachers. In the next line, the first integer denotes the number of chefs L and L integers follow in the same line each denoting the rank of a cook.

Output

Print an integer that tells the number of minutes needed to get the order done.

Example

Input:
3
10
4 1 2 3 4
8
1 1
8
8 1 1 1 1 1 1 1 1

Output:
12
36
1

Roti Prata SPOJ Problem Explanation

Whoof…Huge problem statement right? It’s ok if you did not understand anything in the given problem statement. Let me explain this problem in simple language. We are given L number of chefs. Each chef has some rank R, which will tell how much time the chef will take to make 1st prata or paratha. Then for making the 2nd prata, he will take 2R time, for the 3rd prata he will take 3R time, and so on.

This means that if a chef has rank 2 then he will make 1st prata in 2 minutes. Then 2nd prata in 4 minutes. That means he will take 6 minutes (2 + 2*2) to make 2 pratas. For making 3 pratas he will take 2 + 2*2 + 3*2 = 12 minutes, for making 4 pratas he will take 2 + 2*2 + 3*2 + 4*2 = 20 minutes and so on.

Now we’re given the order of making P number of pratas and we have to tell the minimum number of minutes to complete the order. I hope now you’re clear with the problem statement. You just need to tell the “minimum” number of minutes to complete the order of P pratas. You need to “minimize” the time taken by the chefs to complete the order of pratas.

Let’s see one example test case.

P = 10

L = 4

R[ ] = 1 2 3 4

We have an order of 10 pratas. We have 4 chefs. Their ranks are 1, 2, 3, and 4. Its output is 12 minutes. Why 12 minutes? Why not 15 minutes? Why not 11 minutes?

Chefs would definitely complete the order of 12 minutes in 15 minutes. No need to check. They can’t complete an order of 10 pratas in 11 minutes. Let’s see why.

Chef 1 has rank 1

How many pratas he will make in 11 minutes? The general equation would be:

R + 2R + 3R … nR <= X minutes
R (1+2+3+…n) <= X (Taking R common)
R[ (n * (n+1)) / 2 ] <= X
(n * (n+1)) <= 2*X / R
Putting X = 11, R=1
n * (n+1) <= 2*11
n * (n+1) <= 22

Therefore chef 1 would make 4 pratas in 11 minutes. Notice that he will make 4 pratas in 10 minutes only but since we’re not counting partial prata in 11 minutes also he will make 4 pratas only.

Chef 2 has rank 2

(n * (n+1)) <= 2*X / R
X = 11, R = 2
(n * (n+1)) <= 11

Therefore chef 2 would make 2 pratas in 11 minutes.

Chef 1 and Chef 2 together will make 6 pratas in 11 minutes. 4 made by chef 1 and 2 made by chef 2.

Chef 3 has rank 3

(n * (n+1)) <= 2*X / R –> n * (n+1) <= 7 –> n = 2

Therefore chef 3 would make 2 pratas in 11 minutes. Now in total, we have 8 pratas.

Chef 4 has rank 4

(n * (n+1)) <= 2*X / R –> n * (n+1) <= 5 –> n = 1.

In this way, 4 chefs will be able to make only 9 pratas in 11 minutes. That means 11 minutes are less to complete the order of 10 pratas.

Roti Prata SPOJ Problem Solution Approach

Now how we can solve this problem? You have to make P pratas using given Chefs with minimum time. Now, whenever we have to minimize something and we have a particular condition to fulfill we think of binary search. To apply a Binary search we need to decide 3 things.

The range on which we will apply the binary search. That is the value of low and high.
How we will decide in which direction we will find our answer?
The validation criteria. If we’re at mid then how we will know if is this our answer or do we’ve to search further?

But before that, it’s important to understand why we’re applying binary search here. Think of it in this way. We have a range i.e, solution search space. We don’t know the exact minimum time. But we have a range in which our answer will lie. Suppose we have a chef with a rank equal to P. He will make P pratas in 1 minute. Therefore, to complete any order the minimum to minimum time could be 1 minute. And if we consider the worst case, at max it would be the maximum of rank[i] * ( P * (P+1) / 2). When we give the complete order to only 1 chef and it has rank = 1.

Now, the 1st step is done. Low = 1 and High = max(High, rank[i] * ( P * (P+1) / 2) ).

Roti Prata SPOJ Problem solution — Roti Prata SPOJ Problem

In the 2nd step, we need to decide on criteria that will tell whether mid is a valid answer or not. We have to check whether we can make P pratas in the mid number of minutes or not.

If yes, then we will store this mid in our answer variable and will move high to mid – 1. Why? What if our mid is 15 and our correct answer is 10? If we can make P pratas in 15 minutes, we will try to search a minimum then this. And therefore will move in the left direction.

If not, we will try to increase the time, therefore will move in the right direction and update low to mid + 1.

Step 2 is done. If we’re at mid and this is a valid answer then we will store this mid in our answer variable and try to find a better solution in the left direction otherwise will go to the right.

Now, the question arises how do we check if time = mid is a valid answer or not? For this, we have to write a valid function. We will calculate how many pratas the chefs can make in time = mid minutes. For each, we will calculate how many pratas they can make in the given time and then add them up. If this count is greater or equal to the required order P, then we will return true otherwise we’ll return false.

Step 3 is also done. We have to run a loop for all chefs. We will calculate how many pratas chef[i] will make in a given time. Sum them up and check if it is greater or equal to the required P pratas or not.

Now, let’s see the C++ solution to the roti prata SPOJ problem.

C++ Solution of Roti Prata SPOJ Problem

#include <bits/stdc++.h>
using namespace std;

bool valid(long long t, long long rank[], long long int P, int n)
{
	long long cp = 0, tt, val, count = 0;
	
	for(int i = 0; i < n; i++)
	{
		tt = rank[i];
		count = 0;
		val = 1;
		
		while(tt <= t)
		{
			count++;
			val++;
			tt += (val*rank[i]);
		}
		
		cp += count;
		
		if(cp >= P) return true;
	}
	return false;
}

int main() 
{
	long long t, P, n;
	cin >> t;
	while(t--)
	{
		cin >> P >> n;
	
		long long rank[n];
	
		for(int i = 0; i < n; i++)
			cin >> rank[i];
		
		long long low = 1, high = INT_MIN;
	
		for(int i = 0; i < n; i++)
			high = max(high, rank[i]*(P*(P+1)/2));
	
		long long ans = 0;
		
		while(low <= high)
		{
			long long mid = low + (high -low)/2;
			
			if(valid(mid, rank, P, n))
			{
				ans = mid;
				high = mid-1;
			}
			else 
				low = mid + 1;
		}
	
		cout << ans << endl;
	}
	
	return 0;
}

Java Solution of Roti Prata SPOJ Problem

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();
		
		while(t > 0)
		{
			int P = sc.nextInt();
			int n = sc.nextInt();
			int[] rank = new int[n];
			for (int i = 0; i < rank.length; i++) {
			rank[i] = sc.nextInt();
			}
			
			System.out.println(parathaSpoj(rank, P)) ;
			t--;
		}
		
	}

static boolean isvalid(int[] arr, int P, int mid) {
	int time = 0;
	int cp = 0;
	for (int i = 0; i < arr.length; i++) {
	time = arr[i];
	int j = 2;
	while (time <= mid) {
		cp++;
		time = time + (arr[i] * j);
		j++;
	}
	if (cp >= P) 
		return true;
	}
	
	return false;
}

static int parathaSpoj(int[] arr, int paratha) {
	
		int ans = -1;
		int low = 0, high = Integer.MAX_VALUE;
		
		while (low <= high) {
			
			int mid = low + (high - low) / 2;
			
			if (isvalid(arr, paratha, mid)) {
				ans = mid;
				high = mid - 1;
			} else {
				low = mid + 1;
			}
		}
		return ans;
	}
}

If you want us to add more coding questions kindly tell us in the comments. Don’t forget to share it with your friends. Thanks 🙂

Also Read:

Roti Prata SPOJ Problem Solution – Complete Solution Approach with C++ and Java Code

Table of Contents