Corona Scare | CodeChef

What is the approach to be followed to get 100 points in this question?

I have tried to get that in O(n) but it failed in some of the test cases?

code : notepad.pw / um02vfzz | The napkin of the internet.

You can use KMP algorithm for pattern searching.

Create two new arrays from the differences of adjacent elements. One for a[] and one for b[]. Now apply KMP search.

I understand the approach. Could you provide the code for better understanding please? Thank you @sayanmedya

1 Like

Thanks a lot bro :smile:

What are you actually doing in this line

  if (abs(b[i - j] - a[0]) <= x)
             ans++;

The rest is same as KMP and how finding a match with adjacency difference gives the answer?

Remember the pattern we matched against the array b was difference array.
Here i - j is the index where the difference array matches.
Let’s have a look at the sample testcase,

Here, B\_Diff=\{1,1,1,1,1\} and A\_Diff=\{1,1,1\}

Now, A\_Diff matches in 3 different indices, 0,1,2

The above condition checks if that index can be an answer or not by finding a suitable x as specified in the question.

So by this condition index 2 is not a solution even though it matches.

The question talks about adding some number x to the whole array A[]. Now, whatever value we are going to add with the array, the difference will always remain same. So if A[1,...,n]+x=B[i,...,i+n-1] holds, their difference will also be same. Thus matching difference gives us answer.

2 Likes

K i got it

I have seen that you have solved all the problems. Could you please explain solution for the problems

  1. CodeChef: Practical coding for everyone
    2)CodeChef: Practical coding for everyone

thanks in advance

Problem’s name is good.