BAKECAKE2 - 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:

Baking a cake needs N different types of ingredients.
Chef has B_i units of ingredient i, and needs A_i units of it.
Buying a unit of any ingredient costs 1 coin.

Find the minimum number of coins Chef needs to spend to be able to bake a cake.

EXPLANATION:

Let’s look at only ingredient i.

  • If A_i \leq B_i, Chef already has enough of the ingredient, and doesn’t need to buy anything.
  • If A_i \gt B_i, Chef needs to buy (A_i - B_i) units more of it.
    This of course has a cost of (A_i - B_i), since each unit costs 1.

So, the answer is simply the sum of (A_i - B_i), across all i such that A_i \gt B_i.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    
    ans = 0
    for i in range(n):
        if a[i] > b[i]: ans += a[i] - b[i]
    print(ans)
1 Like