PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: Piyush Pransukhka
Tester: Abhinav Sharma, Aryan
Editorialist: Lavish Gupta
DIFFICULTY:
Easy-Medium
PREREQUISITES:
None
PROBLEM:
You are given two arrays A and B, each of size N. You can perform the following types of operations on array A.
- Type 1: Select any prefix of A and increment all its elements by 1.
- Type 2: Select any suffix of A and increment all its elements by 1.
Your task is to transform the array A into array B using the minimum number of operations. If it is impossible to do so, output -1.
For an array A having N elements:
- A prefix of the array A is a subarray starting at index 1.
- A suffix of the array A is a subarray ending at index N.
EXPLANATION:
Let us first try to solve the problem when the operations of only Type 1 are allowed.
Let us define a difference array D such that D_i = B_i - A_i for 1 \leq i \leq N.
Consider an index i such that D_{i+1} \gt D_i. Because we will have to add D_{i+1} to A_{i+1}, we will also end up adding D_{i+1} to A_i, as the operations of Type-1 applies on a prefix. This will make A_i'= A_i + D_{i+1} \gt A_i + D_i = B_i. Hence, we end up getting A_i' \gt B_i. This suggests that if D_{i+1} \gt D_i for any valid i, then we cannot convert A into B using only operations of Type 1. Otherwise, we can convert A into B using D_1 operations by applying O_i = D_i - \sum_{j = i+1}^{N}D_j operations on prefix of length i.
Now let us come back to our original problem. Let us again define the difference array D such that D_i = B_i - A_i for 1 \leq i \leq N. First of all, we will apply the operations of Type 2 only when absolutely necessary.
Consider an index i. If D_i \lt D_{i+1} we have seen that this cannot be solved using operations of Type 1 only. Hence we must apply operations of Type 2. To be more specific, we need to apply at least D_{i+1} - D_i operations of Type 2 on the suffix A[i+1 \ldots N] so that the condition D_i \geq D_{i+1} will hold. Let us apply these many operations of Type 2. We will update D_j for all i \lt j \leq N, and will continue the above process. If at any index, we have D_i \lt 0, then we cannot convert A into B (as we have only applied the minimum necessarily required operations till now). Otherwise, we will finally get an updated difference array, and we now need to apply D_1 additional operations of Type 1.
Implementation detail: To update D_j for all i \lt j \leq N, we can just maintain a running sum variable which will store the total number of Type 2 operations applied till that point. The updated D_i will be D_i + sum.
TIME COMPLEXITY:
O(N) for each test case.
SOLUTION:
Editorialist’s Solution
Tester-1’s Solution
Tester-2’s Solution