MINBEAUTY - Editorial


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

Author: anky_301
Testers: iceknight1093, rivalq
Editorialist: iceknight1093




Two pointers/binary search


Given an array A of N integers, choose a subsequence S of length 3 such that 3\cdot |\text{mean}(S) - \text{median}(S)| is minimized.


Suppose we choose the three elements A_i, A_j, A_k. Let A_i \leq A_j \leq A_k.


3\cdot |\text{mean} - \text{median}| = 3\cdot \left| \frac{A_i + A_j + A_k}{3} - A_j\right| \\ = |A_i + A_j + A_k - 3A_j| = |A_i + A_k - 2A_j|

So, our objective is to minimize |A_i + A_k - 2A_j|, where A_i \leq A_j \leq A_k.

First, sort A. Notice that N \leq 5000 means we can afford \mathcal{O}(N^2) time; which means we can fix two out of A_i, A_j, A_k and try to find the optimal value of the third.

So, let’s fix i and k, and try to find the best value of j.
Note that we want A_j to be such that |A_i + A_k - 2A_j| is as small as possible.
In other words, 2A_j should be as close to A_i + A_k as possible; equivalently, A_j should be close to \frac{A_i + A_k}{2}.

We have a sorted list, and we’d like to find the element in it closest to a given value.
How to do this? Binary search!

Simply binary search on A to find the smallest A_j that is \geq \frac{A_i + A_k}{2}, and the largest A_j that is \leq \frac{A_i+A_k}{2}.
The optimal j for this fixed i and k will be one of these two; so try both and take the best of them.
Note that you need to ensure that i, j, k are distinct.

Do this for every (i, k) pair and take the minimum answer among everything obtained, for \mathcal{O}(N^2 \log N) time.
It’s also possible to achieve \mathcal{O}(N^2) by using two pointers, utilizing the fact that for a fixed i, as k increases the optimal position of j will also increase.


\mathcal{O}(N^2) per test case.


Setter's code (C++)
#include <bits/stdc++.h>
using namespace std;

int main()
    freopen("8.in", "r", stdin);
    freopen("88.out", "w", stdout);
    int test;
    cin >> test;
    while (test--)
        int n;
        cin >> n;
        for(int i = 0;i<n;i++){
        sort(v.begin(), v.end());
        int result = INT_MAX;
        for(int i = 1;i<n-1;i++){
            int median = v[i];
            int l = 0;
            int r = n-1; 
            int minDiff = INT_MAX;
            while (l<r and l<i and r>i){
                int sum = (v[l] + v[i] + v[r]);
                int dif = abs(sum - 3*median);
                // cout<<l<<" "<<i<<" "<<r<<" "<<sum<<" "<<median<<" "<<dif<<" "<<minDiff<<endl;
                if(dif <= minDiff) minDiff = dif ;

                if(minDiff==0) break;
                if(sum>3*median) r--;
                else             l++;
            result = min(result , minDiff);

    cerr << "\nTime elapsed: " << setprecision(6) << 1000.0 * clock() / CLOCKS_PER_SEC << "ms\n";

    return 0;
Editorialist's code (Python)
for _ in range(int(input())):
	n = int(input())
	a = sorted(list(map(int, input().split())))
	ans = 10**10
	def f(i, j, k):
		return abs(a[i] + a[k] - 2*a[j])

	for i in range(n):
		j = i+1
		for k in range(i+2, n):
			while j+1 < k:
				if f(i, j, k) > f(i, j+1, k): j += 1
				else: break
			ans = min(ans, f(i, j, k))
1 Like

But it calls for subsequence, and you are sorting so how it’s correct then?


You are selecting a subsequence of length 3 , and then to find the median u need to sort it right?
Thats we firstly sorted the array so that u dont need to resort the 3 length subsequence again.

1 Like

If input array is {72 ,7 ,0} then how is the expected output 58 and not 57. Here the mean is 26 and median is 7, giving 19*3 i.e 57 as answer.

1 Like

How the educator in the video solution was able to correctly submit an O(N^3) solution? :exploding_head:

I exactly copied his solution in the IDE and still its showing TLE how is it even possible? Please someone have a look.

The mean is 26.33

test case were weak that time maybe

Hi, can any one pls tell me why ‘fixing j’ solution not working stucking at tc 7

[My code] : CodeChef | Competitive Programming | Participate & Learn

During the testing period we increased the time limit for a while because we were changing constraints, probably he got AC back then and didn’t realize it wasn’t actually intended.

I’ve informed the team, it’ll maybe be updated.

My video explantion :- MINBEAUTY Codechef COOK OFF FEBRUARY 2023 EXPLAINED - YouTube
for O(n^2 log n)

Hi. Where can I find the video editorial ?

if u sort it then median changed

My clean code:

using namespace std;
#define int long long int
const int inf = 1e18;

int chk(vector<int> &a, int i, int j, int k)
   return abs(2 * a[j] - a[i] - a[k]);
int32_t main() {
   freopen("input.txt", "r", stdin);
   freopen("output.txt", "w", stdout);
   int tt;
   cin >> tt;
   while (tt--)
       int n;
       cin >> n;
       vector<int> a(n);
       for (int i = 0; i < n; ++i)
           cin >> a[i];
       sort(a.begin(), a.end());
       int ans = inf;
       for (int i = 0; i < n; ++i)
           int prev = i + 1, cur = i + 1;
           for (int k = i + 2; k < n; k++)
               while (cur + 1 < k && chk(a, i, prev, k) >= chk(a, i, cur + 1, k))
                   prev = cur;
               ans = min(ans, chk(a, i, prev, k));
               ans = min(ans, chk(a, i, cur, k));
       cout << ans << "\n";
   return 0;