2111. Minimum Operations to Make the Array K-Increasing
- observe and find the pattern
- you will be then finding the LIS pattern.
code
```cpp
/* implementation of LIS */
int lis(const vector& arr) {
int n = arr.size();
vector trackNum, trackIndex, parent(2 * arr.size(), 0);
int lis_end = 0;
for (int i = 0; i < n; ++i) {
int pos = upper_bound(trackNum.begin(), trackNum.end(), arr[i]) - trackNum.begin();
if (pos >= trackNum.size()) {
trackNum.push_back(arr[i]);
trackIndex.push_back(i);
lis_end = max(lis_end, i);
} else {
trackNum[pos] = arr[i];
trackIndex[pos] = i;
}
parent[i] = pos ? trackIndex[pos - 1] : -1;
}
return trackNum.size();
}
/* real code */
int kIncreasing(vector& arr, int k) {
int ans = 0;
int n = arr.size();
for (int i = 0; i < k; i++) {
vector temp;
for (int j = i; j < n; j += k)
temp.push_back(arr[j]);
int count = lis(temp);
ans += int(temp.size()) - count;
}
return ans;
}
```
</details>