Partitions into Four Positive Summands
National Olympiad — Municipal round (2020 season)
Submission name: sum.cpp
Problem summary
Count representations X=A+B+C+D with positive integers A≤B≤C≤D, without counting reorderings separately.
Input
X.
Output
The representation count.
Constraints
1 ≤ X ≤ 1500.
Worked example
Input and output for the worked example discussed below.
Input
5
Output
1
Solution analysis
- Write A=1+a,B=A+b,C=B+c,D=C+d with nonnegative differences. Substitution gives X−4=4a+3b+2c+d. Thus count combinations of coin sizes 1,2,3,4 for target X−4.
- Start ways[0]=1, process coin sizes outside the sum loop and sums in increasing order. This permits repeated coin sizes but counts coefficient tuples, not permutations.
- For X=5 the reduced target 1 has one representation, corresponding to 1+1+1+2. For X<4, four positive summands are impossible.
Why it works
The reversible difference transformation is a bijection with the coefficient tuples counted by unbounded coin DP.
Complexity: O(X) time and O(X) space with four fixed coin passes.
Watch out. Subtract four for positivity and loop over coin sizes first to avoid counting permutations.
Commented C++17 solution
An independently written complete program with standard headers.
// The reversible difference transformation is a bijection with the coefficient tuples counted by unbounded
// coin DP.
#include<iostream>
#include<vector>
using namespace std;
int main(){
int total;
cin>>total;
if(total<4){
cout<<0<<'\n';
return 0;
}
int target=total-4;
vector<long long>ways(target+1);
ways[0]=1;
for(int coin=1;coin<=4;coin++){
for(int sum=coin;sum<=target;sum++){
ways[sum]+=ways[sum-coin];
}
}
cout<<ways[target]<<'\n';
}