Addition and Multiplication
National Olympiad — Municipal round (2010 season)
Submission name: addmul.cpp
Problem summary
Initially only 1 is known. At each simultaneous step, add every sum and product of two numbers known before that step; old values remain available. Determine the first step when N appears.
Input
One integer N.
Output
The first step number; 1 is available at step zero.
Constraints
1 ≤ N ≤ 10000.
Worked example
Official statement example.
Input
26
Output
5
Solution analysis
- Let dp[v] be the earliest step for v. If the last operation combines x and y, both must exist before it, so that operation produces v at step 1+max(dp[x],dp[y]).
- Process v in increasing order. Test all splits v=x+(v−x), and all factor pairs v=x·(v/x) with x≥2. All operands in these useful operations are smaller than v, so their optimal times are already known. Initialize dp[1]=0.
- For 26, neither an addition nor a multiplication can combine two numbers available by step three to reach it. But 13 is ready at step four, allowing 13·2 at step five. The recurrence returns five.
Why it works
A minimum expression producing v ends in either addition or multiplication. Its operand arrival times are at least their optimal dp values, giving the recurrence as a lower bound. Conversely operands attaining those times can be computed simultaneously and combined one step after both are available, attaining every recurrence candidate. Induction over v proves correctness.
Watch out. Parallel computation uses max of operand times, not their sum.,Multiplication by one cannot improve an arrival time.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: A minimum expression producing v ends in either addition or multiplication. Its operand
// arrival times are at least their optimal dp values, giving the recurrence as a lower bound.
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
int main(){
int n;
cin>>n;
vector<int>dp(n+1,0);
for(int v=2;v<=n;++v){
dp[v]=v-1;
for(int x=1;x<=v/2;++x){
dp[v]=min(dp[v],1+max(dp[x],dp[v-x]));
}
for(int x=2;x<=v/x;++x){
if(v%x==0){
dp[v]=min(dp[v],1+max(dp[x],dp[v/x]));
}
}
}
cout<<dp[n]<<'\n';
}