EKOSPOJ

Problem Statement

Lumberjack Mirko needs to cut at least M meters of wood. He uses a sawmill that cuts trees at a specific height H. When the blade passes through a forest of N trees, all trees taller than H are cut at height H, and the parts above H are collected. Trees shorter than or equal to H remain intact.

Given the heights of N trees and the required wood M, find the maximum integer height H such that at least M meters of wood is collected.

Constraints:

• 1 ≤ N ≤ 10^6
• 1 ≤ M ≤ 2 × 10^9
• 1 ≤ height[i] ≤ 10^9

Example:

• Input: heights = [20, 15, 10, 17], M = 7
• Output: 15
• Explanation: At H=15: (20-15) + (17-15) = 5 + 2 = 7 meters. At H=16: only 20-16 = 4 meters (not enough).

Example 2:

• Input: heights = [4, 42, 40, 26, 46], M = 20
• Output: 36
• Explanation: At H=36: (42-36) + (40-36) + (46-36) = 6 + 4 + 10 = 20 meters

Approach 1: Brute Force (Linear Search)

Intuition

Try all possible heights from max(heights) down to 0 and find the first height that gives at least M meters of wood.

Algorithm

1. Start from maximum tree height
2. For each height H, calculate total wood collected
3. Return the first H where wood >= M

import java.util.*;

public class Solution {
    private long calculateWood(int[] heights, int H) {
        long wood = 0;
        for (int h : heights) {
            if (h > H) {
                wood += (h - H);
            }
        }
        return wood;
    }
    
    public int findMaxHeight(int[] heights, long M) {
        int maxH = 0;
        for (int h : heights) {
            maxH = Math.max(maxH, h);
        }
        
        for (int H = maxH; H >= 0; H--) {
            if (calculateWood(heights, H) >= M) {
                return H;
            }
        }
        
        return 0;
    }
}

Complexity Analysis

• Time Complexity: O(n × max(heights)) - For each height, we scan all trees
• Space Complexity: O(1) - Only using variables

Approach 2: Binary Search on Answer (Optimal)

Intuition

The wood collected has a monotonic property: as H increases, wood collected decreases. This allows us to binary search on the height H to find the maximum H that gives at least M wood.

Key Observations:

1. H = 0: Maximum wood (sum of all heights)
2. H = max(heights): Zero wood
3. Higher H → Less wood (monotonic decreasing)
4. We want maximum H with wood >= M

Algorithm

1. Set low = 0, high = max(heights)
2. Binary search for maximum H where wood >= M
3. For each mid, calculate total wood and adjust search space
4. Track the maximum valid H

import java.util.*;

public class EKOSPOJ {
    private long calculateWood(int[] heights, long H) {
        long wood = 0;
        for (int h : heights) {
            if (h > H) {
                wood += (h - H);
            }
        }
        return wood;
    }
    
    public long findMaxHeight(int[] heights, long M) {
        long low = 0;
        long high = 0;
        
        for (int h : heights) {
            high = Math.max(high, h);
        }
        
        long result = 0;
        
        while (low <= high) {
            long mid = low + (high - low) / 2;
            long wood = calculateWood(heights, mid);
            
            if (wood >= M) {
                result = mid;
                low = mid + 1;  // Try higher H
            } else {
                high = mid - 1; // Need more wood, lower H
            }
        }
        
        return result;
    }
    
    public static void main(String[] args) {
        EKOSPOJ eko = new EKOSPOJ();
        int[] heights = {20, 15, 10, 17};
        System.out.println(eko.findMaxHeight(heights, 7));  // Output: 15
    }
}

Dry Run Example

Complexity Analysis

• Time Complexity: O(n log(max(heights)))
  • Binary search runs O(log(max(heights))) times
  • Each calculateWood takes O(n)
• Space Complexity: O(1) - Only using variables

Common Pitfalls

1. Integer Overflow

2. Checking Only Trees Above H

SPOJ Solution Template

Key Takeaways

1. Binary Search on Answer: When the answer has monotonic property, binary search on the answer space
2. Monotonic Function: As cutting height increases, wood collected decreases
3. Search for Maximum Valid: We want the maximum H that satisfies the constraint
4. Integer Overflow: Use long long for accumulating wood amounts
5. Greedy Check: Simple O(n) pass to verify if a height works
6. Problem Pattern: "Maximize X such that constraint Y is satisfied" → Binary Search
7. SPOJ Tip: Use fast I/O for competitive programming submissions