Most Frequent Pair Sum
National Olympiad — National round (2022 season)
Submission name: pairs.cpp
Problem summary
Given N positive integers, consider the sums A[i]+A[j] for all index pairs i<j. Output the most frequent sum, breaking ties by the smaller sum. Equal input values at different positions are distinct choices.
Input
N followed by the N values.
Output
The smallest sum among those with maximum frequency.
Constraints
1 < N < 35,000; 0 < values < 25,000.
Worked example
An independently prepared example for this explanation.
Input
4 1 2 3 1
Output
3
Solution analysis
- Count how often each value occurs. Instead of enumerating every pair of positions, enumerate pairs of distinct values x<y and add count[x]·count[y] to the frequency of x+y.
- For equal-value pairs x=x, add count[x]·(count[x]−1)/2 to the frequency of 2x. Keep a list of present values so absent values cause no pair iterations.
- For 1,2,3,1, the value frequencies are 2,1,1. Sum 2 occurs once; sum 3 occurs twice from pairing either 1 with 2; sum 4 occurs twice from pairing either 1 with 3; sum 5 occurs once. Sums 3 and 4 tie, so output 3.
Why it works
Every index pair either has equal values, counted by the binomial coefficient, or has distinct values x<y, counted by the product of their independent occurrence counts. These cases are disjoint and exhaustive, giving exact sum frequencies. Scanning sums increasingly and updating only on strict improvement selects the smallest maximum.
Watch out. Do not count ordered index pairs. Equal values require combinations, not count². Preserve the smaller sum on a tie.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
const int limit = 25000;
int n;
cin >> n;
vector<long long> count(limit, 0);
for (int i = 0; i < n; i++) {
int value;
cin >> value;
count[value]++;
}
vector<int> values;
for (int value = 1; value < limit; value++) {
if (count[value] > 0) {
values.push_back(value);
}
}
vector<long long> sumCount(2 * limit, 0);
for (int i = 0; i < static_cast<int>(values.size()); i++) {
int x = values[i];
// Equal-value choices use combinations, not ordered pairs.
sumCount[2 * x] += count[x] * (count[x] - 1) / 2;
for (int j = i + 1; j < static_cast<int>(values.size()); j++) {
int y = values[j];
sumCount[x + y] += count[x] * count[y];
}
}
int answer = 2;
for (int sum = 3; sum < 2 * limit; sum++) {
if (sumCount[sum] > sumCount[answer]) {
answer = sum;
}
}
cout << answer << '\n';
}