Increasing Sequences
National Olympiad — Municipal round
Submission name: seq.cpp
Problem summary
Count strictly increasing sequences of length n using distinct integers chosen from 1 through k.
Input
k and n, in that order.
Output
The number of valid sequences; zero if n > k.
Constraints
1 ≤ k,n ≤ 49.
Worked example
An independently prepared example for this explanation.
Input
5 2
Output
10
Solution analysis
- Choosing the n numbers completely determines their increasing order. The answer is the binomial coefficient C(k,n).
- Use Pascal’s identity: C(i,j)=C(i−1,j)+C(i−1,j−1).
- Store only one DP row. Update j downward so both terms still belong to the previous row.
- Use long long. The largest coefficient needed here fits in signed 64 bits.
Why it works
Every j-element subset either excludes the newest element, counted by C(i−1,j), or includes it, counted by C(i−1,j−1). These two cases are disjoint and exhaustive.
Complexity: O(k·n) time, O(n) space.
Watch out. Updating the DP from left to right reuses this row’s changes and counts the wrong objects.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
int k,n;
cin>>k>>n;
if(n>k){
cout<<0<<'\n';
return 0;
}
vector<long long>dp(n+1,0);
dp[0]=1;
for(int i=1;i<=k;++i){
for(int j=min(i,n);j>=1;--j){
dp[j]+=dp[j-1]; // Descend to preserve the previous row.
}
}
cout<<dp[n]<<'\n';
}