NOTE: I was not able to solve it during the contest, but I was able to do it afterwards.

This is one type of binary_search problem. You will encounter many such problems. General binary_search which you might have studied(or will study) in the university is done over an array of numbers. In this kind of problems, you need to perform the binary_search over the entire solution space.

For e.g.: In this problem, you can consider the entire solution space as all numbers ranging from 1 to n (as you cannot have more than "n" copies).

So, step 1 of this problem is to find the maximum number of copies which can be cut out from the the given array. Let me call this value as val. How we are going to find val, I will come back to that later. Let us move to Step 2

Step 2

Now, given that if we want to cut out val copies from the given array, can we do that ?

In order to answer this question we need to first construct a frequency array (In this we will store the frequency of all given numbers).

We need to construct an array of length k We iterate over all elements over the frequency array. First we check that whether the given key in frequency array has value more than val. If it has a value more than val. Then this can be used in the construction of the array.

But there is an interesting catch here. Since, duplicates are allowed in the given answer, we might be able to use the same value again. So, we can use that value atmost floor(value/val) number of times.

So this is basically the can function being talked in the above tutorial.

Now coming back to Step 1.

We need to figure out what values of val are valid. Minimum Val = 0 Maximum Val = n If we do a binary_search over this, then we will be able to get the MAXIMUM possible value of val.

Another thing to note is binary_search can only be done when the array(solution space) is monotonically increasing. In this case, as mentioned in the tutorial, if you can create, val copies you can also create val - 1 copies.

Here is my solution: http://codeforces.me/contest/1077/submission/45915120