PROBLEM LINK  Author and Editoriallist  AmirReza PoorAkhavan DIFFICULTY – PREREQUISITES – Binarysearch EXPLANATION – We want to find the maximum possible $X$, such that we can do $X$ steps. Let's use binary search for finding this value. Now we need function check, such that it returns $true$ if we can make $X$ steps, and $false$, otherwise. We can check if we can do $X$ steps using a greedy solution: Sort the array, get $X$ vectors and set $currentVectorIndex = 0$ at first. We define a number is addable to some vector if the vector is empty or the last element of the vector is less than or equal to $\frac{TheNumber}{c}$. In another word, number $B$ is addable to vector $V$ if and only if Now start iterating on the array. For each element check if it can be added to the end of $currentVectorIndex$, if is possible, add it and set $currentVectorIndex = currentVectorIndex + 1 \mod X$. At any moment if all of the vectors have $k$ elements, break the process and return $true$. If the iteration finished with a vector with less than $k$ elements, return $false$. Psudocode of check function:
Proof: It's obvious that if $check(X)$ returns $true$, it's possible to make $X$ steps. For each vector, choose its elements and delete them. There are $k$ elements in each vector and there are $X$ vectors, so you have made $X$ steps obviously. Also, because we are picking the smallest remaining value each time for $currentVectorIndex$, if we don't find an answer, so there is no way to make $X$ steps. Time complexity: $\mathcal{O}(n \log n)$. IMPLEMENTATION  Author's code  here
This question is marked "community wiki".
asked 29 Jul '17, 22:41

Can u please add some more explanation, unable to figure it out ? answered 30 Jul '17, 01:58

Could someone please explain the basic logic from the start? Couldn't understand the editorial at all, comments didn't help much. answered 30 Jul '17, 10:19

The Basic Logic here is: not considering the elements of the array, answer lies between 0 to N/K. We can use binary search on range [0,N/K] and use check function as mentioned in Editorial above to check the mid value of binary search. If check(x)=true all values<=x is also true , so we check in the range> x+1 for the answer. answered 30 Jul '17, 16:40

can anyone please suggest some test case or please check the code where the logic is lacking? http://ideone.com/NXIGZY answered 02 Aug '17, 22:02
3
1 4 2 2 1 2 3 4 Your code outputs 1 for the above case while the answer should be 2.
(03 Aug '17, 18:40)
@adkroxx thanku for viewing my code.. :) but sorry for your test case it is giving correct answer.. http://ideone.com/sHhL4F
(04 Aug '17, 16:57)

Could someone please explain why the greedy algorithm gives the correct answer? I read h_bar's comment but I didn't understand the proof. answered 03 Aug '17, 23:05
