three_nil's blog

Help needed for a question
By three_nil, history, 4 years ago, In English

Given an array A of length N and a number B find the number of subarrays A[l....r] such that A[l]+A[r] and max(A[l...r]) are congruent modulo B
1<=N,B<=500000
 1<=A[i]<=1e9
 The contest of which this question is has ended.

  • Vote: I like it
  • +7
  • Vote: I do not like it

Comments Comments (14)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Your pretty funny. Problem link?

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I don't know any solution which uses two pointer technique.

I would solve this problem by iterating over maximums, that is for every element $$$A[i]$$$ find range $$$[L,R]$$$ in which $$$A[i]$$$ is maximum.

Now for every element this range can be split into parts $$$[L,i]$$$ and $$$[i+1,R]$$$, just iterate on the smaller range, that is if we have fixed $$$A[l]$$$ we just need to find the count of $$$(A[i]-A[l])$$$ under modulo $$$B$$$ in the range $$$[i,R]$$$.

This solution has time complexity of $$$O(Nlog^2(N))$$$

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How is this solution $$$O(Nlog^2(N))$$$.
    If we are iterating on $$$l$$$ for a given elements on worst it can be $$$O(n^2)$$$.
    Consider a increasing sequence. The $$$l$$$ for every element will from $$$1$$$ to $$$i$$$ , thus leading to $$$O(n^2)$$$. Correct me if I misunderstood something.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      No, we are not always iterating on $$$l$$$.

      If i-L>R-i we will then iterate $$$j$$$ in $$$[L, i]$$$ as my left border. Otherwise, iterate $$$j$$$ in $$$[i, R]$$$ as the right border.

      Iterating on smaller part guarantees $$$O(Nlog(N))$$$ iterations.

      → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    for every element A[i] find range [L,R] in which A[i] is maximum

    Is there any standard algorithm to do this? Also can you please share a pastebin link of your AC submission.

    → Reply