Empty Graph
Contest: Codeforces Round 813 (Div. 2)
Difficulty rating: 2000
Tags: binary search, constructive algorithms, data structures, greedy, shortest paths

An array of $$$n$$$ positive integers $$$a_1,a_2,\ldots,a_n$$$ fell down on you from the skies, along with a positive integer $$$k \le n$$$.

You can apply the following operation at most $$$k$$$ times:

- Choose an index $$$1 \le i \le n$$$ and an integer $$$1 \le x \le 10^9$$$. Then do $$$a_i := x$$$ (assign $$$x$$$ to $$$a_i$$$).

Then build a complete undirected weighted graph with $$$n$$$ vertices numbered with integers from $$$1$$$ to $$$n$$$, where edge $$$(l, r)$$$ ($$$1 \le l < r \le n$$$) has weight $$$\min(a_{l},a_{l+1},\ldots,a_{r})$$$.

You have to find the maximum possible diameter of the resulting graph after performing at most $$$k$$$ operations.

The diameter of a graph is equal to $$$\max\limits_{1 \le u < v \le n}{\operatorname{d}(u, v)}$$$, where $$$\operatorname{d}(u, v)$$$ is the length of the shortest path between vertex $$$u$$$ and vertex $$$v$$$.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). Description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 10^5$$$, $$$1 \le k \le n$$$).

The second line of each test case contains $$$n$$$ positive integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le 10^9$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output format:
For each test case print one integer — the maximum possible diameter of the graph after performing at most $$$k$$$ operations.

Constraints:
Time limit: 1.5 s
Memory limit: 256.0 MB

Note:
In the first test case, one of the optimal arrays is $$$[2,4,5]$$$.

The graph built on this array:

$$$\operatorname{d}(1, 2) = \operatorname{d}(1, 3) = 2$$$ and $$$\operatorname{d}(2, 3) = 4$$$, so the diameter is equal to $$$\max(2,2,4) = 4$$$.

Example input:
6
3 1
2 4 1
3 2
1 9 84
3 1
10 2 6
3 2
179 17 1000000000
2 1
5 9
2 2
4 2

Example output:
4
168
10
1000000000
9
1000000000

Editorial:
First of all, we will always use the operation to assign $$$10^9$$$ to $$$a_i$$$.
1. Suppose $$$u < v$$$. Then $$$\operatorname{d}(u, v) = \min(\min(a_u \ldots a_v), 2 \cdot \min(a_1 \ldots a_n))$$$.
Proof: since the weight of an edge is always $$$\ge \min(a_1 \ldots a_n)$$$, the best we can do with one edge is $$$\min(a_u \ldots a_v)$$$. And the best we can possibly do with two edges is $$$2 \cdot \min(a_1 \ldots a_n)$$$, which turns out possible to achieve.
Subproof: suppose $$$i_{min}$$$ is the index of one of the minimums in the array. If $$$u \le i_{min} \le v$$$, then $$$\min(a_u \ldots a_v)$$$ is optimal, so we don't need two edges in the first place. Else, either $$$i_{min} < u$$$ or $$$i_{min} > v$$$. In the first case, we can notice that $$$\operatorname{d}(u, 1) + \operatorname{d}(1, v) = 2 \cdot \min(a_1 \ldots a_n)$$$. In the second case, $$$\operatorname{d}(u, n) + \operatorname{d}(n, v) = 2 \cdot \min(a_1 \ldots a_n)$$$.
$$$ $$$
2. The diameter of the graph is equal to $$$\max\limits_{1 \le i \le n - 1}{\operatorname{d}(i, i + 1)} = \min \left( \max\limits_{1 \le i \le n - 1}{\min(a_i,a_{i+1})}, 2 \cdot \min(a_1 \ldots a_n) \right)$$$.
Proof: since the minimum of a subsegment can only decrease when it's length increases, it is optimal to look only at the distance between two adjacent vertices.
Now we can either do binary search on the answer, or we can do a clever greedy.
$$$ $$$
Binary search solution:
Suppose the answer is $$$\ge ans$$$. First of all, we need to apply the operation for all $$$a_i < \frac{ans}{2}$$$. If there are not enough operations to do this, return false. Otherwise assign $$$10^9$$$ to such $$$a_i$$$. If there are no operations left, just calculate the diameter and see if it is $$$\ge ans$$$.
If there is at least one operation left, there are two cases: $$$k = 1$$$ and $$$k \ge 2$$$. If the first case, it is optimal to apply our operation near one of the maximums in the array to maximize $$$\min(a_i, a_{i + 1})$$$, so we need to return true if $$$\max(a_1 \ldots a_n) \ge ans$$$. With $$$k > 1$$$, it is optimal to apply the operation near an index which has been turned into $$$10^9$$$, so we always return true.
Make sure to binary search on $$$ans$$$ from $$$1$$$ to $$$10^9$$$ inclusive. Doing it from $$$1$$$ to $$$2\cdot 10^9$$$ needs another case to work.
Complexity: $$$\mathcal{O}(n \log A)$$$.
$$$ $$$
Greedy solution:
We can actually maintaining the diameter of the graph while supporting point update queries (set $$$a_i$$$ to some value). To do this, we can use any structure that can get $$$\max\limits_{1 \le i \le n - 1}{\min(a_i,a_{i+1})}$$$ (multiset, segment tree) and another structure to maintain the minimum in the array.
Change the $$$k - 1$$$ smallest values in the array into $$$10^9$$$. For every $$$i$$$ from $$$1$$$ to $$$n$$$, change $$$a_i$$$ to $$$10^9$$$, get the diameter, and then change $$$a_i$$$ back to it's original value. The answer is the max value over all the returned diameters.
Proof: obviously works for $$$k = 1$$$, so suppose $$$k \ge 2$$$. Since we changed at least one value, we will check if having two adjacent $$$10^9$$$ is optimal, maximizing $$$\max\limits_{1 \le i \le n - 1}{\min(a_i,a_{i+1})}$$$. And we will also check if we need to change the $$$k$$$-th smallest value, in this case maximizing $$$2 \cdot \min(a_1 \ldots a_n)$$$.
Complexity: $$$\mathcal{O}(n \log n)$$$
Note: it is also possible to solve without data structures by doing a bit more casework, but the solution is still $$$\mathcal{O}(n \log n)$$$ due to sorting.