CSCARE - Editorial

PROBLEM LINK:

Contest

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!!

5 Likes

If anyone wants a related problem…here it is:

4 Likes

Thanks buddy!

1 Like

can anyone help me in this question. as it is showing wrong verdict. and i m doing the same thing which is done in editorial.
please help me @shreyk5 @akshitm16
https://www.codechef.com/viewsolution/31310337

Line 65 will give runtime error in the next iteration when j becomes equal to n.
You need to update j properly.

1 Like

Thank u so much sir … :heart_eyes: :heart_eyes:

I tried to apply the KMP algorithm after reading the editorial but still getting a TLE, can anyone please find the mistake CodeChef: Practical coding for everyone