LGSEG - Editorial

PROBLEM LINK:

Practice
Contest: Division 3
Contest: Division 2
Contest: Division 1

Author: Piyush Mittal
Tester : Riley Borgard
Editorialist: Aman Dwivedi

DIFFICULTY:

Easy-Medium

PREREQUISITES:

Binary Search, Binary Lifting

PROBLEM:

Chef has a sequence A_1, A_2, \ldots, A_N. Let’s call a contiguous subsequence of A a segment.

A segment is good if it can be divided into at most K segments such that the sum of elements in each of these sub-segments is at most S.

You need to find the maximum number of elements in a good segment.

EXPLANATION:

Let’s try to make an edge from index I to index J, such that the previous segment starts from an index I and ends at index J-1 having the sum of at most S, and the next segment starts with index J. As our goal is to maximize the length we will try to maximize J as much as possible.

By doing so with every index we will get a N-ary tree where edge (u,v) denotes the segment from index [u,v-1] such that sum of this segment is at most S. As we can have at most K such segments we will find the K_{th} node away from this node.

If we look carefully the problem is reduced to finding the K_{th} ancestor of every node. We can find this easily by using Binary Lifting Technique. Finally, we will find the longest segment possible over all the segments.

However, It is not necessary to build the tree, it’s just for analogy and understanding of the problem.
We can solve this problem just by using the concept of Binary Lifting.

For each index i, we will precompute the ending index of sub-segments inside the main segment that starts from index i in powers of two. Let’s store them in the array next, where:

  • nxt[i][j] is the ending index of the 2^j-th sub-segment such that the main segment starts from the index i with i=1,2,\dots,N and j=0,1,\dots,ceil(log(K))

Now for every index, i we will try to find the ending index of the K-th sub-segment by using the magic of the Binary Lifting Technique.

Suppose we are at index i, we will try to find the maximum possible ending index in terms of the power of 2, such that 2^j \le K. Finally, we will subtract 2^j from K as we had already covered 2^j-th sub-segments and our starting index will be changed to up[i][j]+1. We will do until we reach the end of the array or our K becomes 0.

Hence we will be able to find the maximum possible ending index for K-th sub-segment such that the main segment begins from index i. Finally, we output the maximum length of the segment possible.

TIME COMPLEXITY:

O(N*log(N)) per test case

SOLUTIONS:

Author
#include<bits/stdc++.h>
#define int long long

using namespace std;

int n, k, S;
int ans;
deque < int > dq;

vector < vector < int > > gr;
void dfs(int cur, int taken){
    // assert(cur>=0 and cur<=n);
    int pop = -1;
    if((int)dq.size() > k){
        pop = dq.front();
        dq.pop_front();
        taken -= pop;
    }
    ans = max(ans, taken);
    // assert((int)dq.size()<=k);
    for(auto x: gr[cur]){
        assert(x<cur);
        int dif = cur-x;
        // assert(dif>0ll);
        dq.push_back(dif);
        dfs(x, taken+dif);
        dq.pop_back();
    }
    if(pop!=-1){
        dq.push_front(pop);
        taken+=pop;
    }
    return;
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int t;
    cin >> t;
    while(t--){
        cin >> n >> k >> S;
        gr.clear();
        gr.resize(n+1);
        for(int i=0; i<=n; ++i)gr[i].clear();
        vector < int > v(n);
        for(auto &x: v) cin >> x;
        ans=0;
        vector < int > pref(n+1, 0);

        for(int i=0; i<n; ++i){
            pref[i+1] += v[i];
            pref[i+1] += pref[i];
        }
        vector < int > idx(n, 0);
        for(int i=0; i<n; ++i){
            idx[i] = (lower_bound(pref.begin(), pref.end(), pref[i]+S+1)-pref.begin())-1;
        }
        for(int i=n-1; i>=0; --i){
            gr[idx[i]].push_back(i);
        }
        dq.clear(); 
        dfs(n, 0);
        cout << ans << "\n";
    }

    return 0;
}

Tester

#include <bits/stdc++.h>

#define ll long long
#define sz(x) ((int) (x).size())
#define all(x) (x).begin(), (x).end()
#define vi vector<int>
#define pii pair<int, int>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;
template<typename T>
using minpq = priority_queue<T, vector<T>, greater<T>>;

// go[i] = max j such that sum[i, j] > S
// use binary lifting to find go^k [i] for all i
// answer is maximum go^k [i]
// complexity: O(n log n)

void solve() {
    int n, k;
    ll S;
    cin >> n >> k >> S;
    vector<ll> a(n + 1);
    rep(i, 1, n + 1) {
        cin >> a[i];
        a[i] += a[i - 1];
    }
    vi go(n + 2), ans(n + 2);
    rep(i, 1, n + 1) {
        go[i] = upper_bound(all(a), a[i - 1] + S) - a.begin();
        ans[i] = i;
    }
    go[n + 1] = n + 1;
    rep(l, 0, 20) {
        if(k >> l & 1) {
            rep(i, 1, n + 2) ans[i] = go[ans[i]];
        }
        rep(i, 1, n + 2) go[i] = go[go[i]];
    }
    int mx = 0;
    rep(i, 1, n + 1) {
        mx = max(mx, ans[i] - i);
    }
    cout << mx << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int te;
    cin >> te;
    while(te--) solve();
}
Editorialist
#include<bits/stdc++.h>
using namespace std;

