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;
}
. Thank you
