PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: tabr
Editorialist: iceknight1093
DIFFICULTY:
Simple
PREREQUISITES:
Binary search
PROBLEM:
A recipe has i steps, the i-th step recommends a temperature of A_i. Steps must be performed in order.
If the i-th step is performed at a temperature of B_i, the unsavoriness of the dish is \max_{i=1}^N |A_i - B_i|.
Find the minimum possible unsavoriness of the dish if you can only change temperature at most K times.
EXPLANATION:
Let’s turn the problem around - if we set M = \max_{i=1}^N |A_i - B_i| as the maximum allowed unsavoriness, can we change temperature at most K times?
To answer this, we’ll instead find the minimum number of times the temperature needs to change when M is fixed.
Since M is the maximum allowed difference, the array B must satisfy A_i - M \leq B_i \leq A_i + M, i.e, there’s an interval (of length 2M+1) from within which each B_i can be chosen.
Let f_i = [A_i - M, A_i + M] denote the i-th interval.
If we want to maintain the same temperature across the steps L, L+1, \ldots, R, then the temperature should lie in all the intervals f_L, f_{L+1}, \ldots, f_R.
Such a temperature exists if and only if these intervals have a non-empty intersection.
So, we want to be able to split the array A into the minimum number of contiguous segments, such that within each segment the corresponding intervals have non-empty intersection.
This can be done greedily - that is, take the intervals f_1, f_2, f_3, \ldots into one segment as long as they have a non-empty intersection.
The instant you hit some i such that \{f_1, f_2, \ldots, f_i\} has empty intersection, cut the segment at i-1, and repeat the process starting from i.
Proof of correctness
This is fairly easy to show.
Take any optimal solution. Suppose the first segment doesn’t match the one our greedy process finds.
Our greedy process found the longest possible segment that works, so the first segment in the optimal solution must be strictly shorter.
But then, we can take the first element from the second segment and move it to the first segment.
This won’t invalidate the second segment (since removing an interval can only improve the intersection), and we also know it doesn’t invalidate the first segment since the greedy was able to include it.
Simply repeat this process till the first segments equals the greedy’s first segment.
Then, repeat this for the remaining segments.
Now we’ve transformed any optimal solution to our greedy solution without losing optimality, so the greedy must be optimal.
To implement the above check, we need to be able to compute the intersection of the current segment of intervals as we iterate.
This is quite easy: given two intervals [l_1, r_1] and [l_2, r_2], their intersection is the interval [\max(l_1, l_2), \min(r_1, r_2)].
If \max(l_1, l_2) \gt \min(r_1, r_2), then the intersection is empty.
Since the intersection remains an interval, it’s then quite easy to intersect it with the next interval, and so on.
If the intersection ever becomes empty, increase the number of changes needed by 1, then reset the interval to be the current one and continue on.
Pseudocode of the implementation is as follows:
intersection = [a[1] - m, a[1] + m]
changes = 0
for i in 1...n:
intersection = [max(intersection[0], a[i] - m), min(intersection[1], a[i] + m)]
if intersection[0] > intersection[1]:
changes += 1
intersection = [a[i] - m, a[i] + m]
Now, for a fixed M, let f(M) denote the minimum number of changes we need.
Note that:
- We’re able to compute a single f(M) in \mathcal{O}(N) time using the logic above.
- f(M) \geq f(M+1), because any solution for difference at most M also works for difference at most M+1; but M+1 might have better solutions possible (since all the intervals become a bit longer).
Our goal is to find the smallest M such that f(M) \leq K.
The two points above tell us that this is doable by simply binary searching for M on the range [0, 10^9], with an overall complexity of \mathcal{O}(N\log 10^9).
TIME COMPLEXITY:
\mathcal{O}(N \log 10^9) per testcase.
CODE:
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
void solve(istringstream cin) {
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
long long low = -1;
long long high = 2e9;
while (high - low > 1) {
auto mid = (high + low) >> 1;
int mn = a[0];
int mx = a[0];
int cnt = 0;
for (int i = 1; i < n; i++) {
mn = min(mn, a[i]);
mx = max(mx, a[i]);
if (mx - mn > 2 * mid) {
cnt++;
mn = a[i];
mx = a[i];
}
}
if (cnt <= k) {
high = mid;
} else {
low = mid;
}
}
cout << high << '\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, 1e5);
in.readEoln();
int sn = 0;
while (tt--) {
int n = in.readInt(1, 2e5);
in.readSpace();
sn += n;
int k = in.readInt(0, n);
in.readEoln();
auto t = in.readInts(n, 1, 1e9);
in.readEoln();
ostringstream sout;
sout << n << ' ' << k << '\n';
for (int i = 0; i < n; i++) {
sout << t[i] << " \n"[i == n - 1];
}
solve(istringstream(sout.str()));
}
cerr << sn << endl;
assert(sn <= 2e5);
in.readEof();
return 0;
}
Editorialist's code (PyPy3)
for _ in range(int(input())):
n, k = map(int, input().split())
a = list(map(int, input().split()))
def check(mid):
L, R = a[0] - mid, a[0] + mid
ans = 0
for x in a:
L = max(L, x - mid)
R = min(R, x + mid)
if L <= R: continue
ans += 1
L, R = x - mid, x + mid
return ans
lo, hi = 0, 10**9
while lo < hi:
mid = (lo + hi)//2
if check(mid) <= k: hi = mid
else: lo = mid + 1
print(lo)
exit()