# PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Contest: Division 3

Contest: Division 4

* Author:* anky_301

*iceknight1093, rivalq*

**Testers:***iceknight1093*

**Editorialist:**# DIFFICULTY:

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,

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)
```