PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: satyam_343
Tester: kingmessi
Editorialist: iceknight1093
DIFFICULTY:
Easy
PREREQUISITES:
Sorting or maps
PROBLEM:
You’re given two arrays A and B, of lengths N and M respectively.
You can do the following:
- Choose elements X \in A and Y\in B such that X\ne Y.
- Add (X+Y) to your score.
- Delete one copy of X from A and one copy of Y from B.
Find the maximum possible score you can obtain.
In this version, N = M.
EXPLANATION:
Our goal is to essentially pair up each element of A with a different element of B.
The best-case scenario is when we can make N pairs, thus involving every possible element across both arrays.
Let’s understand when this is possible.
Intuitively, if some element appears ‘too many’ times, we won’t be able to avoid making pairs of copies of that element (which is not allowed).
In particular, if there exists an element x that appears more than N times in total (that is, combined across A and B), then there is no way to avoid pairing x with itself (after all, if x isn’t paired with itself, then we can use up at most N copies of x since each pair has at most one copy).
For example, if A = [1, 1, 2] and B = [3, 1, 1], then 1 appears a total of 4 times across A and B, which is larger than N = 3.
In this case, it’s impossible to avoid making a pair of 1 with itself.
So, we have two cases: either some element appears \gt N times in total; or every element appears \le N times in total.
Let’s analyze them separately.
First, suppose some x appears \gt N times in total.
Note that there will be exactly one such x, since there are only 2N elements.
Let K denote the number of times x appears.
Then, we can make (2N - K) pairs of different elements - the construction is simple, simply pair each non-x element with a copy of x from the opposite array.
It’s easy to see that this is also optimal in terms of sum: every element other than x gets used up, and that’s also the maximum number of times we can use x anyway.
Next, suppose every element appears \le N times in total.
Here, we can in fact use up all N elements to form pairs!
A simple recursive construction is as follows:
- Suppose some element appears exactly N times.
Let this element be x. Then, each element that’s not x can be paired up with a copy of x from the opposite array; and this uses up all 2N elements. - Otherwise, all elements appear \lt N times.
Take a random element X of A, and pair it with a random element of B that’s not equal to X (which will always exist, since we’re in the case where everything appears \lt N times).
Now there are N-1 elements left in both arrays, and all remaining elements have total frequency \le N-1, so solve recursively.
So, the case of both arrays having equal length N turns out to be quite easy to solve: if some element appears \gt N times, the optimal solution is to repeatedly pair off copies of this element; and otherwise it’s possible to pair off all N elements from both arrays.
The only thing that needs to be done quickly is to compute the frequencies of elements, which can be done using a map/dictionary, or sorting + binary search/two pointers.
TIME COMPLEXITY:
\mathcal{O}(N\log N + M\log M) per testcase.
CODE:
Editorialist's code (C++)
// #include <bits/allocator.h>
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "bits/stdc++.h"
using namespace std;
using ll = long long int;
mt19937_64 RNG(chrono::high_resolution_clock::now().time_since_epoch().count());
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
int t; cin >> t;
while (t--) {
int n, m; cin >> n >> m;
vector a(n, 0), b(m, 0);
for (int &x : a) cin >> x;
for (int &x : b) cin >> x;
auto solve = [&] () {
map<int, int> freq;
for (int x : a) ++freq[x];
for (int x : b) ++freq[x];
ll ans = 0;
for (auto [x, y] : freq) {
if (y <= n) continue;
// everything other than x can be paired with x
for (int el : a) {
if (el != x) ans += el + x;
}
for (int el : b) {
if (el != x) ans += el + x;
}
return ans;
}
// all elements can be paired -> return sum of both arrays
return accumulate(begin(a), end(a), 0ll) + accumulate(begin(b), end(b), 0ll);
};
cout << solve() << '\n';
}
}