Price Tags

Let the original prices form a multiset. If we choose some integer $x>1$, every item with old price $c$ gets new price

$$\left\lceil \frac{c}{x} \right\rceil.$$

After that, we need price tags for the multiset of new prices. We already own price tags for the multiset of old prices. Since tags are just numbers, the maximum number of reused tags is exactly the multiset intersection size:

$$\sum_v \min(\text{oldCnt}[v], \text{newCnt}[v]).$$

No matching drama, no greedy ceremony. If we need five tags saying 7 and already have two tags saying 7, we reuse two. That's it.

So for a fixed $x$, the income is

$$\text{income}(x)=\sum_i \left\lceil \frac{c_i}{x} \right\rceil -y\left(n-\sum_v \min(\text{oldCnt}[v],\text{newCnt}_x[v])\right).$$

We need maximize this over all integer $x>1$.

Useful range for $x$

Let $M=\max c_i$. If $x>M$, then every price becomes $1$, because $1 \le c_i < x$ implies $\lceil c_i/x\rceil=1$.

So every $x>M$ gives the same result. It is enough to test

$$x=2,3,\dots,M+1.$$

The value $x=M+1$ covers all huge discounts.

Computing one $x$ fast

For a fixed $x$, which original prices become a new price $v$?

$$\left\lceil \frac{c}{x} \right\rceil=v$$

means

$$(v-1)x < c \le vx.$$

So all prices in the integer interval

$$[(v-1)x+1,\ vx]$$

turn into $v$.

If we store frequencies of original prices and build a prefix count array

$$pref[k]=\#\{i:c_i\le k\},$$

then the number of items that become $v$ is

$$\text{newCnt}_x[v]=pref[\min(vx,M)]-pref[(v-1)x].$$

That gives us each bucket in $O(1)$.

For this same bucket:

• it contributes $v\cdot \text{newCnt}_x[v]$ to the total new item value;
• it contributes $\min(\text{oldCnt}[v],\text{newCnt}_x[v])$ reusable tags.

Then after all buckets are processed:

$$\text{printed}=n-\text{reused},$$

and we update the answer with

$$\text{sumNew}-y\cdot\text{printed}.$$

Why this is fast enough

For one fixed $x$, the number of possible new prices is about $M/x$, because buckets have size $x$.

So the total work over all tested $x$ is

$$\sum_{x=2}^{M+1} O\left(\frac{M}{x}\right)=O(M\log M).$$

With $M\le 2\cdot 10^5$, this is easily fine. The answer can be negative because printing tags can cost an absurd amount, so use long long unless you enjoy self-inflicted pain.