A friend talked me about this problem and i don't know how to solve it or if there is a judge to make submitions.
You will be given an array of $$$N$$$ integers $$$A$$$. You know that $$$ 1 \leq N \leq 2000$$$ and $$$1 \leq A_i \leq 10^6$$$.
Is there any way to know for a fixed $$$1 \leq k \leq N$$$ the maximum number of times you can choose $$$k$$$ different elements from $$$A$$$ with the condition that if you choose indexes $$$p_1,p_2,...,p_k$$$ then you have to do $$$A_{p_i}-=1$$$ for every $$$1 \leq i \leq k$$$ and $$$A_i \geq 0$$$ should hold.
My idea is that every time, you have to choose the currently $$$k$$$ greatest elements (but i don´t know if this is optimal, i did´nt prove it). And i guess that the time complexity for this would be $$$O( $$$$$$\sum_{i=1}^{n} A_i $$$$$$ ) \approx 10^9 $$$ worst case.
Another version
You are free to choose $$$k$$$ in such a way that at the end of the process with that $$$k$$$ (the process described above) the sum of the remaining elements should be minimum. You have to find the greatest $$$k$$$ meet this condition.
Any comment is welcome. Thank you.
It can be proved that:
A sequence of length N can be converted into a zero sequence if and only if:
\sum_i(A[i]) is a multiple of K and \max_i(A[i]) * K <= \sum_i(A[i]).
Prove:
For the "only if" part, it's obvious — if \sum_i(A[i]) is not a multiple of K, or if \max_i(A[i]) is larger than (\sum_i(A[i]) / K), there'll be no way to convert the original sequence to 0, 0, ..., 0.
For the "if" part:
Consider a sequence B: A[1] '1's followed by A[2] '2's followed by A[3] '3's ...
Devide the sequence B into K segments, each of length (\sum_i(A[i]) / K).
Then, for each i in [1, \sum_i(A[i]) / K], let p[j] be the i-th element of the j-th segment. it can be proved that for each fixed i, p[j] will be pairwise different(otherwise we can show that one number appear more than (\sum_i(A[i]) / K) times in B).
So for the second problem, we only need to print the largest divisor of \sum_i(A[i]) that is no larger than (\sum_i(A[i]) / \max_i(A[i])).
For the first problem, first you can do a binary search on how many operations can we do then compute the \max_i(A[i]) in that case. Also, a linear sweepline is OK.
Thanks for your response, i only have one question, i didn´t understand entirely the solution for the first problem, how will you know the number of operation with a binary search? And what do you mean by "then compute the \max_i(A[i]) in that case."?
Simply do a binary search on what the answer(maximum number of operations possible). And then you'll get to know for each a[i] what it will be after all operations in the optimal way (denoted by a'[i]): \sum_i(a[i] — a'[i]) must be K * [the number of operations) and \max_i(a[i] — a'[i]) must be as small as possible.