UTS Open '21 P6 - Terra Mater

View as PDF

Submit solution

Points: 25 (partial)
Time limit: 4.0s
Memory limit: 256M

Problem types

In an alternate universe, you are the Earth god tasked with the responsibility of managing terrain safety. Your most pressing duty is that of N hills lined up in a single row. You know that the i^{th} hill from the left currently has height H_i. In your world, the danger factor of any terrain is the maximum difference in height between any 2 adjacent hills. Formally, the danger factor is defined as \max_{1 \le i \le N-1} (|H_i - H_{i+1}|). To minimize the danger factor, you are allowed to change the height of at most K hills, each to any positive integer of your choosing (the resulting height may be different for each hill). Please find the minimum possible danger factor after doing so. To ensure the integrity of your solution, there may be multiple test cases.


For this problem, you will NOT be required to pass the sample case in order to receive points. In addition, you must pass all previous subtasks to earn points for a specific subtask.

For all subtasks:

1 \le T \le 500

2 \le N \le 2 \times 10^5

0 \le K \le N

1 \le H_i \le 10^9

The sum of N over all test cases will not exceed 2 \times 10^5.

Subtask 1 [5%]

K = 0

Subtask 2 [5%]

K = 1

Subtask 3 [10%]

K = 2

Subtask 4 [80%]

No additional constraints.

Input Specification

The first line contains an integer T, the number of test cases. The next 2T lines will describe the test cases.

The first line of each test case contains 2 integers N and K, the number of hills and the number of hills whose height you may change.

The second line of each test case contains N integers H_i (1 \le i \le N), the height of the i^{th} hill from the left.

Output Specification

For each test case output one integer on its own line, the minimum possible danger factor after changing the height of at most K hills.

Sample Input

6 2
1 3 7 2 3 6
7 4
1 5 8 5 5 7 8

Sample Output



For the first test case, one possible solution is to change the height of the third hill to 4 and the height of the sixth hill to 1, as depicted in the diagram above. The resulting danger factor is \max(|1-3|, |3-4|, |4-2|, |2-3|, |3-1|) = 2.

For the second test case, the optimal solution is to change the heights of the first, third, sixth, and seventh hills all to 5. Since all hills have the same height now, the resulting danger factor is 0.


There are no comments at the moment.