MINBEAUTY - Editorial

editorial
, , ,
1

PROBLEM LINK:

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

Author: anky_301
Testers: iceknight1093, rivalq
Editorialist: iceknight1093

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,

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
2

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

6 Likes
3

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
4

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
5

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

6

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

7

The mean is 26.33

8

test case were weak that time maybe

9

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

[My code] : CodeChef: Practical coding for everyone

10

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.

11

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

12

Hi. Where can I find the video editorial ?

13

if u sort it then median changed

14

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;
}