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, # ^ |
          Vote: I like it 0 Vote: I do not like it

        We can get rid of extra $$$log$$$, by doing MO on big ranges. But still, for $$$n \le 5*10^5$$$ it would be TL.

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

          Actually $$$O(Nlog^2(N))$$$ is fine, for $$$N=5*10^5$$$ there are $$$2*10^8$$$ operations in the worst case.
          I had submitted the same solution and it works fine.

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

            Damn man, I had the same thought but didn't implement it. I thought it would be N**2 in worst case. By the way what rank did u get in that contest

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

        Can you please explain or give some intuition why it is O(NlogN)?

        → 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