Pairs With a Given Sum
Национална олимпиада - Общински кръг 2026
Submission name: pair.cpp
Problem summary
Count unordered pairs of distinct input values whose sum equals a target. Input values are distinct positive integers.
Input
n target followed by n distinct values.
Output
The number of qualifying pairs.
Constraints
2 ≤ n ≤ 500000; values < 1000000; 1 ≤ target ≤ 300000.
Worked example
The worked example illustrates the rule described in the analysis.
Input
5 6 1 5 2 3 4
Output
2
Solution analysis
- Maintain a Boolean table indicating which relevant values have already been read. For a new value v, its only possible partner is target−v.
- If v is at least target, no positive partner exists. Otherwise query the table for target−v before inserting v. This prevents pairing a value with itself.
- Every unordered pair is counted when its second member appears. In the example, the pairs are {1,5} and {2,4}; the single 3 cannot pair with itself.
Why it works
Each counted pair has the requested sum and two different input positions. Every valid pair is detected exactly at its later input position. Distinct input values make a Boolean presence table sufficient.
Watch out. The distinctness and positivity guarantees are important. Query before insertion. Values above the target must not index the table.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Each counted pair has the requested sum and two different input positions. Every valid
// pair is detected exactly at its later input position.
#include<algorithm>
#include<array>
#include<cstdint>
#include<iostream>
#include<numeric>
#include<string>
#include<vector>
using namespace std;
int main(){
int n,target;
cin>>n>>target;
vector<bool>seen(target+1);
int answer=0;
for(int i=0;i<n;++i){
int value;
cin>>value;
if(value<target){
answer+=seen[target-value];
seen[value]=true;
}
}
cout<<answer<<'\n';
}