Hints: Price Tags

For a fixed $x$, the new price of item $i$ is $\left\lceil c_i / x \right\rceil$. Which original prices map to the same new price?

Answer to Hint 1: All prices $c$ in the range $[(k-1)x + 1, \; kx]$ map to the same new price $k$. So for a given $x$, the prices partition into blocks of size $x$.

Now, for reusing old price tags: you have a multiset of old values $\{c_1, \ldots, c_n\}$ and a multiset of required new values $\{\lceil c_1/x \rceil, \ldots, \lceil c_n/x \rceil\}$. How do you count how many old tags you can reuse?

Answer to Hint 2: For each distinct value $v$, let $\mathrm{old}[v]$ be the number of old tags with value $v$, and $\mathrm{new}[v]$ be the number of items whose new price is $v$. You can reuse $\min(\mathrm{old}[v], \mathrm{new}[v])$ tags for value $v$.

The total number of reusable tags is $\displaystyle c = \sum_{v} \min(\mathrm{old}[v], \mathrm{new}[v])$, and you must print $n - c$ new tags.

So the income for a given $x$ is:

$$\left(\sum_{i=1}^{n} \left\lceil c_i / x \right\rceil\right) - (n - c) \cdot y.$$

Can you evaluate this efficiently for a single $x$?

Answer to Hint 3: For a given $x$, iterate over the blocks $k = 1, 2, 3, \ldots$. Block $k$ covers original prices in $[(k-1)x+1, \; kx]$. You need:

1. The count of items in block $k$ (call it $\mathrm{cur}$) — this gives $\mathrm{new}[k] = \mathrm{cur}$.
2. Their contribution to total revenue: $\mathrm{cur} \cdot k$.
3. The reusable tags for value $k$: $\min(\mathrm{cur}, \mathrm{old}[k])$.

The old counts $\mathrm{old}[k]$ are just the frequency of price $k$ in the original array — precompute this once.

But how do you get $\mathrm{cur}$ (number of items with price in a range) in $O(1)$?

Answer to Hint 4: Build a prefix sum over the frequency array. Let $\mathrm{pre}[i]$ be the number of items with price $< i$. Then the count of items with price in $[l, r)$ is $\mathrm{pre}[r] - \mathrm{pre}[l]$, computed in $O(1)$.

This means evaluating a single $x$ takes $O(C / x)$ time, where $C = \max(c_i)$. Now, can you afford to try every $x$ from $2$ up to $C$?

Answer to Hint 5: Yes! The total work across all $x$ is:

$$\sum_{x=2}^{C} \frac{C}{x} \;\approx\; C \ln C.$$

With $C = 2 \times 10^5$, this is roughly $2.4 \times 10^6$ — very fast. This is the standard harmonic-sum / divisor-enumeration trick.

Answer to Hint 6: There is one subtle detail: you don’t need to try $x > C$, because for $x > C$ every item’s new price is $1$, so you can just evaluate that case directly (or note that $x = C$ already captures it since $\lceil c / C \rceil = 1$ for all $c \le C$).

Putting it all together:

1. Precompute $\mathrm{cnt}[v]$ (frequency of price $v$) and the prefix sum $\mathrm{pre}$.
2. For each $x$ from $2$ to $C$: iterate blocks, accumulate revenue, count reusable tags, update the best answer.
3. Output the maximum income.

Total complexity: $O(C \log C)$ per test case. Since $t \le 10$ and $C = 2 \times 10^5$, this is comfortable within the time limit.