Expressions
National Olympiad — Regional round (2009 season)
Submission name: expr.cpp
Problem summary
Insert +, − or multiplication between every consecutive pair of given decimal digits, preserving their order. Under ordinary multiplication precedence, count distinct resulting values.
Input
N on the first line; N space-separated decimal digits on the second.
Output
The number of distinct expression values.
Constraints
1 < N < 20; digits are 0 through 9; original time limit 15 seconds.
Worked example
Official statement example.
Input
3 1 2 2
Output
5
Solution analysis
- Every expression is a sum or difference of maximal consecutive multiplication blocks. Let values[i] be the set of possible values using the first i digits. For every possible start j of the final block, compute its product P. If j=0, insert P; otherwise insert x+P and x−P for each x in values[j].
- Build prefixes in increasing length. Hash sets merge equal values immediately, avoiding repeated exploration of expression prefixes that already evaluate to the same number. The signed final block is independent of the preceding prefix, so merging loses no useful information.
- For digits 1,2,2, the final value set is {−3,0,1,4,5}. A final multiplication block may have length one, two or three; all are covered by the backward product loop. Signed 64-bit arithmetic is sufficient: the absolute value of any expression on i digits is at most 9^i, and 9^19<2^63.
Why it works
Induct on prefix length. Every expression either is one multiplication block, or has a unique last addition/subtraction separator. Its preceding prefix value is in values[j] by induction and the remaining digits form the tested product P, so the expression result is inserted. Conversely each insertion concatenates a valid prefix expression and a legal signed product block, so every stored value is achievable. Set cardinality is therefore the exact number requested.
Watch out. Multiplication has precedence over addition and subtraction.,Count unique values, not operator assignments.,Negative values and zero must be retained.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Induct on prefix length. Every expression either is one multiplication block, or has a
// unique last addition/subtraction separator.
#include<iostream>
#include<unordered_set>
#include<vector>
using namespace std;
int main(){
int n;
cin>>n;
vector<int>digit(n);
for(int&x:digit){
cin>>x;
}
vector<unordered_set<long long>>values(n+1);
for(int length=1;length<=n;++length){
long long product=1;
for(int start=length-1;start>=0;--start){
product*=digit[start];
if(start==0){
values[length].insert(product);
}
else{
for(long long prefix:values[start]){
values[length].insert(prefix+product);
values[length].insert(prefix-product);
}
}
}
}
cout<<values[n].size()<<'\n';
}