2111. Minimum Operations to Make the Array K-Increasing Hard

1/**
2 * [2111] Minimum Operations to Make the Array K-Increasing
3 *
4 * You are given a 0-indexed array arr consisting of n positive integers, and a positive integer k.
5 * The array arr is called K-increasing if arr[i-k] <= arr[i] holds for every index i, where k <= i <= n-1.
6 * 
7 * 	For example, arr = [4, 1, 5, 2, 6, 2] is K-increasing for k = 2 because:
8 * 	
9 * 		arr[0] <= arr[2] (4 <= 5)
10 * 		arr[1] <= arr[3] (1 <= 2)
11 * 		arr[2] <= arr[4] (5 <= 6)
12 * 		arr[3] <= arr[5] (2 <= 2)
13 * 	
14 * 	
15 * 	However, the same arr is not K-increasing for k = 1 (because arr[0] > arr[1]) or k = 3 (because arr[0] > arr[3]).
16 * 
17 * In one operation, you can choose an index i and change arr[i] into any positive integer.
18 * Return the minimum number of operations required to make the array K-increasing for the given k.
19 *  
20 * Example 1:
21 * 
22 * Input: arr = [5,4,3,2,1], k = 1
23 * Output: 4
24 * Explanation:
25 * For k = 1, the resultant array has to be non-decreasing.
26 * Some of the K-increasing arrays that can be formed are [5,<u>6</u>,<u>7</u>,<u>8</u>,<u>9</u>], [<u>1</u>,<u>1</u>,<u>1</u>,<u>1</u>,1], [<u>2</u>,<u>2</u>,3,<u>4</u>,<u>4</u>]. All of them require 4 operations.
27 * It is suboptimal to change the array to, for example, [<u>6</u>,<u>7</u>,<u>8</u>,<u>9</u>,<u>10</u>] because it would take 5 operations.
28 * It can be shown that we cannot make the array K-increasing in less than 4 operations.
29 * 
30 * Example 2:
31 * 
32 * Input: arr = [4,1,5,2,6,2], k = 2
33 * Output: 0
34 * Explanation:
35 * This is the same example as the one in the problem description.
36 * Here, for every index i where 2 <= i <= 5, arr[i-2] <= arr[i].
37 * Since the given array is already K-increasing, we do not need to perform any operations.
38 * Example 3:
39 * 
40 * Input: arr = [4,1,5,2,6,2], k = 3
41 * Output: 2
42 * Explanation:
43 * Indices 3 and 5 are the only ones not satisfying arr[i-3] <= arr[i] for 3 <= i <= 5.
44 * One of the ways we can make the array K-increasing is by changing arr[3] to 4 and arr[5] to 5.
45 * The array will now be [4,1,5,<u>4</u>,6,<u>5</u>].
46 * Note that there can be other ways to make the array K-increasing, but none of them require less than 2 operations.
47 * 
48 *  
49 * Constraints:
50 * 
51 * 	1 <= arr.length <= 10^5
52 * 	1 <= arr[i], k <= arr.length
53 * 
54 */
55pub struct Solution {}
56
57// problem: https://leetcode.com/problems/minimum-operations-to-make-the-array-k-increasing/
58// discuss: https://leetcode.com/problems/minimum-operations-to-make-the-array-k-increasing/discuss/?currentPage=1&orderBy=most_votes&query=
59
60// submission codes start here
61
62impl Solution {
63    pub fn k_increasing(arr: Vec<i32>, k: i32) -> i32 {
64        0
65    }
66}
67
68// submission codes end
69
70#[cfg(test)]
71mod tests {
72    use super::*;
73
74    #[test]
75    fn test_2111() {
76    }
77}
78