Problem Link:
Practice
Contest
Author: murugappan_s
Testers: sdssudhu,msv99999
Editorialist: murugappan_s
DIFFICULTY: Easy-Medium
PREREQUISITES: Greedy Algorithms
PROBLEM:
We have two arrays(A and B) each of size N. In one step we can choose any two index l and r such that 1≤l≤r≤N and increment B[i] by 1 for l≤i≤r.
Find the minimum number of steps required to make both are identical.
CONSTRAINTS:
- 1≤N≤100000
- 0≤B[i]≤A[i]≤10^9
SOLUTION:
There are different approaches to solve this problem. We would be discussing the greedy strategy here, but there is a nice divide-and-conquer solution, which is left for the audience to think.
Lets compute the difference array(C) where C[i]=A[i]-B[i].
Lets assume that we have somehow made the array identical for the first i-1 elements. Now,there are two cases to consider
Let number of steps performed till now be STEPS
Case 1: C[i]<=C[i-1]
In this case, the number of times the ith element has to be incremented is <= the number of times the (i-1)th element has to be incremented. So we can greedily choose ith element when (i-1)th element is chosen, thereby spending no extra effort for the ith element. Which implies that there is no change in the value of STEPS.
Case 2: C[i]>C[i-1]
In this case, the number of times the ith element has to be incremented is > the number of times the (i-1)th element has to be incremented. To minimize the extra effort required for the ith element, first we try to choose ith element whenever (i-1)th element is chosen. So, the ith element would have increased by C[i-1], now what is left is C[i]-C[i-1]. For the difference alone we have to take ith element separately without the help of (i-1)th element. Which implies that STEPS increases by C[i]-C[i-1].
Time Complexity: O(N)