EKOSPOJ

The problem, simply

You get the heights of n trees in a row and a number M, the meters of wood you need. A long saw blade is set at height H and sweeps over the whole row. Every tree taller than H loses its top part, and you keep those tops. Trees shorter than H are not touched.

Find the highest whole number H that still gives you at least M meters of wood. A higher blade is kinder to the forest.

A story to remember it

Picture it

Examples

Way 1: the simple way

Start the blade at the top of the tallest tree, where it cuts nothing. Lower it one meter at a time. Each time, add up the tops. Stop at the first height that gives enough wood.

1. H starts at the tallest height.
2. Wood at H is the sum of tree - H over trees taller than H.
3. If the wood is at least M, answer H. Otherwise lower H by one.

class Solution {
    long woodAt(int[] trees, int h) {
        long wood = 0;
        for (int t : trees) {
            if (t > h) wood += t - h;   // only the part above the blade
        }
        return wood;
    }

    public int highestBlade(int[] trees, long need) {
        int top = 0;
        for (int t : trees) top = Math.max(top, t);
        for (int h = top; h >= 0; h--) {
            if (woodAt(trees, h) >= need) return h;   // first one from the top
        }
        return 0;
    }
}

How long it takes: trees can be a billion meters tall, and each height costs a walk over all n trees: O(n * max). Extra room: O(1).

Way 2: the clever way

Raising the blade never gives more wood. So the heights line up as yes, yes, yes, no, no: low blades give enough, high blades do not. We want the last yes. That is a job for binary search on the answer.

1. lo = 0, hi = the tallest tree.
2. Try mid. Add up the wood.
3. Enough wood: remember mid, then try higher with lo = mid + 1.
4. Not enough: try lower with hi = mid - 1.
5. When lo passes hi, the remembered height is the answer.

The bottom row in the animation lists every blade height. Heights marked done give enough wood, heights marked rejected are too high.

class Solution {
    long woodAt(int[] trees, long h) {
        long wood = 0;
        for (int t : trees) {
            if (t > h) wood += t - h;
        }
        return wood;
    }

    public long highestBlade(int[] trees, long need) {
        long lo = 0, hi = 0;
        for (int t : trees) hi = Math.max(hi, t);
        long best = 0;
        while (lo <= hi) {
            long mid = lo + (hi - lo) / 2;
            if (woodAt(trees, mid) >= need) {
                best = mid;          // enough wood, try a higher blade
                lo = mid + 1;
            } else {
                hi = mid - 1;        // not enough, go lower
            }
        }
        return best;
    }
}

How long it takes: about log(max) guesses (30 for a billion), each walking all trees once: O(n log max). Extra room: O(1).

Watch out for

• Adding tree - H for short trees too. A tree shorter than the blade gives 0, not a negative number.
• Moving the wrong pointer. Enough wood means the blade can go higher, so lo moves up.
• The problem promises the answer exists (the total wood is at least M). If not, decide what to return before you search.
• Reading a million numbers with a slow scanner times out on SPOJ. Use a fast reader.

What interviewers ask next

• Can you avoid scanning every tree for every guess? Sort the trees and build prefix sums. Then the wood at height H is (sum of trees taller than H) minus H times (how many there are), found with one binary search. Each guess costs O(log n).
• Even better: after sorting, walk down from the tallest tree and find the stretch where the answer lands, then solve for H with one division. That is O(n log n) for the sort and O(n) after.
• Same pattern elsewhere: "Koko eating bananas" (lowest speed that finishes in time) and "minimum days to make bouquets" are this exact search with a different check.
• What if heights are real numbers? Binary search on a double for a fixed number of rounds.

Remember this

Grown-up words: the guessing game is binary search on the answer, "higher means less wood" is a monotonic function, adding up the tops is the feasibility check, and the total that might not fit is integer overflow.