ROTI-Prata SPOJ

The problem, simply

A party needs P pratas (a flat bread). There are L cooks. A cook with rank R takes R minutes for the first prata, 2R more minutes for the second, 3R more for the third, and so on. So that cook finishes prata number k at minute R * (1 + 2 + ... + k) = R * k(k + 1)/2.

All cooks work at the same time. Give back the smallest number of minutes after which at least P pratas are ready.

A story to remember it

Picture it

Examples

Way 1: the simple way

Try minute 1, minute 2, minute 3, and so on. For each minute, count how many pratas all cooks can finish by then. Stop at the first minute that gives at least P.

1. count(T): for each cook, keep making pratas while the next one is finished by minute T. Add up the pratas, and stop early once you reach P.
2. Try T = 1, 2, 3, ... until count(T) >= P.

class Solution {
    public long minTime(int P, int[] ranks) {
        long T = 1;
        while (count(ranks, T, P) < P) T++;    // try every minute in order
        return T;
    }

    // how many pratas are ready by minute T (stops counting once it reaches P)
    long count(int[] ranks, long T, int P) {
        long total = 0;
        for (int r : ranks) {
            long time = 0;
            for (int k = 1; time + (long) r * k <= T; k++) {
                time += (long) r * k;          // this cook finishes prata k
                total++;
                if (total >= P) return total;
            }
        }
        return total;
    }
}

How long it takes: if the answer is T, we try T minutes, and each count costs at most L + P steps, so O(T * (L + P)). The answer can be in the millions. Extra room: O(1).

Way 2: the clever way

The count only grows as time grows. So binary search the time.

1. lo = 1.
2. hi = the time for the fastest cook to make all P pratas alone: minRank * P(P + 1)/2. That is surely enough.
3. Take mid. If count(mid) >= P, then mid is enough: remember it and try smaller, hi = mid - 1. Otherwise try bigger, lo = mid + 1.

class Solution {
    public long minTime(int P, int[] ranks) {
        int best = Integer.MAX_VALUE;
        for (int r : ranks) best = Math.min(best, r);
        long lo = 1, hi = (long) best * P * (P + 1) / 2;   // fastest cook alone
        long answer = hi;
        while (lo <= hi) {
            long mid = lo + (hi - lo) / 2;
            if (count(ranks, mid, P) >= P) {
                answer = mid;          // enough pratas: try less time
                hi = mid - 1;
            } else {
                lo = mid + 1;          // not enough: wait longer
            }
        }
        return answer;
    }

    long count(int[] ranks, long T, int P) {
        long total = 0;
        for (int r : ranks) {
            long time = 0;
            for (int k = 1; time + (long) r * k <= T; k++) {
                time += (long) r * k;
                total++;
                if (total >= P) return total;   // no need to count further
            }
        }
        return total;
    }
}

How long it takes: hi is at most about 8 * 1000 * 1001 / 2, about 4 million, so about 22 guesses. Each count costs at most L + P steps. In all O((L + P) log T). Extra room: O(1).

Watch out for

• R * k(k + 1)/2 overflows int quickly for big inputs. Use long.
• Counting with the square root formula k = (sqrt(1 + 8T/R) - 1)/2 is faster but rounding can be off by one. If you use it, fix it with a small while check afterwards.
• Stop counting once you reach P. It keeps each check short.
• answer should start at hi, which is known to work.

What interviewers ask next

• Koko eating bananas, minimum speed to arrive on time, and ship packages within D days are the same pattern: a yes/no check that only flips once, so binary search the answer.
• Could a heap solve it? Yes. Put every cook's next finishing time into a min heap, pop P times, and push that cook's following finishing time. That is O(P log L), and here it is just as good.
• What if each cook has a cooldown after every prata? The check changes, the search stays the same.
• Why is the search range log T and not log P? We search over minutes, not over pratas, so the size of the time range is what counts.

Remember this

Grown-up words: the count only going up is monotonicity, guessing the minute is binary search on the answer, and the cook's finishing time R * k(k + 1)/2 is a triangular number times the rank.