GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

Tuesday 16 August 2022

[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 a1,a2,,an fell down on you from the skies, along with a positive integer kn.

You can apply the following operation at most k times:

  • Choose an index 1in and an integer 1x109. Then do ai:=x (assign x to ai).

Then build a complete undirected weighted graph with n vertices numbered with integers from 1 to n, where edge (l,r) (1l<rn) has weight min(al,al+1,,ar).

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 max1u<vnd(u,v), where 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 (1t104).

Solution Click Below:-  👉CLICK HERE👈
👇👇👇👇👇

 Description of the test cases follows.

The first line of each test case contains two integers n and k (2n1051kn).

The second line of each test case contains n positive integers a1,a2,,an (1ai109).

It is guaranteed that the sum of n over all test cases does not exceed 105.

Output

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

No comments:

Post a Comment