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 :)
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
Name |
---|
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
too costly since there are queries for it, anyways thanks :)
You can answer queries in O(1) I guess with the pre-computation.
Problem link please. We don't want to be helping cheaters. So please provide a link to your question.
"/
nevermind
lol okay
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})$$$
Thanks a lot!
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).
Hey thanks a lot for the approach :)