Welcome to WuJiGu Developer Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
1.3k views
in Technique[技术] by (71.8m points)

arrays - Tricky Data Structures and Algorithm Problem

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)

Problem Statement

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

Problem Constraints

1 <= N, B <= 5*105
1 <= A[i] <= 109


Example Input

A : [8, 7]
B : 4

A : [4, 5, 3, 8, 8]
B : 5

A : [1, 10, 2, 5, 3, 6, 4]
B : 3

Corresponding Output

1

3

11

What i have tried so far

  1. 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)

  2. I tried to do divide and conquer but was not able to get a merge step

  3. 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].

  4. 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.

  5. 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


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Answer

0 votes
by (71.8m points)
等待大神解答

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome to WuJiGu Developer Q&A Community for programmer and developer-Open, Learning and Share
...