Editorial : Price Tags
Choose an integer $x \ge 2$. Every item with original price $c_i$ gets a new price $\lceil c_i / x \rceil$. You already own one price tag per item (with the old values). A tag can be reused on any item whose new price equals the tag’s face value; unmatched items require a freshly printed tag at cost $y$ each.
Maximize:
$$\text{income}(x) = \underbrace{\sum_{i=1}^{n} \left\lceil \frac{c_i}{x} \right\rceil}_{\text{revenue}} \;-\; \underbrace{(\text{tags to print}) \cdot y}_{\text{printing cost}}.$$Fix $x$. Let $\mathrm{old}[v]$ be the number of items with original price $v$, and $\mathrm{new}[v]$ the number of items whose new price is $v$. For each value $v$ we can reuse $\min(\mathrm{old}[v], \mathrm{new}[v])$ tags, so:
$$\text{tags to print} = n - \sum_{v} \min\!\bigl(\mathrm{old}[v],\; \mathrm{new}[v]\bigr).$$All original prices $c$ satisfying $(k-1)x < c \le kx$ map to the same new price $k$, so:
$$\mathrm{new}[k] = \bigl|\{i : c_i \in [(k-1)x+1,\; kx]\}\bigr|.$$For each block $k$:
- Revenue contribution: $\mathrm{new}[k] \cdot k$.
- Reusable tags: $\min\!\bigl(\mathrm{new}[k],\; \mathrm{old}[k]\bigr)$.
To query $\mathrm{new}[k]$ in $O(1)$, build a prefix sum over the frequency array:
$$\mathrm{pre}[i] = \#\{j : c_j < i\}, \qquad \mathrm{new}[k] = \mathrm{pre}[kx + 1] - \mathrm{pre}[(k-1)x + 1].$$In the implementation we iterate blocks as $i = 1, 1+x, 1+2x, \ldots$ and use $\mathrm{get}(i, i+x)$ for the count.
We try every $x$ from $2$ to $C$ (where $C = \max(c_i) + 1$, at most $2 \times 10^5$). Evaluating one $x$ takes $O(C / x)$ block iterations, so total work is:
$$\sum_{x=2}^{C} \left\lceil \frac{C}{x} \right\rceil \;\approx\; C \ln C \;\approx\; 2.4 \times 10^6.$$This is the standard harmonic-number complexity, well within the 2-second time limit.
Values $x > C$ are unnecessary: when $x \ge C$, every new price is $1$. This is already covered by $x = C$.
- Read prices. Build frequency array $\mathrm{cnt}[v]$ and prefix sum $\mathrm{pre}$.
- For each $x = 2, 3, \ldots, C$:
- Iterate blocks $i = 1, 1+x, 1+2x, \ldots$
- For each block, compute $\mathrm{cur}$ (items in block), the new price $k = (i + x - 1) / x$, accumulate revenue and reusable-tag count.
- Update the global best: $\mathrm{ans} = \max\!\bigl(\mathrm{ans},\; \mathrm{revenue} - (n - \mathrm{reused}) \cdot y\bigr)$.
- Output $\mathrm{ans}$.
- Time: $O(C \log C)$ per test case, where $C = 2 \times 10^5$. With $t \le 10$ test cases, total $\approx 2.4 \times 10^7$.
- Memory: $O(C)$ for the frequency and prefix arrays.