Cross-Sequence Sums
National Olympiad — Municipal round
Submission name: xsum.cpp
Problem summary
Count pairs of positions, one in each of two sequences of N positive integers, whose values sum to X. Repeated equal values at different positions give different pairs.
Input
N X, followed by the N values of the first sequence and N values of the second.
Output
The number of pairs; 0 if there are none.
Constraints
5 ≤ N ≤ 1000000; every value and X is positive and below 100000. The source also includes a smaller illustrative example.
Worked example
An independently prepared example for this explanation.
Input
5 6 1 1 2 4 5 5 5 4 2 1
Output
7
Solution analysis
- Count occurrences of every value in the first sequence.
- For each second-sequence value b, add the frequency of X−b if this complement is valid.
- Use a 64-bit answer, since as many as N² pairs may qualify.
Why it works
Each pair is counted exactly once when its second position is processed.
Complexity: O(N+100000) time; O(100000) space.
Watch out. Do not count only distinct value pairs.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Each pair is counted exactly once when its second position is processed.
#include<iostream>
#include<vector>
#include<utility>
#include<tuple>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,x;
cin>>n>>x;
vector<long long>f(100000);
for(int i=0,a;i<n;i++){
cin>>a;
f[a]++;
}
long long ans=0;
for(int i=0,b;i<n;i++){
cin>>b;
int a=x-b;
if(a>0&&a<100000){
ans+=f[a];
}
}
cout<<ans<<'\n';
}