EKO SPOJ (https://www.spoj.com/problems/EKO/)

I was trying EKO-eko on SPOJ (https://www.spoj.com/problems/EKO/) . My code is running fine for both sample test cases but am getting WA on submit
Code :
`
#include
#include
#include
#define ll long long int
using namespace std;

bool height(vector <ll> v, ll mid, ll m) {
	 ll sum = 0;
	for (ll i = 0; i < v.size(); i++) {
		if (mid < v[i]) {
			sum += v[i] - mid;
		}
		if (sum == m) {
			return true;
		}
	}
	return false;
}

ll bs(vector<ll>v, ll m) {
	ll s = v[0];
	ll e = v[v.size() - 1];
	ll ans = 0;
	while (s <= e) {
		ll mid = s + (e - s) / 2;
		if (height(v, mid, m)) {
			ans = mid;
			e = mid - 1;

		} else {

			s = mid + 1;
		}
	}
	return ans;
}

int main() {
	ll n, m;
	cin >> n >> m;
	vector <ll> v;
	for (ll i = 0; i < n; i++) {
		ll x;
		cin >> x;
		v.push_back(x);
	}
	sort(v.begin(), v.end());
	cout << bs(v, m);
}

`

This is a binary search for solution problem.

  • Sort all trees in ascending order of height.
  • Create a prefix-sum Array
  • The maximum height we can go is height of tallest tree, minimum height is 0. Do binary search over heights and calculate how much lumber is harvested at that height.
  • Calculating amount of harvest involves a second binary search (we used STL). Only those trees taller than saw will contribute lumber. Using prefix-sum and deduction we calculate the harvest.
  • Notice clever use of PrefixSum. Psum[x] = sum till index (x-1) or first x elements. Helps us avoid corner case.PSum[upper_bound] = Sum TILL upperbound.
/*https://www.spoj.com/problems/EKO/*/
#include <bits/stdc++.h>
#define int long long int
using namespace std;

int calc(vector<int> &psum, vector<int> &arr, int x, int n){
	int idx = upper_bound(arr.begin(), arr.end(), x) - arr.begin();
	int n_trees = n - idx;
	int conserve = n_trees*x;
	return(psum[n] - psum[idx] - conserve);
}

int solve(vector<int> &arr, int n, int x)
{
	vector<int> psum(n+1); int res = 0;

	psum[0] = 0;
	for(int i = 1; i <= n; ++i){
		psum[i] = psum[i-1] + arr[i-1];
	}

	int l = 0, r = arr[n-1];

	while(l <= r){
		int mid = l + (r-l)/2;
		int harvest = calc(psum, arr, mid, n);
		if(harvest == x){
			return mid;
		}

		if(harvest > x){
			res = mid;
			l = mid + 1; //we need to raise our saw.
		}

		if(harvest < x){

			r = mid - 1;
		}
	} 
	return(res);
}

int32_t main(){
	int n, x; cin >> n >> x; 
	vector<int> forest(n);
	for(int i = 0; i < n; ++i){
		cin >> forest[i];
	}
	sort(forest.begin(), forest.end());
	cout << solve(forest, n, x);
}
1 Like

thank you very much