Empty Graph (Codeforces 1712D)
Tags: Greedy, shortest paths

 — Do you have a wish?  — I want people to stop gifting each other arrays.O_o and Another Young BoyAn 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: 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: For each test case print one integer — the maximum possible diameter of the graph after performing at most $$$k$$$ operations.

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$$$.

Sample Inputs:
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

Sample Outputs:
4
168
10
1000000000
9
1000000000

Solution (Python):
import collections
import math

def solve():
    (n, k) = list(map(int, input().split()))
    arr = list(map(int, input().split()))
    if n == k:
        print(10 ** 9)
        return
    new_arr = []
    for i in range(n):
        new_arr.append((arr[i], i))
    new_arr.sort()
    i = 0
    k -= 1
    while k:
        arr[new_arr[i][1]] = 10 ** 9
        i += 1
        k -= 1
    min_idx = set([0])
    curr = arr[0]
    l = 0
    for i in range(1, n):
        l = max(l, min(arr[i - 1], arr[i]))
        temp = arr[i]
        if temp < curr:
            min_idx = set([i])
            curr = temp
        elif temp == curr:
            min_idx.add(i)
    edge = curr
    if len(min_idx) == 1:
        sub_min = math.inf
        for i in range(n):
            if i not in min_idx:
                sub_min = min(sub_min, arr[i])
    if arr[0] < arr[1]:
        e = edge
        if 0 in min_idx and len(min_idx) == 1:
            e = sub_min
        ans = min(max(l, arr[1]), 2 * e)
    else:
        ans = min(l, 2 * edge)
    for i in range(1, n - 1):
        if arr[i] < arr[i - 1] or arr[i] < arr[i + 1]:
            e = edge
            if i in min_idx and len(min_idx) == 1:
                e = sub_min
            ans = max(ans, min(max(l, arr[i - 1], arr[i + 1]), 2 * e))
    if arr[n - 1] < arr[n - 2]:
        e = edge
        if n - 1 in min_idx and len(min_idx) == 1:
            e = sub_min
        ans = max(ans, min(max(l, arr[n - 2]), 2 * e))
    print(ans)
t = int(input())
for _ in range(t):
    solve()

Solution (Python):
from sys import stdin, stdout, setrecursionlimit as srl
from threading import stack_size
from collections import deque, defaultdict as dd
from math import gcd, ceil, sqrt
from bisect import bisect_left as lb
from bisect import bisect_right as rb
from heapq import heapify, heappush, heappop
flush = stdout.flush
p = int(1000000000.0 + 7)

def get_ans(a):
    val = 2 * min(a)
    val2 = 0
    for i in range(1, len(a)):
        val2 = max(val2, min(a[i], a[i - 1]))
    return min(val, val2)

def optimize(k, a):
    if k == 0:
        return get_ans(a)
    z = a.index(min(a))
    z_ = a[z]
    a[z] = int(1000000000.0)
    val = optimize(k - 1, a)
    a[z] = z_
    z = a.index(max(a)) + 1
    if z != len(a):
        z_ = a[z]
        a[z] = int(1000000000.0)
        val = max(val, optimize(k - 1, a))
        a[z] = z_
    z = a.index(max(a)) - 1
    if z != -1:
        z_ = a[z]
        a[z] = int(1000000000.0)
        val = max(val, optimize(k - 1, a))
        a[z] = z_
    return val
tc = 1
tc = int(input())
for _ in range(1, tc + 1):
    (n, k) = map(int, input().split())
    a = list(map(int, input().split()))
    x = [(a[i], i) for i in range(n)]
    x.sort(reverse=True)
    for i in range(k - 1):
        (v, ind) = x.pop()
        a[ind] = int(1000000000.0)
        k -= 1
    print(optimize(k, a))
    pass

Solution (Python):
for _ in range(int(input())):
    (n, k) = map(int, input().split())
    a = list(map(int, input().split()))
    if k == n:
        print(10 ** 9)
        continue
    b = []
    for i in range(n):
        b.append((a[i], i))
    b.sort()
    i = 0
    while k > 1:
        a[b[i][1]] = 10 ** 9
        i += 1
        k -= 1
    ans = 0
    j = i
    for i in range(1, n):
        (x, y) = (a[i - 1], a[i])
        z = b[j][0] * 2
        if i - 1 <= b[j][1] <= i:
            z = b[j + 1][0] * 2
        z1 = b[j + 1][0] * 2
        ans = max(ans, min(max(x, y), z), min(min(x, y), z1))
    print(ans)