 # MINBEAUTY - Editorial

Author: anky_301
Testers: iceknight1093, rivalq
Editorialist: iceknight1093

TBD

# PREREQUISITES:

Two pointers/binary search

# PROBLEM:

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.

# EXPLANATION:

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

Then,

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.

# TIME COMPLEXITY

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

# CODE:

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

int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#ifndef ONLINE_JUDGE
freopen("8.in", "r", stdin);
freopen("88.out", "w", stdout);
#endif
int test;
cin >> test;
while (test--)
{
int n;
cin >> n;
vector<int>v(n);
for(int i = 0;i<n;i++){
cin>>v[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);
}
cout<<result<<'\n';
}

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))
print(ans)

1 Like

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

6 Likes

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.
@boseisback

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? 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

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:

#include<bits/stdc++.h>
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() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
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;
cur++;
}
ans = min(ans, chk(a, i, prev, k));
ans = min(ans, chk(a, i, cur, k));
}
}
cout << ans << "\n";
}
return 0;
}