I am stuck on this one problem for over 2 days from a contest
NOTE: THE CONTEST IS ALREADY OVER. IT IS QUESTION 4 ON THIS CONTEST(CodeDrift: 2 Pointers)
You are given an array of size N.
A subarray A[l..r] contains all the elements from A[l] to A[r] inclusive. A subarray is scaler subarray
if A[l] + A[r] ≡ max(A[l..r]) mod (B)
where B is an integer and max() function is maximum number in the subarray
Find the total number of scaler subarrays. Since the answer can be large return the answer modulo 109 + 7
1 <= N, B <= 5*105
1 <= A[i] <= 109
A : [8, 7]
B : 4
A : [4, 5, 3, 8, 8]
B : 5
A : [1, 10, 2, 5, 3, 6, 4]
B : 3
What i have tried so far
I tried to solve this naively using two loops in O(N2)
time complexity but was not able to turn it into O(N log N)
I tried to do divide and conquer but was not able to get a merge step
If an array is an mountain then finding answer is easy . Just iterate for A[r]. Until the peak of the mountain, since max is same as A[r] in this region, it leaves to find A[l] ≡ 0 mod(B) in A[0..r].
Now for the downhill slope one can partition the problem in 2 parts. A[0..peak] and part A(peak..ar].
For part A[0..peak] max remains constant and we can look for (mx - A[r]) mod B in A[0..peak]
For part A(peak, A[r]) if we take any element as A[l] then max is the same as A[l]. This implies a A[l..r] is scaler subarray if A[r] ≡ 0 mod(B). so all the elements in A(peak, A[r]] will form a subarray starting at itself and ending at A[r].
I tried to break the array in list of mountains and solve for mountain, but was unable to do the merge step, i.e; when A[l] and A[r] belong to different mountains.
I tried to do it using 2 pointers, cause all the problems in that contest was successfully solved using 2 pointer method. Also the name of contest is 2 pointers.
I hope this information is enough. For any other info or query please mention me in the comment