Editorial

Key 1: Frequency

The first key observation is that the actual values of the given items do not matter; only the frequency does. In other words, the list [1, 2, 3, 3, 3, 4, 4] would produce the same result as [5, 6, 7, 7, 7, 8, 8].

Using this, we can construct a list of frequencies of the given items; in the case above, the frequency table would be [1, 1, 3, 2].

Key 2: Bucketing

For each bucket, strictly more than half of its content must be identical. In other words, if a bucket has ~x~ of the same items as the majority, then it can hold up to ~2x - 1~ items.

This also has the implication that we should select the most frequently appearing item to make the first bucket and see if it can hold all items, then the second most frequently appearing item, and so on, repeat until the capacity of all buckets sums to be at least the total number of items.

For example, given the above example with a total of ~n = 7~ items with the frequency table [1, 1, 3, 2]:

• Sort it to get [3, 2, 1, 1] as the sorted frequency table, then
• Make the first bucket with the first ~3~ items, which can hold up to ~2 \times 3 - 1 = 5~ items. As there are a total of ~7~ items, the one bucket will not be enough to hold all items in.
• Make the second bucket with the next ~2~ items, which can hold up to ~2 \times 2 - 1 = 3~ items. Now that the two buckets have a total capacity of ~5 + 3 = 8~ items, which is enough to hold all items in.

Implementation

n = int(input())
d = dict()

for _ in range(n):
    i = int(input())
    if i not in d:
        d[i] = 0
    d[i] += 1

freqs = sorted(d.values(), reverse=True)

bin_count = 0
capacity = 0

for i in freqs:
    bin_count += 1
    capacity += i * 2 - 1
    if capacity >= n:
        break

print(bin_count)