Sum of Pair Minima
National Olympiad — Municipal round (2025 season)
Submission name: sumin.cpp
Problem summary
For an array a of n positive integers, compute the sum of min(a[i],a[j]) over all pairs i<j. Print the exact integer.
Input
n followed by n array elements.
Output
The exact sum of pair minima.
Constraints
1 ≤ n ≤ 10⁶; 1 ≤ a[i] ≤ 10⁹.
Worked example
An independently prepared example for this explanation.
Input
10 3 1 4 1 5 9 2 6 5 3
Output
111
Solution analysis
- Reordering the elements does not change the collection of unordered pairs. Sort the values increasingly. At sorted index i, the value is a minimum for each pair with one of the n−1−i later values, including ties.
- Thus the answer is the sum of a[i](n−1−i). In the example the sorted array is 1,1,2,3,3,4,5,5,6,9. Its contributions are 9,8,14,18,15,16,15,10,6,0, totaling 111.
- The largest possible answer is 10⁹·n(n−1)/2, which exceeds a signed 64-bit integer. Each individual contribution fits, however. Accumulate the result in two base-10⁹ limbs: keep the low limb reduced modulo 10⁹, carry into the high limb, and print the low limb padded to nine digits whenever the high limb is nonzero.
Why it works
Every pair of sorted positions has a unique earlier index i and its minimum equals a[i]. The contribution formula therefore counts every pair exactly once. The two-limb addition maintains answer = high·10⁹+low with 0≤low<10⁹ after every contribution, so it preserves the exact sum without overflow.
Watch out. Do not use a 64-bit accumulator for the full result. Equal values still form distinct position pairs. For n=1 the answer is zero.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iomanip>
#include<iostream>
#include<vector>
// Algorithm: Reordering the elements does not change the collection of unordered pairs.
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin>>n;
vector<long long>values(n);
for(long long&value:values){
cin>>value;
}
sort(values.begin(),values.end());
const long long base=1000000000;
long long high=0;
long long low=0;
for(int i=0;i<n;++i){
long long contribution=values[i]*(n-1-i);
high+=contribution/base;
low+=contribution%base;
high+=low/base;
low%=base;
}
if(high!=0){
cout<<high<<setw(9)<<setfill('0')<<low<<'\n';
}
else{
cout<<low<<'\n';
}
}