Hello ! I am having trouble with Codeforces round #477 Div. 2 D — Resource distribution.
I cannot find any special test case in which this type of thinking is wrong :
Explanation of the code
First we can binary search the minimum k1 such that the value of the smallest element >= x1 / k1, after that we can just sort the vector and remember the initial positions of the elements that so we can just verify that the (k1 + 1)-th element >= x2 / (n — k1), because n — k1 is the maximum number of elements for the second service that we divide x2 by. If the inequality is correct then we can just output the solution(meaning we output the indices of elements in the vector because we stored them). Do the same by finding the minimum k2. If you find no solution output No
Observation : if the smallest elements of the groups respects the condition of value >= x / k then the rest of the elements will respect it.
Fact : The smallest element of the vector needs to be in a group also.
A conclusion of the fact : We can just find ki(where i is 1 or 2, we analyze both), then to be sure that we can build the other group we can find the most suitable case to be biggest n — ki.
Another Conclusion : We can binary search ki, and to have the largest numbers, so by the observation we made earlier, we can just grab the smallest elements for this group after which we get the most suitable condition,
Conplexity : Complexity of O(N + log2(N) * 2 + N * log2(N)) = O(NlogN).
But with this type of thinking i get a WA on test 5 ! I would really thank anybody who helps me ! This is my submission 39044055