Counting Reachable Sums
National Olympiad — National round (2023 season)
Submission name: sums.cpp
Problem summary
For each query (l,r,a,b), count positive values K in [a,b] representable as a subset sum of the banknotes at indices l through r. Every banknote is available at most once and queries are independent.
Input
n q; n positive banknote values; then q lines l r a b.
Output
One count per query.
Constraints
n ≤ 500; q ≤ 1500000; sum S ≤ 250000; 1 ≤ l ≤ r ≤ n; 1 ≤ a ≤ b ≤ 1000000.
Worked example
An independently prepared example for this explanation.
Input
5 2 12 3 4 6 8 2 4 6 15 1 5 1 1000
Output
5 27
Solution analysis
- Process queries grouped by their right endpoint r. Maintain latest[s], the largest possible minimum index in a subset summing to s, using only positions through r. A value s is attainable in [l,r] precisely when latest[s]≥l. Update sums in decreasing order with latest[s]=max(latest[s],latest[s−xr]), then set latest[xr]=r. Zero is handled by this separate singleton update.
- For each right endpoint, bucket sums by latest[s]. Sort its queries by decreasing l. Lower a threshold and activate each bucket in a bit vector; all active sums are now exactly the sums available for that query. Keep a population count for each 512-bit block. A prefix count scans complete block counts plus at most eight 64-bit words, making range counting inexpensive even with 1.5 million queries.
- In the first example the banknotes 3,4,6 produce 6,7,9,10,13 within [6,15], giving five. For the second query the interval upper bound is clamped to S=33: no larger value is attainable. Subtract two prefix counts to answer every query in its original order.
Why it works
After adding xr, a subset either omits it or includes it. In the latter case removing xr leaves a previously reachable sum, whose largest minimum index is latest[s−xr]; the singleton has minimum index r. Descending updates prevent reuse of xr. Thus latest has the claimed invariant. Activating exactly buckets of index at least l makes the bit vector the indicator of attainable positive sums in [l,r]. Block and word counts count its set bits exactly.
Watch out. A boolean reachable-sum array loses the left boundary information. Update sums downward to enforce single use. Exclude sum zero and clamp query bounds before indexing the bit vector.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
#include<cstdint>
#include<algorithm>
// Algorithm: Process queries grouped by their right endpoint r.
using namespace std;
struct Query{
int left,low,high,id;
};
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,q;
cin>>n>>q;
vector<int>x(n+1);
int total=0;
for(int i=1;i<=n;++i){
cin>>x[i];
total+=x[i];
}
vector<vector<Query>>queries(n+1);
for(int i=0;i<q;++i){
int l,r,a,b;
cin>>l>>r>>a>>b;
queries[r].push_back({l,a,min(b,total),i});
}
vector<int>answer(q),latest(total+1,0);
vector<vector<int>>buckets(n+1);
int prefix=0;
const int blockBits=512;
int words=(total+64)/64;
vector<uint64_t>bits(words);
vector<int>blockCount((total+blockBits)/blockBits);
auto countPrefix=[&](int end){
if(end<1){
return 0;
}
end=min(end,total);
int result=0;
int complete=end/blockBits;
for(int i=0;i<complete;++i){
result+=blockCount[i];
}
int firstWord=complete*(blockBits/64);
for(int i=firstWord;i<end/64;++i){
result+=__builtin_popcountll(bits[i]);
}
int remainder=end%64;
uint64_t mask=remainder==63?~uint64_t(0):(uint64_t(1)<<(remainder+1))-1;
result+=__builtin_popcountll(bits[end/64]&mask);
return result;
};
for(int r=1;r<=n;++r){
prefix+=x[r];
for(int sum=prefix;sum>x[r];--sum){
latest[sum]=max(latest[sum],latest[sum-x[r]]);
}
latest[x[r]]=r;
if(queries[r].empty()){
continue;
}
for(auto&bucket:buckets){
bucket.clear();
}
for(int sum=1;sum<=prefix;++sum){
if(latest[sum]!=0){
buckets[latest[sum]].push_back(sum);
}
}
sort(queries[r].begin(),queries[r].end(),[](const Query&a,const Query&b){
return a.left>b.left;
});
fill(bits.begin(),bits.end(),0);
fill(blockCount.begin(),blockCount.end(),0);
int threshold=r+1;
for(const Query&query:queries[r]){
while(threshold>query.left){
--threshold;
for(int sum:buckets[threshold]){
bits[sum/64]|=uint64_t(1)<<(sum%64);
++blockCount[sum/blockBits];
}
}
answer[query.id]=countPrefix(query.high)-countPrefix(query.low-1);
}
}
for(int result:answer){
cout<<result<<'\n';
}
}