EQBEAUTY - Editorial

infinitepro · October 23, 2021, 1:19pm

PROBLEM LINK:

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

PROBLEM:

Beauty of an array is defined as the difference between the largest and smallest element in the array. An array is called good if its elements can be partitioned into two non-empty, disjoint arrays such that the beauties of both arrays are equal.

Given an array A of N integers. In one move, you may add or subtract any element by 1. Determine the minimum number of moves to make array A good.

EXPLANATION:

Sort array A in non-decreasing order. Then A_1\le A_2\le \dots \le A_N.

Say we have partitioned the elements of A (without making any updates to the elements) into two non-empty arrays B_1 and B_2 in some optimal fashion.
Now, we concern ourselves with applying the least number of moves on the elements of B_1 and B_2 to make their beauties equal.

Note: We assume both B_1 and B_2 have \ge 2 elements in them. The case where either contains exactly one element is tackled at the end.

Observation: It suffices to only apply moves on either B_1 or B_2.

Observation: It suffices to only increase/decrease the values of the largest/smallest elements of the array.

Thus, we can only keep one greatest and smallest element in each of B_1 and B_2, and safely discard the rest of the elements from them.
Let B_1 = [A_w,A_x]\ (w<x) and B_2 = [A_y, A_z]\ (y<z).

Observation: Either (but not both) of w or y is equal to 1.
Observation: Either (but not both) of x or z is equal to N.

Then, a bit of casework shows that the following are the only unordered possibilities for the elements of B_1 and B_2 (where 1<i<j<N) -

\begin{aligned} \bullet\quad &B_1 = [A_1, A_j],\;\; B_2 = [A_i, A_N]\\ \bullet\quad &B_1 = [A_1, A_N],\; B_2 = [A_i, A_j]\\ \bullet\quad &B_1 = [A_1, A_i],\;\; B_2 = [A_{i+1}, A_N] \end{aligned}

(Proof of why these are the only cases is mundane, and left to the reader as an exercise).

Now that we know what arrays B_1 and B_2 look like, we can emulate each of them and find the least possible moves required. For each of the above cases, iteratively try every valid value of A_i, and find the best value for A_j, to minimize the difference of the beauties.
This can be done efficiently using binary search (lower_bound to be precise), in O(\log N) for each valid value of A_i.

How?

We only discuss the first case; all other cases can be done similarly.

Say we have fixed the value of i (and are trying to find the best j). Then the difference of the beauties of B_1 and B_2 is equal to:

|(A_j-A_1)-(A_N-A_i)|\\ \implies |A_j-(A_1+A_N-A_i)|

Then, minimising the difference is equivalent to finding an A_j that is closest to the value A_1+A_N-A_i, which can be done by running a lower bound on A and finding the best value around it.

The case that that stumped many (me included!) is when B_1 or B_2 consisted of exactly 1 element. In this case, the beauty of that array always equals 0.
Therefore, we have to make the beauty of the other array (which consists of all but one elements of A) equal 0, by applying moves on its elements to make them all equal.

More formally, we need to apply the least number of moves on the array [A_1,\dots,A_{i-1},A_{i+1},\dots,A_N] to make all elements equal. The answer is then updated with the minimum of this value, over all i.
This is a slightly modified version of a classical problem, which can be solved efficiently in O(N) using suitable preprocessing!

TIME COMPLEXITY:

Sorting array A takes O(N\log N). Computing the 3 cases (mentioned in the editorial) takes O(3\cdot N\log N). Finally, computing the edge case takes O(N). The total time complexity is therefore:

O(N\log N+3\cdot N\log N+N)\approx O(N\log N)

per test case.

SOLUTIONS:

Editorialist’s solution can be found here

Experimental: For evaluation purposes, please rate the editorial (1 being poor and 5 excellent)

1
2
3
4
5

0 voters

nothing_123 · October 24, 2021, 9:09am

Hey I thought the case [A1,AN] [Ai , Aj] doesn’t need any checking from I to J since closest will always be A2 AN-1 , correct if wrong though thanks.

infinitepro · October 24, 2021, 9:12am

Yes, this works.
I didn’t want to handle this triviality in the editorial separately however, so I omitted mentioning it.

soumy_jain · October 24, 2021, 9:51am

I used the observation :
If A_{x} - A_{y} = A_{p} - A_{q} (A_{y} ≤ A_{ p} ) , then A_{x} - A_{p} = A_{y} - A_{q}
and all other elements can arranged accordingly which made my approach a greedy one.
Also, I handled the case differently where either of the set has only 1 element.

ll get(vector<ll> &v, ll k)
{
    ll n = v.size() - 1, c1 = 0, c2 = 0;
    ll x = v[n / 2 - 1 + k], y = v[n / 2 + k];
    for (int i = 0; i < n; i++)
    {
        c1 += abs(x - v[i + k]);
        c2 += abs(y - v[i + k]);
    }
    return min(c1, c2);
}

