COOLER7 - Editorial

editorial
,
1

PROBLEM LINK:

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

Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

An air conditioner needs X minutes to drop the temperature from X to X-1.
The current temperature is N, and you want to drop it to M.
How many minutes are needed?

EXPLANATION:

The temperature drops by 1 at each stage.
So, to reach M from N, we need to drop N \to N-1, then N-1 \to N-2, and so on sequentially till the final drop is M+1 \to M.

Since the cost of the drop X \to X-1 is X, the total cost of the above drops is

N + (N-1) + (N-2) + \ldots + (M+1)

This value can be found in linear time using a loop.

Alternately, a constant time solution is to apply the formula for summing up integers from 1, i.e.

1+2+\ldots + N = \frac{N\cdot (N+1)}{2}

With this, we have

N + (N+1) + \ldots + (M+1) = (1+\ldots + N) - (1+\ldots + M)

so we obtain the value

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

TIME COMPLEXITY:

\mathcal{O}(1) per testcase.

CODE:

Editorialist's code (PyPy3, Looping) 
for _ in range(int(input())):
    n, m = map(int, input().split())
    
    ans = 0
    for i in range(m+1, n+1):
        ans += i
    print(ans)
Editorialist's code (PyPy3, Formula) 
for _ in range(int(input())):
    n, m = map(int, input().split())
    print(n*(n+1)//2 - m*(m+1)//2)