ABC7 - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

Sets

PROBLEM:

You’re given three arrays A, B, C all of length N.
You must create an array D such that D_i equals one of \{A_i, B_i, C_i\}.
Find the minimum possible value of \max(D) - \min(D) across all such arrays.

EXPLANATION:

We have two quantities to work with: \max(D) and \min(D).

Let’s try fixing them - say, we decide we want \max(D) = M.
Now, our goal is to minimize \max(D) - \min(D), so with the maximum fixed, clearly it’s optimal to have the minimum be as large as possible.

That is, for each index i, it’s optimal to choose the largest element among \{A_i, B_i, C_i\} that does not exceed M.
If for some i all three of A_i, B_i, C_i exceed M, no valid array D with \max(D) = M can exist - so we don’t need to even consider such a case.

This gives us a simple \mathcal{O}(N) algorithm to compute the optimal value of \min(D) once \max(D) is fixed.
There are at most 3N possible values of \max(D) at all, so we now have a solution that works in \mathcal{O}(N^2) time.
This is too slow, and needs to be optimized further.

To optimize this, observe that we can in fact reuse a fair bit of information.

Suppose we fix \max(D) = M, and then compute the necessary array D in linear time using our greedy idea.
Now look at what happens if we want \max(D) = M-1 instead.
Observe that the only values of D that will change at all (compared to \max(D) = M), are those for which we have D_i = M currently!
Everything else is already \le M-1, and so doesn’t need to be changed!

For the indices that do have \max(D) = M, we only need to change them to the next smaller value among \{A_i, B_i, C_i\}.

So, as long as we’re able to process such changes quickly, we actually do have a rather fast solution - after all, each index can be the target of a change at most two times (since the third time, there are no more remaining elements at that index.)
This means we only have to deal with at most 2N changes.

Let’s now figure out what data structure is necessary to support what we want to do.
Let S be our data structure.
Then, S should support the following operations quickly:

  • Insertion and deletion of elements (we need to delete occurrences of M, and insert the next smaller element).
  • Return the minimum and maximum elements (to tell us the current value of \min(D) and \max(D)).

These can be accomplished with the help of a sorted set (std::set in C++, TreeSet in Java, unfortunately no equivalent inbuilt in Python.)

That is, we quite simply have the following algorithm:

  • Let S be a set of elements.
    Initially, insert \max(A_i, B_i, C_i) into S, for each index i.
  • Then, repeatedly do the following:
    • Let M = \max(S).
    • Remove all occurrences of M from S.
    • For each index such that the maximum was removed, insert the next-smaller element into S.
    • Then, update the answer with \max(S) - \min(S).

This will take \mathcal{O}(N\log N) time, because as noted above we have only 2N possible updates.

One thing to be careful about is the fact that there may be duplicate elements from different indices - so make sure to handle that properly, either by using a multiset or by storing pairs of (element, index).

TIME COMPLEXITY:

\mathcal{O}(N\log N) 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; cin >> n;
        vector<array<int, 3>> a(n);
        vector ptr(n, 0);
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < 3; ++j) {
                cin >> a[i][j];
            }
            ranges::sort(a[i]);
            ranges::reverse(a[i]);
        }

        set<array<int, 2>> cur;
        for (int i = 0; i < n; ++i) {
            cur.insert({a[i][0], i});
        }

        int ans = 1e9;
        while (size(cur) == n) {
            auto [mx, i] = *rbegin(cur);
            auto [mn, j] = *begin(cur);
            ans = min(ans, mx - mn);

            cur.erase({mx, i});
            ++ptr[i];
            if (ptr[i] < 3) cur.insert({a[i][ptr[i]], i});
        }
        cout << ans << '\n';
    }
}
1 Like
2

we can use 2 pointers as well. make a sorted array of values with their indices paired and then we need subsegments such that all n indices exist

1 Like
3

Can you elaborate? @wasifshahzad22

4

What about using sliding window?

5

yep I think that’s an easier approach

6

Here is a simpler two pointer implementation:

void prateek() {
   rdLL(n);

   vector<pr> v;
   for (ll i=0; i<n; i++) {
      rdLL(ai); rdLL(bi); rdLL(ci);
      v.pb({ai, i});
      v.pb({bi, i});
      v.pb({ci, i});
   }

   sort(v.begin(), v.end());

   // dbgVecPr(v);

   ll cnt = 0;
   ll l = 0, r = -1;
   ll ans = LLONG_MAX;
   vector<ll> freq(n, 0);

   while (l < 3*n) {
      while (r+1 < 3*n && cnt < n) {
         r++;
         ll idx = v[r].second;
         freq[idx]++;
         if (freq[idx] == 1) cnt++;
      }

      if (cnt == n) ans = min(ans, v[r].first-v[l].first);

      // cout << l << cmsp << r << arw << ans << nl;

      if (l > r) {
         l++;
         r = l-1;
      }
      else {
         ll idx = v[l].second;
         freq[idx]--;
         if (freq[idx] == 0) cnt--;
         l++;
      }
   }

   put(ans);
}