PROBLEM LINK:
Author: Shrey Kaushik
Testers: Rahul Sawantdesai , Himanshu Shukla. Mayuresh Patle
Editorialist: Shrey Kaushik
DIFFICULTY:
MEDIUM
PREREQUISITES:
String matching and basic observations.
PROBLEM:
Given is a password which is an array of N integers (call it A) and an array of M integers entered by Bob (call it B).
We need to find the number of subarrays of the array B which are valid passwords.
A valid password is an array of length N (call it C) iff \exists x such that |x| \leq X and A_i = C_i+x holds for all 1 \leq i \leq N.
EXPLANATION:
For the first subtask, since N \leq M \leq 10^3 we can apply brute force which is trying out all possible subarrays of length N of the array B one by one. There are M-N+1 such subarrays.
Now take the difference between the first element of A and the first element of the considered subarray C (call it x) and check whether the absolute value of that difference is \leq X.
If it is, then check if A_i = C_i+x holds for all 2 \leq i \leq N Else simply go to the next subarray.
Time complexity of Brute Force approach - O(NM).
Let’s come to the final subtask now.
Since the offset (or difference) x can be different for different subarrays, we need to manipulate the arrays somehow to apply any standard string matching algorithm.
Here comes the magic, what if we consider the difference arrays of A and B.
Given an array of numbers, an array constructed by replacing each element by the difference between itself and the previous element, except for the first element, is known as the difference array.
Let’s call the difference array of A as A\_difference and the difference array of B as B\_difference.
Now let’s see what happens when a subarray of B\_difference of length N-1 matches the array A\_difference.
A\_difference has elements {A_2 - A_1, A_3 - A_2,…A_N - A_{N-1} }.
Any subarray of B\_difference has elements - {B_{i+1} - B_{i}, B_{i+2} - B_{i+1},…B_{i+N-1} - B_{i+N-2}}.
If this subarray matches with A\_difference, it is easy to say that B_{i} - A_1 = B_{i+1} - A_2 = ….= B_{i+N-1} - A_{N}.
Then the only check to make now is that if the absolute value of this difference is less than or equal to X.
Thus, we can use the KMP algorithm to find such subarrays(or any other string matching algorithm which works in linear or linearithmic time).
Time complexity of this approach - O(N+M).
Setter’s solution
Please feel free to share your approaches as well!!