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.
). If there does not exist a answer we will run out of array elements. Hope the above helps :{D