Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

### prabhat7298's blog

By prabhat7298, history, 8 months ago, ,

In most of the knapsack variants we've a linear dependency on the knapsack size M but in case where we've many small items leading to a very large knapsack capacity we need an alternate way of solving it. I read about it here that we can solve it by using shortest path algorithm but I wasn't able to grab the whole concept. Can anyone explain it in simpler words and can comment a little on the implementation part. Here you can find a related problem.

• +16

By prabhat7298, history, 11 months ago, ,

I want to find largest length subarray having sum greater than k.

One of the solution I found somewhere is binary searching on the length of subarray. Length of subarray can vary from 1 to n. We can binary search in range low=1 to high=n and for every mid=(low+high)/2 we can check for all subarray of length=mid if any subarray has sum greater than k in O(n). If any such subarray exist then we can search for higher length subarray i.e. low=mid+1 otherwise we decrease the search length i.e. high=mid-1.

int maxlen(vector<int> v)
{
int hi = n, lo = 1, ans = -1, mid, cnt = 0;
while(lo <= hi) {
mid = hi+lo>>1;
if(cnt = count(mid)) {
ans = mid;
lo = mid + 1;
} else {
hi = mid - 1;
}
return ans;
}

int count(int len) {
int cnt = 0;
for(int i = len; i <= n; i++)
if(prefixsum[i] - prefixsum[i - len] > K)
cnt++;
return cnt;
}


What puzzles me is that if we get sum < k for present length subarray then increasing the search length of subarray will ensure that we'll get some subarray having subarray>k. And if we have subarray>k for any length then by decreasing search length we can get more such subarrays having greater than k sum. It could be that we could have decreased search length to get some subarray>k.

So, the question boils down to deciding the predicate of binary search i.e. at each step how we'll decide to change the search range?

PS: I know it can be easily solved by binary searching on prefix subarray rather than on length but I want to know the correctnes of the solution or how it works