Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

### IWantToBeNutellaSomeday's blog

By IWantToBeNutellaSomeday, history, 10 months ago, , 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. Comments (4)
 » Why comment on an alt-account?
 » 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's followed by A '2's followed by A '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.