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 | 3750 |

2 | Benq | 3726 |

3 | cnnfls_csy | 3690 |

4 | Radewoosh | 3649 |

5 | jiangly | 3631 |

6 | orzdevinwang | 3558 |

7 | -0.5 | 3545 |

8 | inaFSTream | 3477 |

9 | fantasy | 3468 |

10 | Rebelz | 3415 |

# | User | Contrib. |
---|---|---|

1 | adamant | 178 |

2 | awoo | 167 |

3 | BledDest | 165 |

4 | Um_nik | 164 |

5 | maroonrk | 163 |

6 | SecondThread | 159 |

7 | nor | 156 |

8 | -is-this-fft- | 154 |

9 | kostka | 146 |

10 | TheScrasse | 143 |

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/23/2023 03:40:46 (k3).

Desktop version, switch to mobile version.

Supported by

User lists

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