P6209 - Editorial

editorial
, , , ,
1

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:

Greedy, sorting

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.

EXPLANATION:

Let’s recall the solution to the easier version with N = M (which can be read here).

If some element x has a total frequency \gt N, the optimal solution is to pair every non-x with a copy of x.
If every element has a frequency that’s \le N, the optimal solution was to simply sum up both arrays.

Next, we need to generalize the above idea to arbitrary lengths N and M.
For now, suppose N \ge M (if not, swap the arrays).

Once again analyzing the situation where we’re ‘forced’ to make pairs of equal elements, it can be seen that this happens exactly when some element appears \gt N times in total across both arrays (recall that N here is the larger length.)

So, suppose some x does appear \gt N times (there can only be one such element.)
It’s easy to see that again, the best case for us is just pairing every element that’s not x with a copy of x.
Thus, in this case, the answer is just the sum of all elements not equal to x, plus x multiplied by the count of elements not equal to x.

That leaves us with the case where all frequencies are ‘small’.
Here, in the N = M case we were able to pair of all N elements.
When N \gt M, it’s clear that the best we can do is make M pairs (since the second array will then become empty).
In fact, the exact same construction as for N = M works to form M pairs here: if some element appears exactly N times, then all elements of B can be paired up with a different element of A; and if all elements appear \lt N times, just take a random element of B and find a pair for it in A, and solve for (N-1, M-1) recursively.

That only leaves us with the task of optimizing the sum of the chosen elements.
However, all the understanding we have this far makes that not too hard to do.

First, all the M elements of B will be chosen; so take them.
Next, we need to choose M elements from A to match.
Ideally, we do this greedily: choose elements of A from largest to smallest.
However, to ensure that we can in fact make M pairs of elements, we must ensure that the overall frequency of any chosen element doesn’t exceed M.

So, for each element of A in descending order, choose it if the corresponding frequency will remain \le M, and skip it otherwise.

TIME COMPLEXITY:

\mathcal{O}((N+M)\log(N+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;

        if (n < m) {
            swap(n, m);
            swap(a, b);
        }

        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 else can be paired
                for (int el : a) {
                    if (el != x) ans += el + x;
                }
                for (int el : b) {
                    if (el != x) ans += el + x;
                }
                return ans;
            }

            freq.clear();
            for (int x : b) {
                ++freq[x];
                ans += x;
            }

            ranges::sort(a); ranges::reverse(a);
            int taken = 0;
            for (int x : a) {
                if (freq[x] == m or taken == m) continue;
                ans += x;
                ++taken;
                ++freq[x];
            }
            return ans;
        };
        cout << solve() << '\n';
    }
}
1 Like