PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07
Tester: tabr
Editorialist: iceknight1093
DIFFICULTY:
Easy
PREREQUISITES:
Prefix sums
PROBLEM:
For an array B, define f(B, K) to be the minimum number of operations required to make the sum of adjacent differences be \leq K.
In one operation, you can choose a maximal segment of B that contains the same element, and either add 1 or subtract 1 from them all.
You’re given an array A. Answer Q queries on it:
- Given L, R, K, find f(A[L\dots R], K)
EXPLANATION:
This editorial will continue from the solution to the easy version.
Recall that to compute f(B, K), we defined S = \sum_{i=2}^M |B_i - B_{i-1}|, and then repeatedly found moves that reduced S by 2 while possible, otherwise reduced it by 1.
Now, the constraints are too large for direct simulation to work.
However, let’s analyze what exactly we’re doing.
Suppose we find a maximal subarray [L, R] that reduces S by 2.
Then, one of the two following cases must hold:
- B_{L-1} \gt B_L and B_{R+1} \gt B_R (in which case increasing the subarray by 1 reduces S by 2).
- B_{L-1} \lt B_L and B_{R+1} \lt B_R (in which case decreasing the subarray by 1 reduces S by 2).
In particular, such a subarray cannot have L = 1 or R = M, i.e, cannot be a border subarray.
This is because both its neighbors must exist for S to decrease by 2.
We now observe that:
- If B is not sorted (in either ascending or descending order), such a subarray will definitely exist.
- If B is sorted, no such subarray exists.
Proof
It should be obvious that if B is sorted, no such subarray can exist: after all, such a subarray gives us both ascending and descending relations in the array, which cannot happen if it’s sorted.
Now, suppose B isn’t sorted.
Look at the maximal subarrays of B from left to right, and let the corresponding values in these subarrays be x_1, x_2, \ldots, x_r.
Suppose x_1 \lt x_2.
Then, there must exist some i such that x_i \gt x_{i+1} (otherwise the array would be sorted in ascending order).
Choose the leftmost such i.
We then see that the block containing x_i has greater values than both its neighboring blocks, thus giving us a 2-move.
In other words, our procedure is as follows:
- While B is not sorted, reduce S by 2.
- While B is sorted, reduce S by 1.
However, observe that when B is not sorted, we never operate on the first and last subarrays of B (since as we noted above, these can’t reduce S by 2).
But, for a sorted array, the sum of adjacent differences is simply the difference between the first and last elements!
So, since B_1 and B_N don’t change at all, the first time B becomes sorted is when we’ll have S = |B_1 - B_N|.
This means our process is in fact quite simple:
- While S \gt |B_1 - B_N|, reduce it by 2.
- Once it reaches |B_1 - B_N|, reduce it by 1 henceforth.
- Stop once it becomes \leq K.
We are now ready to answer queries.
For the query (L, R, K):
- First, compute S = \sum_{i=L+1}^R |A_i - A_{i-1}|.
- To compute this quickly, use prefix sums on the array d with d_i = |A_i - A_{i-1}|.
- If S \leq K already, nothing needs to be done.
Otherwise,- If K \geq |A_R - A_L|, we’ll repeatedly decrease S by 2 till it falls to K or below.
The number of moves needed is thus
\displaystyle\left\lceil \frac{S-K}{2} \right\rceil - Otherwise, S reduces by 2 till it reaches |A_L - A_R|, and then by 1 till it reaches K.
The number of moves needed is
\displaystyle\frac{S - |A_L - A_R|}{2} + (|A_L - A_R| - K)
- If K \geq |A_R - A_L|, we’ll repeatedly decrease S by 2 till it falls to K or below.
TIME COMPLEXITY:
\mathcal{O}(N + Q) per testcase.
CODE:
Author's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
void Solve()
{
int n, q; cin >> n >> q;
vector <int> a(n + 1), b(n + 1);
for (int i = 1; i <= n; i++){
cin >> a[i];
}
for (int i = 2; i <= n; i++){
b[i] = abs(a[i] - a[i - 1]);
b[i] += b[i - 1];
}
while (q--){
int l, r, k; cin >> l >> r >> k;
int diff = b[r] - b[l];
if (diff <= k){
cout << 0 << "\n";
continue;
}
int go = abs(a[r] - a[l]);
assert(diff % 2 == go % 2);
int ans = 0;
if (k < go){
// first go to go
ans += (diff - go) / 2;
ans += (go - k);
} else {
ans += (diff - k + 1) / 2;
}
cout << ans << "\n";
}
}
int32_t main()
{
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// freopen("in", "r", stdin);
// freopen("out", "w", stdout);
cin >> t;
for(int i = 1; i <= t; i++)
{
//cout << "Case #" << i << ": ";
Solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
return 0;
}
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
void solve(istringstream cin) {
int n, q;
cin >> n >> q;
vector<long long> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
vector<long long> d(n);
for (int i = 1; i < n; i++) {
d[i] = d[i - 1] + abs(a[i] - a[i - 1]);
}
while (q--) {
int l, r;
long long k;
cin >> l >> r >> k;
l--;
r--;
long long sum = d[r] - d[l];
if (sum <= k) {
cout << 0 << '\n';
continue;
}
long long t = (sum - abs(a[l] - a[r])) / 2;
t = min(t, (sum - k + 1) / 2);
long long ans = t;
sum -= 2 * t;
if (sum > k) {
ans += sum - k;
}
cout << ans << '\n';
}
}
////////////////////////////////////////
#define IGNORE_CR
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;
}
#ifdef IGNORE_CR
if (c == '\r') {
continue;
}
#endif
buffer.push_back((char) c);
}
}
string readOne() {
assert(pos < (int) buffer.size());
string res;
while (pos < (int) buffer.size() && buffer[pos] != ' ' && buffer[pos] != '\n') {
assert(!isspace(buffer[pos]));
res += buffer[pos];
pos++;
}
return res;
}
string readString(int min_len, int max_len, const string& pattern = "") {
assert(min_len <= max_len);
string res = readOne();
assert(min_len <= (int) res.size());
assert((int) res.size() <= max_len);
for (int i = 0; i < (int) res.size(); i++) {
assert(pattern.empty() || pattern.find(res[i]) != string::npos);
}
return res;
}
int readInt(int min_val, int max_val) {
assert(min_val <= max_val);
int res = stoi(readOne());
assert(min_val <= res);
assert(res <= max_val);
return res;
}
long long readLong(long long min_val, long long max_val) {
assert(min_val <= max_val);
long long res = stoll(readOne());
assert(min_val <= res);
assert(res <= max_val);
return res;
}
vector<int> readInts(int size, int min_val, int max_val) {
assert(min_val <= max_val);
vector<int> res(size);
for (int i = 0; i < size; i++) {
res[i] = readInt(min_val, max_val);
if (i != size - 1) {
readSpace();
}
}
return res;
}
vector<long long> readLongs(int size, long long min_val, long long max_val) {
assert(min_val <= max_val);
vector<long long> res(size);
for (int i = 0; i < size; i++) {
res[i] = readLong(min_val, max_val);
if (i != size - 1) {
readSpace();
}
}
return res;
}
void readSpace() {
assert((int) buffer.size() > pos);
assert(buffer[pos] == ' ');
pos++;
}
void readEoln() {
assert((int) buffer.size() > pos);
assert(buffer[pos] == '\n');
pos++;
}
void readEof() {
assert((int) buffer.size() == pos);
}
};
int main() {
input_checker in;
int tt = in.readInt(1, 1e4);
in.readEoln();
int sn = 0, sq = 0;
while (tt--) {
int n = in.readInt(2, 2e5);
in.readSpace();
int q = in.readInt(2, 2e5);
in.readEoln();
sn += n;
sq += q;
auto a = in.readInts(n, 1, 1e9);
in.readEoln();
vector<int> l(q), r(q), k(q);
for (int i = 0; i < q; i++) {
l[i] = in.readInt(1, n);
in.readSpace();
r[i] = in.readInt(l[i] + 1, n);
in.readSpace();
k[i] = in.readInt(1, 1e9);
in.readEoln();
}
ostringstream sout;
sout << n << " " << q << '\n';
for (int i = 0; i < n; i++) {
sout << a[i] << " \n"[i == n - 1];
}
for (int i = 0; i < q; i++) {
sout << l[i] << " " << r[i] << " " << k[i] << '\n';
}
solve(istringstream(sout.str()));
}
cerr << sn << " " << sq << endl;
assert(sn <= 2e5);
assert(sq <= 2e5);
in.readEof();
return 0;
}
Editorialist's code (Python)
for _ in range(int(input())):
n, q = map(int, input().split())
a = list(map(int, input().split()))
pref = [0]*n
for i in range(1, n): pref[i] = pref[i-1] + abs(a[i] - a[i-1])
for j in range(q):
l, r, k = map(int, input().split())
l, r = l-1, r-1
sm = pref[r] - pref[l]
if sm <= k:
print(0)
continue
# while sm > a[r] - a[l], decrease by 2
# then, decrease by 1
if k >= abs(a[r] - a[l]):
d = sm - k
print((d+1)//2)
else:
print((sm - abs(a[r] - a[l]))//2 + abs(a[r] - a[l]) - k)