void work()
{
    ll n;
    cin >> n;
    vector<ll> v(n);
    multiset<ll> S;
    for (auto &i : v)
        cin >> i;
    if (n == 2)
        return void(cout << 0 << '\n');
    sort(v.begin(), v.end());
    for (int i = 1; i < n - 1; i++)
        S.insert(v[i]);
    ll ans = LLONG_MAX;
    ans = min(get(v, 0), get(v, 1));
    for (int i = 1; i < n - 1; i++)
    {
        S.erase(S.find(v[i]));
        ll e = v[0] + v[n - 1] - v[i];
        auto it = S.lower_bound(e);
        if (S.size())
        {
            if (it != S.end())
            {
                ans = min(ans, abs(*it - e));
            }
            if (it != S.begin())
            {
                it--;
                ans = min(ans, abs(*it - e));
            }
        }
        S.insert(v[i]);
    }
    cout << ans << '\n';
}

pks18 · October 24, 2021, 1:35pm

I didn’t quite get what you were trying to point out. Could you elaborate it with an example?

ssvb · October 24, 2021, 2:59pm

It is possible to use the two pointers technique to avoid binary search altogether. In this case everything has O(N) time complexity, except for the initial array sort operation.

Initially set j=2. Then iterate i through all values starting from N-1 and down to 2. Inside of each loop iteration, just keep incrementing j until it reaches the best value for the current i (instead of repeatedly doing binary search to find the best j for the current i as suggested by the editorial). My submission in D language is here.

As for the “B_1 or B_2 consisting of exactly 1 element” subproblem, I used a different geeksforgeeks link for that. It’s interesting that their ternary search code is incorrect, but their alternate solution from the same page for a sorted array does the job.

vishwajeet7381 · October 24, 2021, 6:38pm

Hey I did somewhat similar, bt getting WA. Can you or someone tell whats wrong in my approach, here’s the code:

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef pair<double, double> pd;

typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pi> vpi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<pll> vpll;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<pd> vpd;

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define FORb(i, a, b) for (int i = (a); i >= (b); i--)
#define trav(x, a) for (auto &x : a)
#define travc(x, a) for (auto const &x : a)

#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()

const int int_max = numeric_limits<int>::max();
const int int_min = numeric_limits<int>::min();
const ll ll_max = numeric_limits<ll>::max();
const ll ll_min = numeric_limits<ll>::min();
const int MOD = 1000000007;
const double PIE = 3.14;
const char nl = '\n';

void setIO(string name = "")
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    if (name.size())
    {
        freopen((name + ".in").c_str(), "r", stdin);
        freopen((name + ".out").c_str(), "w", stdout);
    }
}

int main()
{
    setIO();

    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        vll v(n);
        trav(x, v)
        {
            cin >> x;
        }
        sort(all(v));
        if (n == 2)
            cout << 0;
        else
        {
            ll i = n - 2, j = 1, ans = ll_max;
            while (i - j >= -1)
            {
                ll one = v[i] - v[0], two = v[n - 1] - v[j];
                if (i != j)
                    ans = min(ans, abs(one - two));
                if (one > two)
                    i--;
                else if (one < two)
                    j++;
                else
                {
                    if (i - 1 < 0 || j + 1 >= n)
                        break;
                    if (v[i] - v[i - 1] <= v[j + 1] - v[j])
                        i--;
                    else
                        j++;
                }
            }
            cout << ans;
        }
        cout << nl;
    }

    return 0;
}

/***Author: Vishwajeet Prasad***/

ssvb · October 24, 2021, 8:07pm

Your approach is generally correct, but your code doesn’t correctly handle the special case when B_1 or B_2 contain only one element. Consider the following input:

1
5
1 8 8 9 9

The split is B_1=[1], B_2=[8,8,9,9] and the correct answer is 2. Because two operations are needed to make all elements of B_2 equal.

And your code can be fixed by applying the following changes:

-            ll i = n - 2, j = 1, ans = ll_max;
-            while (i - j >= -1)
+            ll ans = min(minCostToMakeElementEqual(&v[0], n - 1),
+                         minCostToMakeElementEqual(&v[1], n - 1));
+            ll i = n - 2, j = 1;
+            while (i - j >= -1 && i >= 1 && j < n - 1)

sasta_achar · October 25, 2021, 11:03am

ll findCost(ll a, ll b, ll c, ll d) {
    return abs((b - a) - (d - c));
}
ll solve(vl &arr, int n) {
    if (n == 2) {
        return 0;
    }

    int l = 1, r = n - 2;

    ll cost = INT_MAX;

    int mid = n / 2;

    ll allMidSum = 0;
    fr(n, i) {
        allMidSum += abs(arr[i] - arr[mid]);
    }
    cost = min(cost, allMidSum);

    if (n % 2 == 0) {
        mid = (n / 2) - 1;
        allMidSum = 0;
        fr(n, i) {
            allMidSum += abs(arr[i] - arr[mid]);
        }
        cost = min(cost, allMidSum);
    }

    ll a = arr[0], b = arr[n - 1];

    while (l <= r) {
        if (l == r) {
            //a l-1, l b
            cost = min(cost, findCost(a, arr[l - 1], arr[l], b));

            //a l, l+1 b
            cost = min(cost, findCost(a, arr[l], arr[l + 1], b));
            break;
        }

        // a r l b
        cost = min(cost, findCost(a, arr[r], arr[l], b));

        if (cost == 0) return cost;

        if ((arr[r] - a) > (b - arr[l])) {
            --r;
        } else {
            ++l;
        }
    }

    return cost;
}

I am using a two pointer approach, i have also taken care of the single element issue but not sure why this is not passing ? Any clue why ? Or is my approach itself flawed ?