SHISTR - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest

Author: sahilarora.535

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

None

PROBLEM:

Given a string S of length N and Q queries, and in each query, integers L, R and K, add K to all the characters at index L to R inclusive. After processing all the queries, output the final string.

EXPLANATION:

If we go by brute force, the number of computations will reach a maximum of T*N*Q, i.e. 2.5 * 10^8, which will give us a TLE. So we need to process the queries faster. Since we do not need to view the output in between the queries, we can use a difference array and perform each query in O(1), which will reduce the computations required to T*N = 5 * 10^5.

Difference array is the array in which every element stores the difference between this element and the previous element.
Assume that initially we don’t have anything to add to the array. So make an array V of size N, which will keep a record of how much to add to which element, initialized to 0, and another array D of size N+2 and initialize it to 0 as well, since all elements of V are currently 0, so the difference between two consecutive elements will also be zero.

for each query, do:
    D[L] += K;
    D[R+1] -= K;
V[0] = D[1];
for i = 2 to N,
    V[i] = V[i-1] + D[i]

Now you can add the value from vector V to the respective element in the string.

AUTHOR’S SOLUTIONS:

Author’s solution can be found here.

SIMILAR PROBLEMS:

Way Out - WOUT

1 Like