NINJA5 - K NUMBERS
You are given N numbers from 1 to N. Now, your task is to choose some numbers from the N numbers (including 1 & N) such that no two numbers are consecutive. As this is easy, you are given an extra task. You have to definitely choose K numbers which are given. Find the maximum number of numbers that you can choose in such a way.
The first line has an integer T, the number of test cases.
Then for each test case, the first line has two integers N and K.
Then the next line has K numbers which you should definitely chooose.
For each test case, print the maximum number of numbers that you can choose.
1 <= T <= 100
2 <= N <= 2 x 10 ^ 6
1 <= K <= N / 2
1 <= X[1...K] <= N
my accepted codes give:
if any of the two given K numbers are already consecutive, then just print 0. Worked for me!
Can't pass in raw Python and O(klogk) slower than O(n) in PyPy. Poorly set problem.
Very easy.AC in one go.O(n) solution exists.
no sorting :) just take char array of size max n.and O(n+t)solution
qsort giving TLE why? @himanshuz1Last edit: 2017-06-18 12:33:46
need to tighten the time.... O(n) easily excepted
O(n+k) solution passes it easily... while sorting gives tle
My code does not account for the already selected numbers being consecutive
If the question can be done in O(n), I think the constraints can be a little tighter. My O(nlogn) passed comfortably!