All Tracks Algorithms Greedy Algorithms Basics of Greedy Algorithms Problem

Rjit need leaves
Tag(s):

Algorithms, Easy-Medium, Greedy

Problem
Editorial
Analytics

Rjit being fond of traveling, needs some leaves from his office for the same. Once in his office, the Monk claimed that no one can split the given array of $$N$$ elements into less than or equal to $$K$$ $$Special \; Subsequences$$. Being greedy for leaves, Rjit accepted his challenge.

In case Rjit succeeds in the challenge, and let's say he found $$X$$ $$Sepecial \; Subsequences$$ in the array, then he will get $$K-X$$ number of leaves.

$$Special \; Subsequences$$ should follow the conditions mentioned below:

  • The Subsequence should be in decreasing order.
  • The adjacent elements should have difference exactly equal to $$1$$.

Help Rjit to maximize the number of leaves. In case Rjit fails in Monk's challenge, print $$-1$$.

Note: We consider a splitting of the array to be valid, if each element of the array occurs in exactly one $$Special \;Subsequence$$ present in the split.

Input format:
The first line contains T, the number of test cases. For each test case, two integers N and K will be given. Following that line, the next line contains N space separated integers denoting array elements $$A_i$$ of array $$A$$.

Output format:
You've to print $$-1$$, if Rjit fails in Monk's challenge, else print the maximum leaves he can get.

Constraints:
$$1$$ ≤ T ≤ $$10$$
$$1$$ ≤ N ≤ $$10^5$$
$$1$$ ≤ K ≤ $$10^5$$
$$1$$ ≤ Ai ≤ $$10^9$$

Sample Input-0:
$$1$$
$$4$$ $$1$$
$$4$$ $$3$$ $$2$$ $$1$$

Sample output-0:
$$0$$

Sample explanation-0:
Here Rjit will find $$1$$ $$Special \; Subsequence$$ that is $$4,3,2,1$$. So number of leaves he will get is $$K-1 = 1-1 = 0$$.

SAMPLE INPUT
1
4 3
1 2 3 4
SAMPLE OUTPUT
-1
Explanation

Here Rjit fails in Monk's challenge, and not able to find number of Special Subsequences less than or equal to $$K$$. So answer is $$-1$$.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Scala 2.11.8, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

CodeMonk (Greedy Technique)

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications