Min Max Equality solution codechef

Min Max Equality solution codechef

 

Chef found an array AA of NN elements. He defines a subarray as bad if the maximum element of the subarray is equal to the minimum element of the subarray.

More formally, a subarray [L,R][L,R] (1LRN)(1≤L≤R≤N) is bad if max(AL,AL+1,,AR)=min(AL,AL+1,...,AR)max(AL,AL+1,…,AR)=min(AL,AL+1,…,AR).

Chef is allowed to change at most KK elements of the array.
Find the minimum number of bad subarrays Chef can obtain after changing at most KK elements of the array.

Min Max Equality solution codechef

  • First line will contain TT, the number of test cases. Then the test cases follow.
  • Each test case contains two lines of input, the first line contains two space-separated integers NN and KK – the number of elements in the array and the maximum number of elements Chef can change respectively.
  • The second line contains NN space-separated integers A1,A2,,ANA1,A2,…,AN – the initial array.

Min Max Equality solution codechef

For each test case, output the minimum number of bad subarrays Chef can obtain after changing at most KK elements of the array.

Constraints

  • 1T31041≤T≤3⋅104
  • 1N1051≤N≤105
  • 1KN1≤K≤N
  • 1Ai1091≤Ai≤109
  • Sum of NN over all test cases does not exceed 31053⋅105.

Min Max Equality solution codechef  

3
3 1
1 2 3
4 2
3 3 3 1
5 1
1 1 1 1 1

Min Max Equality solution codechef  

3
4
7

Explanation

Test case 11: The minimum number of bad subarrays Chef can obtain is 33. Chef does not need to perform any operations. The subarrays where the maximum element is equal to the minimum element are [1,1],[2,2],[1,1],[2,2], and [3,3][3,3] where [L,R][L,R] denotes the subarray starting at index LL and ending at index RR.

Test case 22: The minimum number of bad subarrays Chef can obtain is 44. Chef can perform 22 operations and change the array to [2,4,3,1][2,4,3,1]. The subarrays where the maximum element is equal to the minimum element are [1,1],[2,2],[3,3],[1,1],[2,2],[3,3], and [4,4][4,4].

Leave a Comment