Fence 363/B

Intuition

This problem felt interesting when I was grinding prefix sum problems. Here, a person has n fences in front of his house, where the heights of the fences are h1, h2, ..., hn. Now he bought a piano whose side length is given as k. To bring the piano inside, he has to cut exactly k consecutive fences.

But cutting taller fences is more painful. So we need to find a starting index such that the sum of heights of those k consecutive fences becomes minimum. That way, the person has to do the least amount of work.

Now if we calculate the sum of every segment manually, then for every position we again traverse k elements. In that case, the time complexity becomes roughly:

O(n × k)

According to the constraints, this can become too slow.

Since the problem is heavily about repeated sum calculation and complexity optimization, the best option here is prefix sum.

Approach

In prefix sum, we mainly use cumulative sums to calculate range sums quickly.

Suppose:

pref[i] means the cumulative sum of the first i elements.

Then any range sum from l to r can be calculated as: pref[r] - pref[l - 1]

Here every segment size is fixed as k.

So if the current starting index is i, then the ending index becomes: i + k - 1

Therefore, the current segment sum becomes: pref[i + k - 1] - pref[i - 1]

This allows us to calculate every segment sum in:

O(1)

Since the output requires the starting index, we also need to track the current index along with the minimum sum.

Whenever we find a smaller sum:

• 
  update the minimum sum
  

• 
  store the current starting index
  

Finally, print that index.

Code

#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<long long> VLL;

#define inp(v) for (auto& x : v) cin >> x
 void solve();
int   main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
     #ifdef LOCAL
    cerr << "Execution time: " << 1000.f * clock() / CLOCKS_PER_SEC << " ms." << nl;
    #endif
    
        solve();
    return 0;       
}

void solve() {

    ll a, b;
    cin >> a >> b;
    VLL fence(a);
    inp(fence);
    VLL pref(a + 1, 0);
    for (int i = 1; i <= a;i++){
        pref[i] = pref[i - 1] + fence[i - 1];
    }
    ll min_f = INF;
    ll min_i = 1;
    for (int i = 1; i <= pref.size()-b;i++){
        ll threesum = pref[i + b-1] - pref[i - 1];
        if(min_f>threesum){
            min_f = threesum;
            min_i=i;
        }
    }
    cout << min_i << endl;
}