I was trying EKO-eko on SPOJ (SPOJ.com - Problem 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);
}
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);
}
Same with me
It’s showing wrong answer edit ideone it
#include <iostream>
#include <vector>
using namespace std;
bool isPossible(vector<int> arr, int n, int m, int mid) {
int sub = 0;
for(int i = 0; i < n; i++) {
if(arr[i] > mid) {
sub += (arr[i] - mid);
}
}
if(sub >= m) return true;
else return false;
}
int allocateWoods(vector<int> arr, int n, int m) {
int s = 0;
int maxi = -1;
for(int i = 0; i < n; i++) {
maxi = max(maxi, arr[i]);;
}
int e = maxi;
int mid = s + (e-s)/2;
int ans = -1;
while(s <= e) {
if(isPossible(arr, n, m, mid)) {
ans = mid;
s = mid + 1;
}
else {
e = mid - 1;
}
mid = s + (e-s)/2;
}
return ans;
}
int main() {
vector<int> arr;
int n, m;
cin>>n>>m;
for(int i = 0; i < n; i++) {
int data;
cin>>data;
arr.push_back(data);
}
cout<<allocateWoods(arr, n, m)<<endl;
return 0;
}