Longest Strike Codeforces Solution | Codeforces Problem Solution 2022

Longest Strike Codeforces Solution | Codeforces Problem Solution 2022

F. Longest Strike

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Given an array 𝑎$a$ of length 𝑛$n$ and an integer 𝑘$k$, you are tasked to find any two numbers 𝑙$l$ and 𝑟$r$ (𝑙≤𝑟$l\le r$) such that:

• For each 𝑥$x$ (𝑙≤𝑥≤𝑟)$(l\le x\le r)$, 𝑥$x$ appears in 𝑎$a$ at least 𝑘$k$ times (i.e. 𝑘$k$ or more array elements are equal to 𝑥$x$).
• The value 𝑟−𝑙$r-l$ is maximized.

If no numbers satisfy the conditions, output -1.

For example, if 𝑎=[11,11,12,13,13,14,14]$a=[11,11,12,13,13,14,14]$ and 𝑘=2$k=2$, then:

• for 𝑙=12$l=12$, 𝑟=14$r=14$ the first condition fails because 12$12$ does not appear at least 𝑘=2$k=2$ times.
• for 𝑙=13$l=13$, 𝑟=14$r=14$ the first condition holds, because 13$13$ occurs at least 𝑘=2$k=2$ times in 𝑎$a$ and 14$14$ occurs at least 𝑘=2$k=2$ times in 𝑎$a$.
• for 𝑙=11$l=11$, 𝑟=11$r=11$ the first condition holds, because 11$11$ occurs at least 𝑘=2$k=2$ times in 𝑎$a$.

Solution Click Below:-  CLICK HERE

A pair of 𝑙$l$ and 𝑟$r$ for which the first condition holds and 𝑟−𝑙$r-l$ is maximal is 𝑙=13$l=13$, 𝑟=14$r=14$.

Input

The first line of the input contains a single integer 𝑡$t$ (1≤𝑡≤1000$1\le t\le 1000$) — the number of test cases. The description of test cases follows.

Lucky? Codeforces Solution

Equal Candies Codeforces Solution

Most Similar Words Codeforces Solution

X-Sum Codeforces Solution

Eating Queries Codeforces Solution

Longest Strike Codeforces Solution

White-Black Balanced Subtrees Codeforces Solution

Maximum Crossings (Easy Version) Codeforces Solution

Maximum Crossings (Hard Version) Codeforces Solution

The first line of each test case contains the integers 𝑛$n$ and 𝑘$k$ (1≤𝑛≤2⋅105$1\le n\le 2\cdot {10}^5$, 1≤𝑘≤𝑛$1\le k\le n$) — the length of the array 𝑎$a$ and the minimum amount of times each number in the range [𝑙,𝑟]$[l,r]$ should appear respectively.

Then a single line follows, containing 𝑛$n$ integers describing the array 𝑎$a$ (1≤𝑎𝑖≤109$1\le a_i\le {10}^9$).

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

Output

For each test case output 2$2$ numbers, 𝑙$l$ and 𝑟$r$ that satisfy the conditions, or "-1" if no numbers satisfy the conditions.

If multiple answers exist, you can output any.

Join Now for Solution:-