Problem 3: Distributing Ballot Boxes

https://open.kattis.com/problems/ballotboxes

Key Idea 1:

Given an integer $n$ representing the maximum number of people assigned to one ballot box, we can calculate the minimum number of ballot boxes needed for each city given its population. In particular, $n$ is a feasible maximum number of people assigned to one box if the sum of the minimum number of ballot boxes needed for each city is not bigger than $B$. In other words,

$$B \geq \sum_{i=1}^N \left\lceil \frac{a_i}{n} \right\rceil$$

For each test case, we want to find the smallest $n$ that satisfies the above equation.

Linear Approach:

For $n = 1$to $\max_{i=1}^N(a_i)$, compute the sum of the minimum number of ballot boxes needed for each city and take the first $n$ whose sum is less than or equal to $B$.

This approach has a time complexity of $O(N^2)$. Since $1 \leq N \leq 500000$, this is too slow.

Key Idea 2:

• If $n$ is not a feasible maximum number of people assigned to one box, then all integers less than $n$ are also not a feasible maximum number of people.

• However, if $n$ is a feasible maximum number of people assigned to one box, then all integers greater than $n$ cannot be the maximum number of people assigned to one box in the most efficient assignment.

Therefore, we can find find the smallest $n$ that satisfies the above equation using binary search.