Expression
National Olympiad — Regional round (2011 season)
Submission name: express.cpp
Problem summary
Insert parentheses into a digit-and-operator expression to minimize its value. Digits remain in order and operators are +, − or *.
Input
One alternating digit/operator string of odd length.
Output
The smallest achievable value.
Constraints
The string has fewer than 30 characters. Every intermediate value for every valid parenthesization has absolute value below 10^18.
Worked example
Official statement example.
Input
1+2-3*4
Output
-9
Solution analysis
- For each interval of digits store both its smallest and largest attainable values. A singleton interval has its digit as both extrema.
- Try each possible final operator inside an interval. Addition and subtraction attain their extrema at endpoint combinations; multiplication can reverse order for negative operands, so explicitly test all four combinations of left and right minima and maxima.
- Fill intervals by increasing length. For 1+2−3*4, the parenthesization 1+(2−(3*4)) gives −9. Keeping only minima would lose possible minima formed by subtracting a large right value or multiplying values of opposite signs.
Why it works
Every parenthesization has a unique final operator splitting it into two smaller intervals. Inductively their extrema are correct. For +, − and multiplication, the extrema over attainable operand values occur at extreme operand pairs, all four of which are tested and are themselves attainable independently. Taking the minimum and maximum over all splits therefore yields exactly the interval extrema.
Watch out. Track maxima as well as minima.,Use signed 64-bit integers; the stated bound makes every evaluated combination safe.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Every parenthesization has a unique final operator splitting it into two smaller
// intervals. Inductively their extrema are correct.
#include<algorithm>
#include<iostream>
#include<limits>
#include<string>
#include<vector>
using namespace std;
long long apply(long long a,long long b,char op){
if(op=='+'){
return a+b;
}
if(op=='-'){
return a-b;
}
return a*b;
}
int main(){
string s;
cin>>s;
int n=int(s.size()+1)/2;
vector<vector<long long>>lo(n,vector<long long>(n)),hi=lo;
for(int i=0;i<n;++i){
lo[i][i]=hi[i][i]=s[2*i]-'0';
}
for(int length=2;length<=n;++length){
for(int l=0;l+length<=n;++l){
int r=l+length-1;
lo[l][r]=numeric_limits<long long>::max();
hi[l][r]=numeric_limits<long long>::min();
for(int k=l;k<r;++k){
for(long long a:{lo[l][k],hi[l][k]}){
for(long long b:{lo[k+1][r],hi[k+1][r]}){
long long value=apply(a,b,s[2*k+1]);
lo[l][r]=min(lo[l][r],value);
hi[l][r]=max(hi[l][r],value);
}
}
}
}
}
cout<<lo[0][n-1]<<'\n';
}