CHEFSTRT - Editorial

Practice

Contest

DIFFICULTY:

Easy

PREREQUISITES:

Arrays and Mathematics

PROBLEM:

You have to find the minimum value X such that X + cumulative\_sum[i] where i = 0, 1, \cdots, n-1 never goes below 1.

Note: It is possible that X can be less than 1.

QUICK EXPLANATION:

Let’s consider the value at i^{th} index, i.e. X + cumulative\_sum[i].

The condition is:

X + cumulative\_sum[i] >= 1.

\implies X >= 1 - cumulative\_sum[i]

If you consider the condition for all the indices, turns out that the minimum value of X will be the maximum value of 1 - cumulative\_sum[i].

EXPLANATION:

If you have multiple conditions like:

X >= 1, X >= 2, X >= 3

Then, the minimum value of X satisfying them all is the maximum value on the RHS of the inequality.

COMMON MISTAKES:

Subtask 1 was kept just because of the common mistake many of you might have made to consider the numbers as integers, but it turns out the the original constraints in the problem may lead to a value of X outside the range of int, so you will need a long int.

SOLUTION:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll minimum_X(vector<ll>& arr) {
    ll res = LLONG_MIN;
    int n = arr.size();
    ll sum = 0;
    for (int i = 0; i < n; ++i) {
        sum += arr[i];
        res = max(res, 1 - sum);
    }
    return res;
}

int main () {
    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        vector<ll> inp(n);
        for (auto &x: inp) {
            cin >> x;
        }

        cout << minimum_X(inp) << endl;
    }
    return 0;
}