# Breaking Arrays into subarrays meeting some condition

Few example problems

## Codeforces Contest 882 Div 2, Problem A

### Problem Statement

In Codeforces Contest 882 Div 2, Problem A they are asking to break the array into continuous parts such that sum of power for all segment is minimised. Suppose $$A$$ is the array then find a sequence $$(a_i) \mid \forall i \in [n], a_i = A[i]$$ such that $$\sum_{i \in (a_i)} f(a_{i-1}, a_i)$$ is minimised. Here $$(a_{i-1}, a_i)$$ is subsequence of the array $$A$$.

### Approach

• Power of a sub sequence of villagers from $$a[l \dots r]$$ is defined as $$abs(a[l] - a[l + 1]) + abs(a[l+1] - a[l + 2]) + ... + abs(a[r-1] - a[r])$$
• Our task is to break the villagers into exactly $$k$$ contiguous subgroups so that the sum of their power for each of the group is minimized and single member groups are worth $$0$$ power.
• Simple Observation is that if we break the continiousness of a group at some location $$i$$ then the sum of all the powers reduces by $$abs(a[i - 1] - a[i])$$. Hence we must find the biggest such drop and break the members there.
• At the end return the total sum.

### Code

#include <iostream>
#include <math.h>
#include <vector>

using namespace std;

int main() {
// ith guy has a[i] sus on Kars.
// a sub sequence of villagers from a[l ... r] is defined as
// abs(a[l] - a[l + 1]) + abs(a[l+1] - a[l + 2]) + ... + abs(a[r-1] - a[r]) is the power of a group

// task break the villagers into exactly k
// contiguous subgroups so that the sum of their power for each of the group is minimized.
// single member groups are worth 0 power.

int testcases;
cin >> testcases;

while (testcases--) {
int n, k;
cin >> n >> k;

int a[n];
for (int i = 0; i < n; i++) {
cin >> a[i];
}

// solution for each of the testcases
// first consider the entire array as a group
int maxcost = 0;
pair<int, int> diff[n]; // difference array stores all n-1 a[i-1] - a[i] computations

diff[0] = {0, 0};

for (int i = 1; i < n; i++) {
int cost = abs(a[i] - a[i - 1]);
maxcost += cost;
diff[i] = {cost, i - 1};
}

// now sort the diff array based on decreasing differences
std::sort(diff, diff + n, [](const auto &a, const auto &b) {
return a.first > b.first;
});

for (int i = 0; i < k-1; i++) {
maxcost -= diff[i].first;
}

cout << maxcost << endl;
}

return 0;
}