Numbers That Sum Three Earlier Values
National Olympiad — National round (2023 season)
Submission name: nice.cpp
Problem summary
Count positions whose value equals three earlier values; earlier positions may be reused.
Input
N and N signed values.
Output
The qualifying-position count.
Constraints
1≤N≤5000;−100000≤a[i]≤100000.
Worked example
Input and output for the worked example discussed below.
Input
6 2 1 3 5 7 10
Output
4
Solution analysis
- Maintain a table of sums of two strictly earlier values, including the same earlier position twice. For a[i], try every earlier a[j] as the third term and look up a[i]−a[j].
- Only after testing position i, insert a[i]+a[j] for j≤i. This admits repeated positions for future queries without accidentally using the current value in its own representation.
- In[2,1,3,5,7,10], values3,5,7,10 qualify:3=1+1+1,5=2+2+1,7=3+3+1,10=5+3+2. Thus the answer is4.
Why it works
Before each query the table contains exactly pair sums of earlier positions. Each successful lookup gives a legal triple, and every legal triple has an earlier third value tested by the loop. Delayed insertion preserves strict earlierness.
Complexity: O(N²) time and O(N+V) space with fixed pair range V=400001.
Watch out. Insert diagonal pairs and allow position reuse. Test before inserting current pairs, and bounds-check differences before indexing.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
#include<utility>
using namespace std;
// Before each query the table contains exactly pair sums of earlier positions.
int main(){
int n;
cin>>n;
vector<int>a(n);
for(int&x:a){
cin>>x;
}
const int offset=200000;
vector<bool>pairSum(400001,false);
int answer=0;
for(int i=0;i<n;i++){
for(int j=0;j<i;j++){
int need=a[i]-a[j];
if(need>=-offset&&need<=offset&&pairSum[need+offset]){
answer++;
break;
}
}
for(int j=0;j<=i;j++){
pairSum[a[i]+a[j]+offset]=true;
}
}
cout<<answer<<'\n';
}