[Solution] Empty Graph Codeforces Solution

D. Empty Graph

time limit per test

1.5 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

An array of 

𝑛$n$ positive integers 𝑎1,𝑎2,…,𝑎𝑛$a_1,a_2,\dots ,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≤𝑖≤𝑛$1\le i\le n$ and an integer 1≤𝑥≤109$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$1$ to 𝑛$n$, where edge (𝑙,𝑟)$(l,r)$ (1≤𝑙<𝑟≤𝑛$1\le l<r\le n$) has weight min(𝑎𝑙,𝑎𝑙+1,…,𝑎𝑟)$min(a_l,a_{l+1},\dots ,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 max1≤𝑢<𝑣≤𝑛d(𝑢,𝑣)$\underset{1\le u<v\le n}{max}\mathrm{d}(u,v)$, where d(𝑢,𝑣)$\mathrm{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≤𝑡≤104$1\le t\le {10}^4$).

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

 Description of the test cases follows.

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

The second line of each test case contains 𝑛$n$ positive integers 𝑎1,𝑎2,…,𝑎𝑛$a_1,a_2,\dots ,a_n$ (1≤𝑎𝑖≤109$1\le a_i\le {10}^9$).

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

Output

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