omggg's blog

By omggg, 4 years ago, In English

Given array and m. Find the index i such that A[i]%m is maximum. What is the best method to do that if I have incoming queries of m.

Any help is much appreciated, thanks :)

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

»
4 years ago, # |
Rev. 2   Vote: I like it +18 Vote: I do not like it

One Possible Approach may be,

Sort the Array $$$A$$$ For every $$$i$$$, you iterate over all it's multiples $$$x, x \le 2max(A)$$$, and find the maximum $$$a_i < x$$$. This should have the same complexity as of Sieve, i.e $$$M\log M$$$ with $$$M = max(m)$$$.

However for this the limits should be $$$a_i,m \leq 10^6.$$$

You may want to try 484B - Maximum Value

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

    too costly since there are queries for it, anyways thanks :)

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

      You can answer queries in O(1) I guess with the pre-computation.

»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Problem link please. We don't want to be helping cheaters. So please provide a link to your question.

»
4 years ago, # |
Rev. 5   Vote: I like it 0 Vote: I do not like it

nevermind

»
4 years ago, # |
  Vote: I like it +33 Vote: I do not like it

Say M is max possible m. Then there's $$$O(n\log{n} + n\sqrt{M} + q\sqrt{M}\log{n})$$$ solution. For each $$$m < \sqrt{M}$$$ calculate the answer naively, that takes $$$O(n\sqrt{M})$$$. Then sort the array to anwer other queries. For other m decompose the array into segments such that for each segment $$$l ... r$$$ $$$\lfloor{}\frac{a_l}{m}\rfloor{} = \lfloor{}\frac{a_{l+1}}{m}\rfloor{} = ... = \lfloor{}\frac{a_r}{m}\rfloor{}$$$. The answer is $$$max(a_r\mod{m})$$$ for each right boundary of each segment. There are $$$O(\sqrt{M})$$$, but i don't know if there's a way to decompose the array faster than $$$O(\sqrt{M}\log{n})$$$

»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

I have $$$O(n + q + M\cdot log(M))$$$ solution where $$$M$$$ is maximum over all m.

For each $$$1 \le m \le M$$$ calculate answer. Every number $$$x$$$ can be written as $$$x = y \cdot m + r$$$, where $$$y = \lfloor \frac{x}{m} \rfloor$$$ and module remainder $$$r < m$$$. Iterate over all $$$m$$$ and $$$y$$$ ($$$1 \le m \le M, 0 \le y \le \lfloor \frac{M}{m} \rfloor$$$). Now find maximum $$$a[i] < y \cdot m + m$$$ and update answer for $$$m$$$ as $$$a[i]$$$ % $$$m$$$ (you need store result for fast search maximum $$$a[i]$$$). Time complexity is $$$O(\sum_{m=1}^{M}\frac{M}{m}) = O(M\cdot log(M))$$$ (harmonic series).

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

    Hey thanks a lot for the approach :)