ROTI-Prata SPOJ

Problem Statement

IEEE wants to serve its members some delicious Indian food. A dish called "Prata" needs to be prepared. There are L cooks, each with a different cooking skill represented by a rank R. A cook with rank R can prepare:

• 1st prata in R minutes
• 2nd prata in 2R minutes
• 3rd prata in 3R minutes
• And so on...

Given the number of pratas P needed and the ranks of L cooks, find the minimum time required to prepare all P pratas.

Constraints:

• 1 ≤ P ≤ 1000
• 1 ≤ L ≤ 50
• 1 ≤ R ≤ 8

Example:

• Input: P = 10, ranks = [1, 2, 3, 4]
• Output: 12
• Explanation:
  • Cook 1 (rank 1): pratas in 1, 2, 3, 4 min (4 pratas in 1+2+3+4=10 min)
  • Cook 2 (rank 2): pratas in 2, 4 min (2 pratas in 2+4=6 min)
  • Cook 3 (rank 3): pratas in 3, 6 min (2 pratas in 3+6=9 min)
  • Cook 4 (rank 4): pratas in 4, 8 min (2 pratas in 4+8=12 min)
  • Total: 4+2+2+2 = 10 pratas in 12 minutes

Example 2:

• Input: P = 8, ranks = [1, 1]
• Output: 10
• Explanation: Each cook makes 4 pratas in 1+2+3+4=10 minutes

Background: Time for K Pratas

For a cook with rank R:

• Time for k pratas = R×(1 + 2 + ... + k) = R × k(k+1)/2

Given time T and rank R, max pratas a cook can make:

• Find largest k such that R × k(k+1)/2 ≤ T
• This can be solved using quadratic formula

Approach 1: Brute Force (Simulation)

Intuition

Simulate the cooking process minute by minute, assigning pratas to available cooks.

Algorithm

1. Start from time = 1
2. At each time, check how many total pratas can be made
3. Return first time where total pratas >= P

public class Solution {
    private int maxPratasInTime(int rank, int time) {
        double discriminant = 1 + 8.0 * time / rank;
        return (int)((-1 + Math.sqrt(discriminant)) / 2);
    }
    
    private int totalPratasInTime(int[] ranks, int time) {
        int total = 0;
        for (int rank : ranks) {
            total += maxPratasInTime(rank, time);
        }
        return total;
    }
    
    public int minTimeBrute(int P, int[] ranks) {
        int time = 1;
        
        while (totalPratasInTime(ranks, time) < P) {
            time++;
        }
        
        return time;
    }
}

Complexity Analysis

• Time Complexity: O(P × maxTime) - Linear search up to answer
• Space Complexity: O(L) - For ranks array

Approach 2: Binary Search on Time (Optimal)

Intuition

The total number of pratas that can be made is monotonically increasing with time. This allows binary search on the time.

Key Observations:

1. If we can make P pratas in time T, we can also make them in any time > T
2. Minimum time = 1 (theoretical lower bound)
3. Maximum time = when one cook makes all P pratas (worst case)
4. Binary search for minimum time where total pratas >= P

Algorithm

1. Calculate upper bound: time for worst cook to make all P pratas
2. Binary search on time in range [1, upperBound]
3. For each mid, calculate total pratas all cooks can make
4. If >= P, try smaller time; else, increase time

import java.util.*;

public class RotiPrata {
    private int maxPratasInTime(int rank, long time) {
        double discriminant = 1.0 + 8.0 * time / rank;
        return (int)((-1 + Math.sqrt(discriminant)) / 2);
    }
    
    private long totalPratasInTime(int[] ranks, long time) {
        long total = 0;
        for (int rank : ranks) {
            total += maxPratasInTime(rank, time);
        }
        return total;
    }
    
    private long timeForKPratas(int rank, int k) {
        return (long)rank * k * (k + 1) / 2;
    }
    
    public long minTime(int P, int[] ranks) {
        int maxRank = 0;
        for (int rank : ranks) {
            maxRank = Math.max(maxRank, rank);
        }
        
        long high = timeForKPratas(maxRank, P);
        long low = 1;
        long result = high;
        
        while (low <= high) {
            long mid = low + (high - low) / 2;
            
            if (totalPratasInTime(ranks, mid) >= P) {
                result = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        
        return result;
    }
    
    public static void main(String[] args) {
        RotiPrata rp = new RotiPrata();
        int[] ranks = {1, 2, 3, 4};
        System.out.println(rp.minTime(10, ranks));  // Output: 12
    }
}

Dry Run Example

Complexity Analysis

• Time Complexity: O(L × log(maxTime))
  • Binary search: O(log(maxTime)) iterations
  • Each iteration: O(L) to calculate total pratas
  • maxTime ≈ R_max × P × (P+1) / 2
• Space Complexity: O(L) - For ranks array

SPOJ Solution Template

Key Takeaways

1. Binary Search on Answer: Search for minimum time where condition is satisfied
2. Quadratic Time Formula: Time for k pratas = R × k(k+1)/2
3. Inverse Formula: Use quadratic formula to find max pratas in given time
4. Upper Bound: Worst cook making all pratas gives upper bound
5. Parallel Execution: All cooks work simultaneously
6. Monotonic Property: More time → More pratas (non-decreasing)
7. Similar Problems: Koko Eating Bananas, Capacity to Ship, Minimum Speed to Arrive