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)
.
.