JUICEQ - Editorial

editorial
, , ,
1

PROBLEM LINK:

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

Author: iceknight1093
Tester: raysh07
Editorialist: iceknight1093

DIFFICULTY:

Easy

PREREQUISITES:

None

PROBLEM:

There are N glasses of juice in a row, initially the i-th glass has A_i units.

You can perform the following operation:

  • Choose a glass, pour an integer amount of juice from it to each of its neighbors (some can remain), and then remove the glass.

Find the minimum number of operations needed to make all the glasses have the same amount of juice.

EXPLANATION:

Letā€™s try to solve a more restricted version of the problem first: if we wanted to make all remaining glasses have a value of exactly X, how many operations do we need at minimum?

To answer this, letā€™s look at the glasses that remain in the end.
Suppose we want to have glasses i_1, i_2, \ldots, i_K remain, where i_1 \lt i_2 \lt\ldots\lt i_K.

First, note that each of these glasses must satisfy A_{i_j} \leq X initially, because we cannot lower the amount of juice in a glass (without removing it entirely).

Now, consider the glasses before i_1, i.e. 1, 2, 3, \ldots, i_1 - 1.
All of the juice in these glasses can be transferred to glass i_1, via the following sequence:

  • Pour everything from 1 into 2.
  • Then pour everything from 2 (which includes what was initially in glass 1) into 3.
    \vdots
  • Pour everything from i_1 - 1 (which now includes everything before it) into i_1.

There are now two possibilities:

  1. A_1 + A_2 + \ldots + A_{i_1} \geq X
    That is, there is enough juice to the left of i_1 to ensure that glass i_1 ends up with X.
    Here, observe that itā€™s impossible to transfer any quantity from the left of i_1 to its right, since doing so would have to involve removing i_1 (which we arenā€™t doing).
    So, any excess juice is simply wasted.
  2. A_1 + \ldots + A_{i_1} \lt X
    Here, glass i_1 still isnā€™t satisfied after using up everything to its left.
    So, we have no choice but to use some glasses from its right now.
    However, observe that we can only use glasses between i_1 and i_2: anything to the right of i_2 cannot cross over i_2 to contribute to i_1.
    On the other hand, we can use any amount of juice from between i_1 and i_2, while ensuring that the remaining part can always go towards i_2 instead - a simple construction is to ā€˜mergeā€™ all the glasses between them into a single glass, then pour exactly as much as needed into i_1 and the remainder (or however much is needed) into i_2.
    So, in this case, as long as A_1 + A_2 + \ldots + A_{i_2-1} \ge X, itā€™s still possible to satisfy glass i_1.
    After this, weā€™ll have an excess of A_1 + A_2 + \ldots + A_{i_2-1} - X to give to i_2, if needed.

Observe that once i_1 has been satisfied, the exact same analysis applies to i_2 as well: there is some remaining juice to its left that can only go to it; and if this is not enough weā€™ll need to take some from between i_2 and i_3, and so on.

So, if we know the indices i_1, i_2, \ldots, i_K, itā€™s quite easy to check if exactly these indices can be given the final value X.

Clearly, itā€™s not possible to check for all possible choices of final indices.
However, here we can be greedy with our choice.

Observe that itā€™s always ideal to leave as much of the juice as possible for the next chosen index.
With that in mind, letā€™s try to find the optimal value for index i_1.
There are two possibilities:

  1. A_1 \geq X.
    Here, observe that any index we choose as i_1 will be valid (as long as A_{i_1} \leq X is satisfied, of course).
    This is because there is automatically enough juice to the left of i_1 to make it reach X.
    So, here we can simply choose the smallest index such that A_{i_1} \leq X, which leaves the most possible for the remaining indices.
  2. A_{1} \lt X.
    Here, we instead need to keep including elements in the prefix till we reach a sum of at least X.
    However, we can stop the instant the sum reaches X: after all, we already have an element smaller than X, so we can just choose i_1 = 1, make the quantity here X, and save the rest for future indices.

Extending this idea further, we obtain the following greedy algorithm: find the smallest prefix that both has sum \ge X and some element \le X, choose the leftmost element \le X in this prefix as the final container, and give it the value X.
This will leave some juice which can be used with the remaining glasses; so add that in and continue.

This greedy algorithm runs in \mathcal{O}(N) time and gives us the maximum possible number of glasses that can have final value exactly X.

Now that we have a reasonably fast check function, we need some candidates for which values to check for.
Here, itā€™s not hard to see that it suffices to check for only element of A itself: if the final quantity in all the glasses is not an existing value, it means we increased the values of all remaining glasses - but since weā€™re allowed to ā€œwasteā€ juice, we the quantities in all glasses can be reduced by 1 (by just reducing by 1 the amount poured into each glass, at some point) and weā€™ll still have a valid solution. Repeat this reduction and we eventually reach a state where some glass had nothing poured into it, proving the claim.

So, we have N candidates for the value X, and each one is processed in \mathcal{O}(N) time, for \mathcal{O}(N^2) overall.
This is fast enough for the constraints.

TIME COMPLEXITY:

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

CODE:

Editorialist's code (C++) 
// #include <bits/allocator.h>
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "bits/stdc++.h"
using namespace std;
using ll = long long int;
mt19937_64 RNG(chrono::high_resolution_clock::now().time_since_epoch().count());

int main()
{
    ios::sync_with_stdio(false); cin.tie(0);

    int t; cin >> t;
    while (t--) {
        int n; cin >> n;
        vector a(n, 0);
        for (int &x : a) cin >> x;

        auto best = [&] (int x) {
            ll left = 0, right = 0;
            int ans = 0, small = -1;
            for (int i = 0; i < n; ++i) {
                if (small == -1) {
                    if (a[i] <= x) small = i;
                    else left += a[i];
                }
                else right += a[i];

                if (small == -1) continue;
                if (left + right + a[small] >= x) {
                    ++ans;
                    if (a[small] + left >= x) left = right;
                    else left = right - (x - a[small] - left);
                    small = -1;
                    right = 0;
                }
            }
            return ans;
        };

        int ans = 0;
        for (int x : a)
            ans = max(ans, best(x));
        cout << n-ans << '\n';
    }
}
1 Like
2

good explanation