Most Frequent Pair Products
National Olympiad — National round (2017 season)
Submission name: pairs.cpp
Problem summary
For all original index pairs i<j, find the largest multiplicity M of a product a[i]a[j]. Report the P distinct products attaining M, with each product’s lexicographically smallest index pair. Print at most the first 100 product records, but report the full P.
Source clarification. This 2017 National-round task was shared by Groups C and D; its existing permanent URL is retained.
Input
N followed by N positive integers.
Output
M on the first line, P on the second, then min(P,100) lines product i j in increasing product order. Indices are 1-based.
Constraints
4 ≤ N ≤ 2000; 1 ≤ a[i] < 10^8.
Worked example
Input and output for the worked example discussed below.
Input
7 5 3 2 2 3 5 4
Output
4 3 6 2 3 10 1 3 15 1 2
Solution analysis
- Enumerate every i<j pair, storing its 64-bit product and the original indices. At most 1,999,000 records are needed. Do not sort away the original index identity before constructing representatives.
- Sort records by product, then first index, then second index. Equal products form contiguous runs; a run’s length is its frequency, and its first record automatically contains the lexicographically smallest index pair.
- Scan runs, maintaining the best frequency, full number of winning products, and at most 100 representatives. A new larger frequency discards all previous winners. An equal frequency increments P even after the representative list is full.
- For [5,3,2,2,3,5,4], products 6,10,15 each occur four times. Their earliest pairs are respectively (2,3),(1,3),(1,2), producing the sample. Equal values at different positions still make distinct index pairs.
Why it works
Enumeration produces each permitted index pair exactly once. Sorting groups exactly equal products and puts the smallest index pair first. The scan invariant retains precisely the products of maximum multiplicity encountered so far. Because products are visited in increasing order, the retained first 100 final winners have the required order.
Watch out. Products can approach 10^16, requiring long long. Count index pairs rather than distinct value pairs. Only the output list is capped at 100, not P. Reset both the count and saved list at a new maximum.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
struct ProductPair{
long long product;
int first;
int second;
};
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin>>n;
vector<long long>values(n+1);
for(int i=1;i<=n;i++){
cin>>values[i];
}
vector<ProductPair>pairs;
pairs.reserve(n*(n-1)/2);
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
pairs.push_back({values[i]*values[j],i,j});
}
}
sort(pairs.begin(),pairs.end(),[](const ProductPair&a,const ProductPair&b){
if(a.product!=b.product){
return a.product<b.product;
}
if(a.first!=b.first){
return a.first<b.first;
}
return a.second<b.second;
});
int maximum=0;
int productCount=0;
vector<ProductPair>winners;
for(int start=0;start<int(pairs.size());){
int end=start+1;
while(end<int(pairs.size())&&pairs[end].product==pairs[start].product){
end++;
}
int frequency=end-start;
if(frequency>maximum){
maximum=frequency;
productCount=0;
winners.clear();
}
if(frequency==maximum){
productCount++;
// Sorting indices makes the first pair the required representative.
if(winners.size()<100){
winners.push_back(pairs[start]);
}
}
start=end;
}
cout<<maximum<<'\n'<<productCount<<'\n';
for(const ProductPair&winner:winners){
cout<<winner.product<<' '<<winner.first<<' '<<winner.second<<'\n';
}
return 0;
}