Largest Unrepresentable Step Sum
Autumn Tournament (2014)
Submission name: sequence.cpp
Problem summary
Allowed positive step sizes x1<…<xn define increasing sequences beginning at zero. Find the largest integer that cannot be expressed as a nonnegative integer combination of these sizes. The first two sizes are coprime.
Input
n, then the n increasing step sizes.
Output
The largest nonrepresentable integer.
Constraints
2≤n≤5; x1>1; gcd(x1,x2)=1. Subtasks: all sizes<1000; or n=2 and xn<10^9; or1<x1<10^(6−n), x2>10^(n+11), xn<10^(n+12).
Worked example
Original statement sample.
Input
2 4 7
Output
17
Solution analysis
- If there are exactly two sizes a and b, the coprime two-coin theorem gives ab−a−b immediately. This avoids allocating a residue graph with up to a billion vertices in that subtask.
- For three or more sizes, let a=x1. For every residue r modulo a, compute the smallest representable sum dist[r]. Adding a coin x is an edge r→(r+x)%a with weight x, so Dijkstra from residue zero computes these minima. The constraints make a small even when the coin values are very large.
- Every value dist[r]+ka is representable. Conversely no smaller value with residue r is. Thus the last missing value in this class is dist[r]−a, and the answer is their maximum. For sizes4 and7, residues0,1,2,3 have minima0,21,14,7; the largest last gap is21−4=17.
Why it works
Paths in the residue graph correspond exactly to multisets of allowed steps and have their sum as path weight. Therefore shortest paths give the least representable sum of each residue. Coprimality makes every residue reachable, and adding copies of a fills every larger value of that residue. For two coprime coins, the residues of 0,b,…,(a−1)b are all distinct, so their maximum minimal value is (a−1)b, yielding ab−a−b.
Watch out. Use 64-bit distances and products. Do not enumerate every integer up to the answer. The small-a condition applies only when n≥3; use the formula for n=2.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<functional>
#include<iostream>
#include<limits>
#include<queue>
#include<utility>
#include<vector>
using namespace std;
int main(){
int n;
cin>>n;
vector<long long>coin(n);
for(long long&value:coin){
cin>>value;
}
if(n==2){
cout<<coin[0]*coin[1]-coin[0]-coin[1]<<'\n';
return 0;
}
int modulus=static_cast<int>(coin[0]);
const long long infinity=numeric_limits<long long>::max()/2;
vector<long long>distance(modulus,infinity);
priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<pair<long long,int>>>pending;
distance[0]=0;
pending.push({0,0});
while(!pending.empty()){
auto[cost,residue]=pending.top();
pending.pop();
if(cost!=distance[residue]){
continue;
}
for(long long value:coin){
int next=static_cast<int>((residue+value)%modulus);
if(cost+value<distance[next]){
distance[next]=cost+value;
pending.push({distance[next],next});
}
}
}
// The first representable value ends the missing part of each residue class.
cout<<*max_element(distance.begin(),distance.end())-modulus<<'\n';
}