Ordered Compression
National Olympiad — Municipal round (2014 season)
Submission name: compress.cpp
Problem summary
Count ordered sequences of integers between 1 and A whose sum is N. Such a sequence represents a compression of N consecutive ones.
Input
Two integers N A.
Output
The exact number of sequences.
Constraints
1≤A≤N≤50.
Worked example
An independently prepared example for this explanation.
Input
4 2
Output
5
Solution analysis
- Let ways[s] be the number of valid sequences summing to s. The empty sequence gives ways[0]=1.
- Classify a nonempty sequence by its final value v. Removing v leaves any sequence counted by ways[s−v], hence ways[s]=Σ ways[s−v] over 1≤v≤min(A,s). Compute increasing sums.
- For N=4,A=2 the sequences are 1111,112,121,211,22, giving 5. The three arrangements containing one 2 are distinct because order matters.
Why it works
Every nonempty sequence has exactly one final value. Removing or appending that value is a bijection with a smaller valid sequence, and the different final-value classes are disjoint. The recurrence therefore counts every sequence exactly once.
Complexity: O(NA) time and O(N) space. The answer is at most 2^(N−1), so signed 64-bit integers suffice.
Watch out. This counts compositions, not unordered partitions. The base ways[0]=1 is required.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
// Algorithm: Let ways[s] be the number of valid sequences summing to s.
using namespace std;
int main(){
int total,maximum;
cin>>total>>maximum;
vector<long long>ways(total+1,0);
ways[0]=1;
for(int sum=1;sum<=total;sum++){
for(int last=1;last<=maximum&&last<=sum;last++){
ways[sum]+=ways[sum-last];
}
}
cout<<ways[total]<<'\n';
}