#define int long long

int up[100005][20];

void solve()
{
	int n,k,s;
	cin>>n>>k>>s;

	vector<int> a(n);
 

	for(int i=0;i<n;i++)
	{
		cin>>a[i];

		if(i!=0)
			a[i]+=a[i-1];
	}


	vector <int> nxt(n+1);
	nxt[n]=n;


	for(int i=0;i<n;i++)
	{
		int prev;
		if(i==0)
			prev=0;
		else
			prev=a[i-1];

		nxt[i] = lower_bound(a.begin(), a.end(),prev+s+1) - a.begin();
	}


	for(int i=0;i<20;i++)
	{
		for(int j=0;j<n;j++)
		{
			up[j][i] = nxt[j];
			nxt[j] = nxt[nxt[j]];
		}
	}

	int ans = 0;

	for(int i=0;i<n;i++)
	{
		int temp = k;
		int idx = i;

		for(int j=19;j>=0;j--)
		{
			if((1<<j) <= temp)
			{
				idx = up[idx][j];
				temp -= (1<<j);
			}

			if(idx==n)
				break;
		}

		ans = max(ans,idx-i);
	}

	cout<<ans<<endl;
}

int32_t main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
 
  // freopen("input.txt","r",stdin);
  // freopen("output.txt","w",stdout);

  int t;
  cin>>t;

  while(t--)
    solve();

return 0;
}

19 Likes

I’m really curious: how did you know it can be solved using tree? It’s not obvious to me.
Btw, great problem :fire:

5 Likes

This was one of the greatest binary lifting/sparse table problem I have seen.

19 Likes

It’s marked Easy? Damn! I am feeling dumb :frowning:

17 Likes

It was the 5^{th} problem of the whole list, so I marked it as easy. Don’t feel dumb I will change that into Easy-Medium.

5 Likes

Is it possible to solve using binary search?

I haven’t done such problem yet but i tried to solve using an iterative method, i understand that it will result in TLE in worst case but i thought it could be optimised i’m getting TLE on test case 3 only can someone suggest some improvements ?
https://www.codechef.com/viewsolution/49352485

I tried it using binary search.
But giving TLE
https://www.codechef.com/viewsolution/49338359

Now, he don’t feel dumb :sweat_smile:

1 Like

I tried binary search over length of the segment and sliding window technique using deque. Can someone give me a testcase where this code fails.
My submission

Might be a noob doubt…
If we store contiguous clusters of sum <= s, like below
n = 5, k = 2
arr = [1, 3, 2, 1, 5]
cluster = [ (1, 3), (2, 1), (5) ]
length_of_clusters = [ 2, 2, 1 ]
can we perform maximum sum of k-contiguous length_of_clusters

2 Likes

This problem is even better by far. It uses binary lifting. Problem - D - Codeforces

1 Like

Why the momory limit was so strict, I wasted 2 hr to find that I should replace long to int.

2 Likes

I don’t think many binary lifting problems are uninteresting. Binary lifting problems are usually about spotting a nice observation and generalizing it. Just before this contest I solved this problem which involves binary lifting:

I honestly prefer P7SWAPS to both today’s problem and the one you listed, but it just comes down to your own taste.

Great problem either way (although the only one I solved during the contest) :slight_smile:

2 Likes

All my tests are getting AC, but I am getting RE (SIGSEGV) in test number 3.
I am unable to figure out what mistake I am making.
Solution link: CodeChef: Practical coding for everyone

This was a nice problem. I really enjoyed solving it. Append INF to the array. I defined f[i] as the smallest j such that \sum_{t=i}^{j} a_t > S.These values can be calculated by pre-computing prefix sums and then doing simple binary search for each value of f[i]. Now we perform binary search on the answer. Say we want to check if there is a beautiful segment of size b.
We can check this by iterating through all possible segments [p, p+b-1] . So, how do we efficiently find minimum subsegments required to cover a interval? We do this using Binary Lifting. We are basically asking for minimum r such that f^r(p) \geqslant p+b. This can be done in \mathcal O(\log n) if we do Binary Lifting. That’s it. That solves the problem in \mathcal O(n \log^2n).

1 Like

I used two pointer approach to calculate the longest subarray starting at i such that sum doesn’t exceed s. IMO it’s easier to implement and reduces the execution time quite a bit (about 30% faster so some slow language may pass easier).

Here’s my solution if anyone is curious CodeChef: Practical coding for everyone

5 Likes

I tried to solve the problem using

binray-search & dfs

, my submission is giving Runtime error on the 3rd test case can someone please suggest some test case where my code might be getting into RTE.
Submission link: https://www.codechef.com/viewsolution/49364717

Loved the problem. It’s been a while since I learnt binary lifting, but wasn’t ever able to get AC in any contest before this. Also, probably this helped me reach 6 :star2: . Thank you

5 Likes

you are op bhaiya :slight_smile: :partying_face: