MINMAXARR - Editorial

PROBLEM LINK:

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

Author: tausif_539
Testers: iceknight1093, tabr
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

Prefix sums

PROBLEM:

Given an array A, in one move you can pick an integer X and an index 1 \leq i \lt N, and add X to A_i while subtracting X from A_{i+1}.
The array elements must always remain non-negative.

What’s the smallest possible value of \max(A)?

EXPLANATION:

When dealing with operations that affect adjacent elements in terms of adding/subtracting, it’s often useful to see what happens to the prefix sums of the array.

So, let P be the prefix sum array of A, i.e, P_i = A_1 + A_2 + \ldots + A_i.

Note that performing an operation on indices (i, i+1) with X leads to the following changes:

  • For j \lt i, P_j remains the same.
  • P_i increases by X.
  • For j \gt i, P_j remains the same.

So, we can essentially increase some element of P (except P_N) by as much as we like.
The only constraint is that P must always be sorted in ascending order, since this is what it means for A to have all non-negative elements.

This immediately allows us to binary search for the answer.

Suppose we want to check if the maximum element can be made \leq x.
This can happen if and only if P_i \leq i\cdot x for every i from 1 to N.

Why?

Suppose P_i \gt i\cdot x.
P_i is the sum of i integers, so by the pigeonhole principle at least one of them must be \gt x.

Since we aren’t allowed to decrease P_i, no matter how we perform operations we’re always going to have an element \gt x, so the maximum cannot be made \leq x.

Conversely, suppose P_i \leq i\cdot x for every i.
Then, perform operations as follows to obtain a valid array:

  • For each i from N-1 down to 1, set P_i = \min(P_{i+1}, i\cdot x).

This ensures two things:

  • P_i is kept sorted (since we ensure P_i \leq P_{i+1} for every i)
  • P_{i+1}-P_i \leq x; i.e, A_{i+1} \leq x.

So, every array element is \leq x, and so the maximum is \leq x.

This check can be made in \mathcal{O}(N) time, giving a solution in \mathcal{O}(N\log{10^9}).

In fact, analyzing this solution a bit gives an even simpler approach.

P_i \leq i\cdot x means that \frac{P_i}{i} \leq x.
Clearly, the only limiting factor here is the largest value of \frac{P_i}{i}, since if it satisfies the inequality, so will everything else.
Thus, the answer is simply the largest value of \displaystyle \left\lceil \frac{P_i}{i} \right\rceil across all i (where we take the ceiling because the answer is an integer).

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Setter's code (C++)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define kuchh endl
/*************** JUST IGNORE THIS ******* */

// constants

const double pi = 3.141592653589;
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
/*
  const int dx[] = {-1,-1,-1,0,0,1,1,1};
  const int dy[] = {-1,0,1,-1,1,-1,0,1};
*/
const int md = 1e9 + 7;
const int INF = 1e9 + 13;
// macros
#define dis(doo) cout << doo << endl
#define zz dis("Yes")

#define kk dis("No")
#define srt(v) sort(v.begin(), v.end())
#define grtsrt(v) sort(v.begin(), v.end(), greater<ll>())
#define mnv(v) *min_element(v.begin(), v.end())
#define mxv(v) *max_element(v.begin(), v.end())
#define rep(i, j) for (int i = 0; i < j; i++)
#define rrep(i, j) for (int i = j - 1; i >= 0; i--)
#define all(x) x.begin(), x.end()
#define fast_io                     \
  ios_base::sync_with_stdio(false); \
  cin.tie(NULL);

#ifndef ONLINE_JUDGE
#define debug(maxii)       \
  cerr << #maxii << " : "; \
  _print(maxii);           \
  cerr << endl;
#else
#define debug(maxii)
#endif

void _print(int v)
{
  cerr << v;
}
void _print(ll v) { cerr << v; }
void _print(string v) { cerr << v; }
void _print(char v) { cerr << v; }
void _print(double v) { cerr << v; }
void _print(float v) { cerr << v; }

void init_code()
{
  fast_io;
#ifndef ONLINE_JUDGE

  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
  freopen("error.txt", "w", stderr);

#endif // ONLINE_JUDGE
}

/*************** CODE STARTS FROM HERE ****************/

void solve()
{

  int n;
    cin >> n;
    vector<int> v(n);

    for (int i = 0; i < n; i++)
    {
      cin >> v[i];
    }

    vector<int> pref(n);

    pref[0] = v[0];
    int ans = pref[0];

    for (int i = 1; i < n; i++)
    {
      pref[i] = pref[i - 1] + v[i];

      if (pref[i] % (i + 1))
      {
        ans = max(pref[i] / (i + 1) + 1, ans);
      }
      else
        ans = max(pref[i] / (i + 1), ans);
    }

    cout << ans << endl;

  
}

int main()
{

  int Testcases = 1;
  cin >> Testcases;
  while (Testcases--)
  {
    solve();
  }
}
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif

struct input_checker {
    string buffer;
    int pos;

    const string all = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
    const string number = "0123456789";
    const string upper = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    const string lower = "abcdefghijklmnopqrstuvwxyz";

    input_checker() {
        pos = 0;
        while (true) {
            int c = cin.get();
            if (c == -1) {
                break;
            }
            buffer.push_back((char) c);
        }
    }

    int nextDelimiter() {
        int now = pos;
        while (now < (int) buffer.size() && buffer[now] != ' ' && buffer[now] != '\n') {
            now++;
        }
        return now;
    }

    string readOne() {
        assert(pos < (int) buffer.size());
        int nxt = nextDelimiter();
        string res;
        while (pos < nxt) {
            res += buffer[pos];
            pos++;
        }
        return res;
    }

    string readString(int minl, int maxl, const string& pattern = "") {
        assert(minl <= maxl);
        string res = readOne();
        assert(minl <= (int) res.size());
        assert((int) res.size() <= maxl);
        for (int i = 0; i < (int) res.size(); i++) {
            assert(pattern.empty() || pattern.find(res[i]) != string::npos);
        }
        return res;
    }

    int readInt(int minv, int maxv) {
        assert(minv <= maxv);
        int res = stoi(readOne());
        assert(minv <= res);
        assert(res <= maxv);
        return res;
    }

    long long readLong(long long minv, long long maxv) {
        assert(minv <= maxv);
        long long res = stoll(readOne());
        assert(minv <= res);
        assert(res <= maxv);
        return res;
    }

    void readSpace() {
        assert((int) buffer.size() > pos);
        assert(buffer[pos] == ' ');
        pos++;
    }

    void readEoln() {
        assert((int) buffer.size() > pos);
        if (buffer[pos] != '\n') {
            cerr << int(buffer[pos]) << endl;
        }
        assert(buffer[pos] == '\n');
        pos++;
    }

    void readEof() {
        assert((int) buffer.size() == pos);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    input_checker in;
    int tt = in.readInt(1, 1e3);
    in.readEoln();
    int sn = 0;
    while (tt--) {
        int n = in.readInt(2, 1e5);
        sn += n;
        in.readEoln();
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            a[i] = in.readInt(0, 1e9);
            (i == n - 1 ? in.readEoln() : in.readSpace());
        }
        long long ans = 0;
        long long sum = 0;
        for (int i = 0; i < n; i++) {
            sum += a[i];
            ans = max(ans, (sum + i) / (i + 1));
        }
        cout << ans << '\n';
    }
    assert(sn <= 1e5);
    in.readEof();
    cerr << sn << endl;
    return 0;
}
Editorialist's code (Python)
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    ans = pref = 0
    for i in range(n):
        pref += a[i]
        ans = max(ans, (pref + i) // (i+1))
    print(ans)
1 Like

Hello,
I understand that

and this also makes sense. Since, we are minimizing the maximum value, it does mean we are going to equalize the values as far as possible.

However, isn’t this just a limit and it doesn’t really say it should be satisfied every time ?
The equality holds when all the elements of subset Ai are maximum.

Can anyone help me understand this by giving more context or a more rigorous proof regarding this :sweat_smile:

I didn’t claim that equality will always be satisfied, only that the inequality will always be satisfied :slightly_smiling_face:

In fact, the main idea behind this problem (and many other similar ones where binary search is applicable) is the fact that you can ‘relax’ the problem slightly to allow for inequalities instead of equalities.

Instead of asking “can I make the maximum exactly x?”, we’re asking “can I make the maximum at most x?”
This means we can instead concentrate on making every element of the array \leq x, instead of worrying about whether an x exists in the array and how many of them exist.

I’ve also given a formal proof (in the “Why?” section) of why P_i \leq i\cdot x is both a necessary and sufficient condition for the maximum to be at most x. Is there any confusion there?

Hi, I get the second part of the solution but did not understand the part on how to obtain a valid array

What happens when during the binary search we select a value of ‘x’ that is too large or too small?
Also, I cannot co-relate the construction of the valid array to the operation mentioned in the problem ie. add and subtract from adjacent elements.

Hello @iceknight1093 , Thank You for replying back to me.
Sorry for being vague. I could understand that

\left \lceil \frac{P_{i}}{i} \right \rceil

is the answer as I found out that in a round about way.

This will be a long post, please bear with me a bit.

However, I couldn’t understand few points in the proof.

Let me explain here what I have understood and doubts regarding that.

  1. Regarding the below

I understand that P_{j} remains same and the only effect on Prefix sum is P_{i} will increase. However, this is true only when we consider a single operation. If we consider two or more such operations, the adjacent or any P_{i} will change.
For example, take the array
A = \left[ 1,2,3,4 \right]
then prefix array will be
P = [1,3,6,10]
If we convert the array using operations
then A \sim [2,2,3,3] or A \sim [1,3,3,3]
consequently P \sim [2,4,7,10] or P \sim [1,4,7,10] .
From the above we can observe that all except the last element of P can be changed through multiple operations.
Also, we can observe that all P_{i} (except last element P_{N}) can only be increased but the array is always sorted (as it is a cumulative array).

Since P is always sorted, we can perform binary search as needed. However, the need is the constraint that we should find now.

  1. Now we consider x as the maximum element of the array.
    We can be sure that P_{i} \le i\cdot x . This is clear as x is the maximum of the array and P_{i} is the sum of only i elements. Hence, summing x , i times is clearly larger or equal (when all the elements in the array till A_{i} are equal to maximum of the array) [It seems this is pigeonhole principle in its simplest form]

  2. Now I cannot understand the below

Why is this required ? Isn’t it enough to say P_{i} \le i \cdot x ? [as P_{i+1} \le (i +1)\cdot x and subtracting both will give A_{i+1} \le x]
Was this the constraint that we need to use in the binary search ?

  1. My understanding of final simpler approach is a bit vague.

While the largest \left \lceil \frac{P_{i}}{i} \right \rceil value gives us a x which satisfies all P properties. How can we say

* This the smallest largest number that can be made.
*  That particular configuration is possible in the array "A" by using the given operations.

I guess I really lack the knowledge of mathematical formulations (of the scope/universe created at the start of the proof), mathematical proofs, hypothesis, inferences .

Also can you (or anyone) help me find some videos/lectures/slides/book for learning mathematical proofs, mathematical literacy (such as the above)

I will now explain how I understood that \left \lceil \frac{P_{i}}{i} \right \rceil is the answer from my approach (in a roundabout way)

  1. Observe that due to the given operations, “value” only moves from right to left. Which means borrowing of “value” from element A_{i-1} to A_{i} is not possible.

  2. Since this is the case, if the maximum element of the array is at the last position (position A_{N}), then we can virtually say to minimize the maximum element, borrow from A_{N} and distribute equally as possible to the before elements.
    That is, we equalize the array. So, the resulting array will contain the elements either \left \lfloor \frac{\sum A_i}{N} \right \rfloor or \left \lceil \frac{\sum A_i}{N} \right \rceil. (Average of the array)

  3. By this understanding, I thought I can use recursive approach. That is, split the array into two (A_{a}, A_{b}) subarrays, one with elements till the maximum of the array (A_{a}) and the rest of the elements as the second array (A_{b}).
    Since, A_{a} is a case where we know the solution, just equalize that part of the array and combine it with A_{b}.

  4. Do the above step again till doing the above step will not change the array. (By checking the position of maximum element. In case of multiple maximum elements, check the reversed index of the maximum)
    (Now that I think about it, I could have just equalized even when there is a local maxima and not just the global maxima)

  5. After reading this, I understood that what I was doing is same as calculating \lceil \frac{P_i}{i} \rceil.

For example,
take A = [1,2,5,4,3]
According to logic, A_{a1} = [1,2,5] and A_{b1} = [4,3].

A_{a1} becomes [2,3,3] after equalization and A_1 = [2,3,3,4,3]

Similarly, A_{a2} = [2,3,3,4] and A_{b2} = [3] which leads to A_2 = [3,3,3,3,3].
This array will not change even after going through the process again.
So, the answer is 3.

Now notice that, while calculating A_{a1} and A_{a2} what we are essentially calculating is \lceil \frac{P_i}{i} \rceil. After all, equalization is done by taking the average of that subarray.

Hence, by calculating the average of all subarrays (instead of checking the maximum and then calculating average of that specific subarray) we are reducing the complexity. (As just checking the maximum once is O(n) and we will be doing this multiple times in this approach)

After reading the above blog by iceknight1093 multiple times and writing this post along with constant pondering, I got more clarity.

Few things I understood.

  1. x in the post refers to a variable which must become the maximum. I previously thought x is fixed and hence the question about equality.

  2. The conditions so that x is maximum is derived from prefix sum array. Simply put we are creating N equations from P_{i} \le i \cdot x and we need to find x such that it satisfies all those N equations. Additionally, x should be minimum as required by the problem.

  3. As the array A itself is one of the configurations possible, we can find x such that P_{i} \le i \cdot x by just taking \lceil \frac{P_i}{i} \rceil for every i.
    Note that the same x should satisfy all the N conditions. So, we can take max(\lceil \frac{P_i}{i} \rceil) as it satisfies the inequality P_{i} \le i \cdot x or \frac{P_i}{i} \le x.
    This is smallest x that can satisfy all the equations.

  4. Also please note the value \frac{P_i}{i} can only be increased and cannot be decreased as P_i can only be increased as shown in above post and i is fixed for a for particular value.
    For example,
    A = [1,3,5,4,2] $$
    P = [1,4,9,13,15]
    \frac{P_i}{i} = [1,2,3,3.25,3]
    After equalizing the array,
    \widetilde{A} = [3,3,3,4,2] .
    \widetilde{P} = [3,6,9,13,15]
    \widetilde{\frac{P_i}{i}} = [3,2,3,3.25,3]

However, I am still a bit confused on

  1. whether A can get a configuration where x is the maximum.
  2. If operations are done on the array, P_i increases and \frac{P_i}{i} value also increase.
    So how can we say the x will satisfy those new N equations as well after the operations.

A sincere shoutout of amazement and awe to those who figured the simplest approach during the contest :saluting_face: .
I am really sure this would be impossible for me even if more than a week is given as I am now.

Kinda long post, I’ll just point out some issues I see and hopefully that helps.

Correct, and the editorial doesn’t say otherwise.
Performing an operation on (i, i+1) changes only P_i; of course choosing a different i will change a different value.

The idea here is to notice that you can discard A entirely and only work with P.

This is a misunderstanding (and hopefully the fact that you later realized that x is a variable helped solve this misunderstanding).
P is sorted, true. We use binary search, true. But those two facts aren’t related!

We aren’t binary searching on P, we’re binary searching on the answer, i.e we’re binary searching on the value of x.
If this idea is new to you, here’s a rather nice blog detailing the intuition behind it.

It’s always possible, yes.
If the final answer is x, then it’s possible to make every array element \leq x (I gave a construction of this in the editorial).

Now, if the maximum of this constructed array wasn’t x, every element would be \leq x-1.
In that case, x wouldn’t be the answer, no? The answer would be x-1 (or lower).
The fact that x is the smallest value for which this is achievable is already enough to say that such a configuration exists.

This again seems to be a misunderstanding stemming from not being clear on how binary search on the answer works.
Basically:

  • At the very start, we established that P_i can only increase.
  • When we binary search, for a value of x we want to check whether the answer is \leq x, i.e, whether the maximum can be made \leq x.
  • As you noted, this comes down to x satisfying N simultaneous inequalities, of the form P_i \leq i\cdot x.
  • Since we can only increase P_i values, if any of these inequalities is initially not satisfied, the answer is immediately “No”.
  • On the other hand, suppose every inequality is indeed satisfied.
    • Now we’d like to say that the answer is “Yes”, which means we need to prove that there’s a way to make every A_i \leq x while also satisfying these inequalities.
    • Of course, you can’t hope to randomly increase the P_i and achieve this, as you’ve noted. But we only need to show that there exists one way of doing it.
    • This is exactly what the construction I gave in the editorial does (the one where you set P_i = \min(i\cdot x, P_{i+1}), going from N-1 down to 1.
      • By the way, the intuition behind this construction is that ideally, you’d just set P_i = i\cdot x and be happy; but that isn’t always possible because you can’t increase P_N.
      • For example, what happens if P_N = (N-1)\cdot x - 1? If you increase P_{N-1} to (N-1)\cdot x, suddenly P is no longer sorted!
      • That’s why that slightly weird construction is used: it tries to conform to P_i = i\cdot x when possible; and when it isn’t possible because sortedness would break it does the next best thing.

If I had to say, the hardest part of this problem is explicitly writing out a correct construction.

However, actually getting AC technically didn’t need that because we didn’t ask for a construction, so you could just guess/hope/pray that a valid construction existed and that your approach is correct. I’d be completely unsurprised if many contestants did exactly that.

Thank You very much clarifying my misunderstandings :smiling_face: .

I still need some time and practice to understand this completely.
Also I think I need to read the blog again and again to understand that.

So, it is sad that I cannot say confidently that I understood everything :sweat_smile:.

If you do not mind, can suggest even more books/readings or findings to understand such constructions or ideology ?

I thought CP is more of data structures and generic algorithms , but now I need to re-evaluate and learn theoretical mathematics (not sure how though).