PROFIT - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: raysh07
Tester: iceknight1093
Editorialist: iceknight1093

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

N customers will visit your lemonade stand. The i-th customer is willing to pay Rs. i.
Each lemonade costs you Rs. X to make.
For each customer, you can choose to either sell the lemonade or send them away.

Find the maximum profit you can make.

EXPLANATION:

Each lemonade has a constant cost X to make.
So, for customer i,

  • If you send them away, you make a profit of 0, since nothing was made and nothing was sold.
  • If you choose to sell to them, you earn i but lose X from making the lemonade, for an overall profit of (i-X).

Since the choice can be made for each customer independently, it’s clearly only profitable to sell to those customers for whom i-X \gt 0, i.e. i \gt X.

So, the answer is simply

\sum_{i=X+1}^N (i-X)

An equivalent way of writing this is

\sum_{i=1}^N \max(0, i-X)

The above summation is easily implemented in linear time with a simple loop.

It’s also possible to solve the problem in \mathcal{O}(1) time with a bit of math.
Observe that since you only sell to people \gt X, persons X+1, X+2, \ldots, N will give you a profit of 1, 2, \ldots, N-X respectively.
So, the answer is the sum of 1+2+\ldots + (N-X), which is well-known to equal

\frac{(N-X) \cdot (N-X+1)}{2}

Note that if N-X \le 0 then the answer is 0 instead.

TIME COMPLEXITY:

\mathcal{O}(N) or \mathcal{O}(1) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n, x = map(int, input().split())
    ans = 0
    for i in range(1, n+1): ans += max(0, i-x)
    print(ans)