BAKECAKE3 - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author:
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

Chef needs 30 coins to bake a cake, and earns 50 coins by selling it.

Chef will sell cakes for N days.
Each day, X cakes will be available for sale.

On the i-th day, A_i customers will visit the shop and buy one cake each (as long as there are enough cakes available).

Find the maximum possible profit Chef can attain if X is chosen optimally.

EXPLANATION:

Suppose we fix the value of X. What will Chef’s profit be?

On the i-th day, he will bake X cakes. This has a cost of 30\cdot X coins.
Then, some customers will buy cakes. Specifically,

  • If X \leq A_i, all X cakes will be bought, for a revenue of 50\cdot X.
  • If X \gt A_i, only A_i cakes will be bought, for a revenue of 50\cdot A_i.

A simpler way of stating this is that Chef’s income for the day will be 50\cdot \min(X, A_i).

So, on the i-th day, Chef’s profit is 30\cdot X - 50\cdot \min(X, A_i).
Thus, for this fixed value of X, Chef’s overall profit is simply

\sum_{i=1}^N (30\cdot X - 50\cdot\min(X, A_i))

This is, of course, easily computed in linear time.

Now, what value of X should we choose to maximize the above quantity?
Well, we can just try them all!

Looking at the constraints, it can be seen that 1 \leq A_i \leq 100.
That is, no more than 100 people can come to the shop on any given day.
This makes baking more than 100 cakes in a day useless, i.e. we don’t need to consider X \gt 100 at all.

That leaves us with only 1 \leq X \leq 100, so we can just try each of them, compute the profit using the formula above, and take the maximum among them.
Because N is also small, being \leq 100, this is fast enough.

TIME COMPLEXITY:

\mathcal{O}(N\cdot\max(A)) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    ans = 0
    
    for x in range(max(a) + 1):
        cur = 0
        for i in range(n):
            cur -= 30*x
            cur += 50*min(x, a[i])
        ans = max(ans, cur)
    print(ans)
1 Like