I have found an interesting problem like this: given_there are $n$ kind of cakes with amounts $a_1, a_2, ..., a_n$ (i.e.and for $1 \le i \le n$, there are $a_i$ cakes of the $i-$th kind for $1 \le i \le n$). We need to take out as much as $k-$ tuples of distinct cakes. WSo with the given value of $k \ge 1$ and array $a_1,a_2,...,a_n$, what is the maximum number of tuples can we get?↵
↵
↵
~~~~~_↵
↵
For example: we have $4$ kinds of cake as $(A,B,C,D)$ with amounts: $a[4] =\{(20,30,40,50 \})$ and $k=3$. We can get at most $45$ tuples as: $5$ tuples $(A,B,C)$ and $15$ tuples $(A,C,D)$ and $25$ tuples $(B,C,D)$.↵
~~~~~↵
↵
↵
↵
I came up with this idea to solve as follow: ↵
↵
<spoiler summary="Spoiler">↵
Denote $d$ as the number of $k-$tuple we can get then it is easy to check that $d \gle \dfrac{s}{k}$ with $s$ is the sum of all amounts. Then we can make this estimation stronger by the remark: the number of used cakes of each kind is also upper bounded by $\frac{s}{k}$, we iteratively update all numbers $a_i$ in the given array by this value., i.e $a_i = $ minimum of $a_i$ and $\dfrac{s}{k}.$ So we have the new array with new sum $s'$ and a new upper bound $\d \le \dfrac{s'}{k}$. We do this until there is no update and then get the answer.↵
</spoiler>↵
↵
By this idea, for the test case as: $a[5] =\{(1,2,3,1000,1000\})$ and $k=4$, I got the answer is $3$ after some iterations. And by checking with some other tricky test cases, I'm pretty sure this idea is true.↵
↵
I have two questions:i_Is this problem new a? And how to find a proof for this approach?_ Thanks for your help.
↵
↵
~~~~~
↵
For example: we have $4$ kinds of cake as $(A,B,C,D)$ with amounts: $a[4] =
~~~~~↵
↵
↵
I came up with this idea to solve as follow: ↵
↵
<spoiler summary="Spoiler">↵
Denote $d$ as the number of $k-$tuple we can get then it is easy to check that $d \
</spoiler>↵
↵
By this idea, for the test case as: $a[5] =
↵
I have two questions:
