Equal Maximum and Minimum
Autumn Tournament (2025)
Submission name: minmax.cpp
Problem summary
Two players each choose an unordered pair of distinct positions. The same position may belong to both players’ pairs. Count the ordered choices of the two pairs for which the first pair’s maximum equals the second pair’s minimum.
Input
n, followed by n array values.
Output
The number of valid choices.
Constraints
1 ≤ n ≤ 200000; 1 ≤ values ≤ 1000000000; the answer is guaranteed to fit in long long.
Worked example
Original statement sample.
Input
3 1 2 1
Output
3
Solution analysis
- Group equal values after sorting. Suppose value x occurs c times, with L values smaller than x and G values larger. A pair with maximum exactly x either uses one x and one smaller value (cL choices), or two x values (c(c−1)/2 choices).
- Similarly a pair with minimum exactly x has cG+c(c−1)/2 choices. Multiply these two counts because the players choose independently and sharing positions is allowed. Sum the products over distinct x.
- For [1,2,1], x=1 has one possible maximum-pair (the two ones), and three possible minimum-pairs. Its contribution is 3. Value 2 has no possible minimum-pair, so the total remains 3.
Why it works
Every valid choice has one unique common extremal value x. The two formulas enumerate every pair with that extremum exactly once. Independent multiplication is valid even for overlapping pairs; summing disjoint extremal-value cases counts all valid choices.
Watch out. The players’ pairs may overlap: do not subtract shared indices. Use long long before multiplying. The source guarantee excludes inputs whose true answer would overflow long long.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin>>n;
vector<int>values(n);
for(int&value:values){
cin>>value;
}
sort(values.begin(),values.end());
long long answer=0;
for(int left=0;left<n;){
int right=left;
while(right<n&&values[right]==values[left]){
right++;
}
long long count=right-left;
long long equalPairs=count*(count-1)/2;
long long maximumPairs=count*left+equalPairs;
long long minimumPairs=count*(n-right)+equalPairs;
// Pair choices are independent, including overlapping positions.
answer+=maximumPairs*minimumPairs;
left=right;
}
cout<<answer<<'\n';
}