PONGAL3 - Editorial

Author: Vishal
Tester: Vishal
Editorialist: Vishal

Easy

PREREQUISITES:

Two Pointers, Sliding Window

PROBLEM:

Given an array representing the prices of sweets and some money M, find the longest contiguous subarray of sweets you can buy.

EXPLANATION:

For each index L, we need to find the largest index R such that A_L + A_L+1 + … + A_R \leq M.

Assume R has already been computed for some L. Changing L to L+1 decreases the sum on the segment [L,R] as A_i > 0 for all i in the range [0,N-1]. Hence, the new R' for L+1 has to be \geq R.

Hence, since we have proved that R is non-decreasing as L increases, we can use the sliding window technique to calculate the longest valid subarray from each index. The final answer would be max(R-L+1), \forall L \in [0,N-1].

SOLUTIONS:

Setter's Solution
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int tt = 1;
cin >> tt;
while (tt--)
{
ll n, m;
cin >> n >> m;
ll a[n];
for (int i = 0; i < n; ++i)
cin >> a[I];

// Cur holds the sum in the range [L,R].
ll ans = 0, r = -1, cur = 0;

for (ll l = 0; l < n; ++l)
{

// Extend 'R', as long as [L,R] valid.
while (r < n - 1 && cur + a[r + 1] <= m)
{
cur += a[r + 1];
r++;
}

// Try to maximize answer using R-L+1.
ans = max(ans, r - l + 1);

// Reduce cur.
cur -= a[l];
}

cout << ans << "\n";
}

}