Choose Exams to Reach a Target
Autumn Tournament (2010)
Submission name: points.cpp
Problem summary
Choose any subset of N exams. Attending exam i earns its positive score. Count the subsets whose total score is at least T; different exam positions remain distinct even when their scores are equal.
Input
N T, followed by N positive exam scores.
Output
The number of qualifying subsets.
Constraints
1 ≤ N ≤ 36; each score is at most 10^13; T is positive and at least one qualifying subset exists.
Worked example
Original statement sample.
Input
4 6 1 2 5 4
Output
9
Solution analysis
- Enumerating all 2^36 subsets directly is too much. Split the exams into two halves of at most 18 positions. Generate all subset sums of each half, including the empty subset sum 0. To append a score, duplicate the current list with that score added.
- Sort the right-half sums. For every left sum x, a full subset qualifies exactly when its right sum is at least T−x. lower_bound finds the first such entry; every entry from there to the end contributes one subset. Keep duplicate sums, because they may come from different choices of exams.
- For [1,2] and [5,4], left sums are 0,1,2,3 and right sums are 0,4,5,9. The qualifying right counts for target 6 are respectively 1,2,3,3, giving 9. An empty half-choice is allowed; it is simply one part of a full subset.
- Use long long both for sums and the answer: total scores can reach 36·10^13, and the number of subsets can reach 2^36. Neither fits in int.
Why it works
Every full exam subset splits uniquely into one subset of each half. For a fixed left subset, the binary search counts exactly the compatible right subsets. The unique decomposition prevents omission and double counting, including when several subsets have the same numerical sum.
Watch out. Do not deduplicate sums. Include empty subsets in both halves. Use lower_bound for ≥T, not upper_bound. Scores and subset counts require 64-bit arithmetic.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
vector<long long>subsetSums(const vector<long long>&scores,int left,int right){
vector<long long>sums;
sums.reserve(1<<(right-left));
sums.push_back(0);
for(int i=left;i<right;i++){
int oldSize=static_cast<int>(sums.size());
for(int j=0;j<oldSize;j++){
sums.push_back(sums[j]+scores[i]);
}
}
return sums;
}
int main(){
int n;
long long target;
cin>>n>>target;
vector<long long>scores(n);
for(long long&score:scores){
cin>>score;
}
vector<long long>left=subsetSums(scores,0,n/2);
vector<long long>right=subsetSums(scores,n/2,n);
sort(right.begin(),right.end());
long long answer=0;
for(long long sum:left){
// Equal sums remain separate entries because exams are distinct.
answer+=right.end()-lower_bound(right.begin(),right.end(),target-sum);
}
cout<<answer<<'\n';
}