Блог пользователя three_nil

Help needed for a question
Автор three_nil, история, 3 года назад, По-английски

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.

  • Проголосовать: нравится
  • +7
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Your pretty funny. Problem link?

→ Ответить
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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))$$$

→ Ответить
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить
    • »
      »
      »
      3 года назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      → Ответить
  • »
    »
    3 года назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить