Just sharing my thoughts and experience with this problem:
This should have been the first problem in \text{Division 2}.
I liked this problem very much. This got me thinking for a while, while I was able to solve the first two in less than 10 mins.
The moment I read the statement I couldn’t come up with any solution, not even brute-force (generating a state-space tree for this kind of problem will consume a lot of time).
After thinking for some time, I thought only one sorting would be enough - sort segment A[L\dots R] for some 1 \le L\le R\le N. Further:
- Let B = \text{sorted}(A).
- Let i and j be two integers such that A[1\dots i] = B[1\dots i] and A[j\dots N] = B[j\dots N].
- The answer will be \text{max}(A[i + 1, \dots, j - 1]) - \text{min}(A[i + 1, \dots, j - 1).
But samples betrayed me (Nice framing of samples). My approach worked on samples but not on private test cases.
I missed something, so started working on some small test cases, when I found this.
6
1 5 3 8 7 9
// Expected Output: 3
// My Output: 5
Then I realised there’s not just one segment, there could be more than 1 non-overlapping segments that should be sorted individually to minimise the cost.
Then framed this approach:
-
For each element A[i], find an integer j that satisfies the following conditions
-
j was not used earlier
-
j should be one of the indices where A[i] can be placed. By “\text{can be placed}”, j is one of the positions where A[i] appears in sorted array.
-
|i - j| should be minimum.
-
We end up with several intervals of the form (i, j), that have to be sorted.
-
We still have to merge overlapping intervals - intervals (x_1, y_1) and (x_2, y_2) can be merged iff (y_1 \ge x_2).
-
Now, we have a set of non-overlapping intervals \{(x_1,\ y_1),\ (x_2,\ y_2), \dots, (x_m,\ y_m)\}.
-
The cost of sorting will be \sum_{i = 1}^{i = m} \text{max}(A[x_i\dots y_i ]) - \text{min}(A[x_i\dots y_i]).
Implementation
vector<pair<int, int>> merge_intervals(vector<pair<int, int>>& intervals) {
sort(intervals.begin(), intervals.end());
vector<pair<int, int>> ans;
int i = 0;
while(i < intervals.size()) {
int start = intervals[i].first;
int end = intervals[i].second;
while(i < intervals.size() && intervals[i].first <= end) {
end = max(end, intervals[i].second);
i++;
}
ans.push_back({start, end});
}
return ans;
}
void solve() {
int N = 0;
cin >> N;
vector<int> A(N);
for(int i = 0; i < N; i++)
cin >> A[i];
vector<int> B(N);
for(int i = 0; i < N; i++)
B[i] = A[i];
sort(B.begin(), B.end());
map<int, vector<int>> indices;
FOR(i, N) {
indices[B[i]].push_back(i);
}
map<int, int> index_position;
vector<pair<int, int>> segs;
for(int i = 0; i < N; i++) {
if(A[i] != B[i]) {
pair<int, int> seg = make_pair(i, indices[A[i]][index_position[A[i]]]);
if(seg.second < seg.first) {
swap(seg.first, seg.second);
}
segs.push_back(seg);
}
index_position[A[i]]++;
}
vector<pair<int, int>> intervals = merge_intervals(segs);
int ans = 0;
for(auto interval : intervals) {
int start = interval.first;
int end = interval.second;
int max_val = INT_MIN, min_val = INT_MAX;
for(int i = start; i <= end; i++) {
if(A[i] > max_val) max_val = A[i];
if(A[i] < min_val) min_val = A[i];
}
ans += max_val - min_val;
}
cout << ans << '\n';
}
