Lecture 65 :- EKO SPOJ

EKO is a classic problem on the Sphere Online Judge (SPOJ) platform. The problem is named "EKO - Eko" and is described as follows:

There are N trees in a row, each with a height represented by an integer. The heights of the trees are given in an array H. A lumberjack wants to cut the trees and needs a total of M meters of wood. The lumberjack follows these rules:

1. The lumberjack can only cut the trees at heights greater than or equal to a certain level.
2. When a tree of height H[i] is cut at height H[i] - K, it gives K meters of wood.
3. The lumberjack can cut any part of the tree that is above the given level. In other words, the lumberjack can cut a tree starting from any height between 0 to H[i] and get K meters of wood.

The task is to find the maximum height (the highest level) at which the lumberjack can cut the trees to obtain a total of M meters of wood.

To solve this problem, we can use binary search to find the maximum height at which the lumberjack can cut the trees. We will set the search space to be the range from the minimum height to the maximum height of the trees. Then, we will check if it is possible to cut the trees at a certain height and obtain at least M meters of wood. If it is possible, we try to maximize this height by moving to the right half of the search space. Otherwise, we move to the left half.

Here's the C++ implementation of the EKO problem:

cppCopy code

#include <iostream> #include <vector> #include <algorithm> bool isPossible(std::vector<int>& trees, int targetHeight, int woodRequired) {    long long woodCollected = 0;    for (int height : trees) {        if (height > targetHeight) {            woodCollected += (height - targetHeight);        }    }    return woodCollected >= woodRequired; } int maxTreeCutHeight(std::vector<int>& trees, int woodRequired) {    int left = 0;    int right = *std::max_element(trees.begin(), trees.end());    int result = -1;    while (left <= right) {        int mid = left + (right - left) / 2;        if (isPossible(trees, mid, woodRequired)) {            result = mid;            left = mid + 1;        } else {            right = mid - 1;        }    }    return result; } int main() {    int N, M;    std::cin >> N >> M;    std::vector<int> trees(N);    for (int i = 0; i < N; i++) {        std::cin >> trees[i];    }    int maxHeight = maxTreeCutHeight(trees, M);    std::cout << maxHeight << std::endl;    return 0; }

Example Input:

Copy code

5 7 20 15 10 17 8

Example Output:

Copy code

15

In this code, the isPossible function checks if it is possible to cut the trees at height targetHeight and obtain at least woodRequired meters of wood. The maxTreeCutHeight function uses binary search to find the maximum height at which the lumberjack can cut the trees. The time complexity of this algorithm is O(N * log(maxHeight)), where N is the number of trees and maxHeight is the maximum height of the trees.