**PROBLEM LINK** -

Author and Editoriallist - AmirReza PoorAkhavan

Tester - MohammadSina Pakseresht

Second Tester - Shayan CheshmJahan

**DIFFICULTY** –

**PREREQUISITES** –

Binary-search

**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

```
v.empty() || v.back() * c <= B
```

.

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:

```
int nw = 0;
for (int i = 0; i < n; i ++){
if (vec[nw].size() == k)
return 1;
if (vec[nw].empty() || (vec[nw].back() < inf / c && vec[nw].back() * c <= a[i])){
vec[nw].push_back(a[i]);
nw = (nw + 1) % X;
}
}
return 0;
```

**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

Tester’s code - here

Second tester’s code - here.