IWantToBeNutellaSomeday's blog

By IWantToBeNutellaSomeday, history, 3 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.

• +20

 » 3 months ago, # |   -15 Why comment on an alt-account?
 » 3 months ago, # |   +3 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.
•  » » 3 months ago, # ^ |   0 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."?
•  » » » 2 months ago, # ^ |   0 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.