Lexicographically First Sum Pair
National Olympiad — Municipal round (2015 season)
Submission name: sum.cpp
Problem summary
Find the lexicographically smallest index pair (i,j), 1 ≤ i ≤ j ≤ n, whose values sum to s. An index may be used twice. Output 0 0 when no pair exists.
Input
n, the n sequence values, then s.
Output
The required indices or 0 0.
Constraints
0 < n < 1000000; 1 ≤ ai < 1000; 0 < s < 2000.
Worked example
Official sample; other valid outputs may exist.
Input
10 3 2 2 3 3 1 5 3 1 1 6
Output
1 1
Solution analysis
- Because values lie in a small range, record only the earliest index of each value. For a complementary value pair x,y with x+y=s, their earliest occurrences give its lexicographically best index pair after sorting the two indices.
- Enumerate all x between 1 and 999, discard missing or out-of-range complements, and minimize the resulting index pair. If x=y, using the same earliest index twice is permitted.
- In the sample value 3 first appears at index 1 and 3+3=6. Thus (1,1) is feasible and no pair can precede it.
Why it works
Every feasible pair uses complementary values. Replacing each selected occurrence by the earliest occurrence of its value cannot increase either ordered index after sorting. The enumeration considers the resulting best pair for every complementary value choice and selects their lexicographic minimum.
Watch out. The condition is i≤j, so equal indices are explicitly allowed.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Every feasible pair uses complementary values. Replacing each selected occurrence by the
// earliest occurrence of its value cannot increase either ordered index after sorting.
#include<iostream>
#include<array>
#include<algorithm>
#include<utility>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin>>n;
array<int,1000>first{};
for(int i=1;i<=n;++i){
int x;
cin>>x;
if(first[x]==0){
first[x]=i;
}
}
int s;
cin>>s;
pair<int,int>best={n+1,n+1};
for(int x=1;x<1000;++x){
int y=s-x;
if(y>0&&y<1000&&first[x]&&first[y]){
pair<int,int>candidate={min(first[x],first[y]),max(first[x],first[y])};
best=min(best,candidate);
}
}
if(best.first==n+1){
best={0,0};
}
cout<<best.first<<' '<<best.second<<'\n';
}