Official

B - Bought Review Editorial by evima

Hints

Hint 0 If you want the average rating to be at least 33 stars, adding reviews with 11 or 22 stars would be a waste.

Hint 1 What does it mean for the average rating to be at least 33 stars? Let’s formulate it. (This formulation can explain Hint 0)

Hint 2 Suppose there were originally qq reviews with a total of pp stars.
Furthermore, suppose we add BiB_i reviews with ii stars.
In this case, the condition for the average rating to be at least 33 stars can be formulated as follows:
p+B1+2B2+3B3+4B4+5B5q+B1+B2+B3+B4+B5≥3\displaystyle \frac{p+B_1+2B_2+3B_3+4B_4+5B_5}{q+B_1+B_2+B_3+B_4+B_5} \ge 3
From here, proceed with transforming the equation.

Hint 3 By transforming the equation, we obtain the following:
p+B1+2B2+3B3+4B4+5B5≥3×(q+B1+B2+B3+B4+B5)p+B_1+2B_2+3B_3+4B_4+5B_5 \ge 3 \times (q+B_1+B_2+B_3+B_4+B_5)
p−3q−2B1−B2+B4+2B5≥0p-3q-2B_1-B_2+B_4+2B_5 \ge 0
From this equation, we can see that adding reviews with 33 stars or less is meaningless or harmful.
Continuing with the transformation by setting B1=B2=B3=0B_1=B_2=B_3=0, we get B4+2B5≥3q−pB_4+2B_5 \ge 3q-p.
Let’s consider satisfying this equation with the minimum bribe.

Hint 4 Regarding the equation in Hint 3, it can be seen that “adding two 44-star reviews” has the same effect as “adding one 55-star review”.

Hint 5 “Adding two 4-star reviews” has the same effect as “adding one 5-star review.”
In other words, these two actions can be exchanged.
Using this exchange, we can see that (for any additional costs P4,P5P_4, P_5) there are not so many optimal candidates for B4,B5B_4, B_5.
Furthermore, by calculating the necessary costs for several patterns and taking the min⁡\min of them, we can solve this problem.

posted:
last update:

2025-04-06 (Sun)
02:56:51 +00:00