PROBLEM LINK:
DIFFICULTY:
Easy
PREREQUISITES:
Difference Sequence, Coordinate compression
PROBLEM:
You’re given an array of N integers. You’ve to process M types of queries where each
query asks you to add/ subtract a constant integer from a consecutive range of
the array. In the end, you’re to find out the minimum and maximum number of the array.
QUICK EXPLANATION:
Maintain a difference sequence of the array. Each query can be processed in
O(1)
time. After that restore the whole sequence in O(N) time and find the minimum
and maximum. Total time taken per test case is O(N+M)
DETAILED EXPLANATION:
Let A be the given array where initially A[i] = i for all i. Let’s
create another array D of length N-1 where D[i] = A[i+1] - A[i]. Initially all
entries of D are 1. What happens to D when you add z to A[x…y] ?
D[x-1] increases by z and D[y] decreases by z. Besides these two entries, no
other entries of D change! This is convenient because we can update D in
O(1)
time by changing only these two entries. Now we have processed all queries and
made changes in D. How do we restore the original sequence again? Well if we can
keep track of A(1) and have all the entries of D, we can restore it.
D[1] = A[2] - A[1] Rearranging, we get
A[2] = A[1] + D[1] Similarly :
A[3] = A[2] + D[2]
.
.
.
A[N] = A[N-1] + D[N-1]
So we can restore the whole sequence of A. Once we do that, we can find min and
max values of A in O(N) time.
Time limit is a little strict for O(T(N+M)) solutions. We indeed do have a
faster solution. This solution is O(T * MlogM) and is a slight variant of the
previous algorithm. In previous algorithm, we’re reconstructing the whole
sequence A and then seeing each entry if it is min or max. This part of the
solution takes O(N) time. The observation to make here is that minimum and maximum
would appear only near the end points of the segment on which a query acts. This
is so because between the end points, A is monotonically increasing. As there are M queries, so there are O(M) critical points
which could be checked. Look at tester’s solution for a clean implementation of
this method. Another way of writing O(M logM) solution would’ve been to use a
segment tree only on critical points.
SETTER’S SOLUTION:
Can be found here.
TESTER’S SOLUTION:
Can be found here.
