| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | maomao90 | 163 |
| 2 | Um_nik | 163 |
| 4 | atcoder_official | 161 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | nor | 153 |
| 9 | Dominater069 | 153 |
You have an array $$$arr$$$ with $$$n$$$ elements. Let number $$$i$$$ occurs in multiset $$$Q$$$ $$$arr_i$$$ times. How to get random number from multiset $$$Q$$$ faster than $$$O($$$$$$\log n$$$$$$)$$$?
$$$n$$$ <= $$$1e5$$$, $$$arr_i$$$ <= $$$1e9$$$
Is this even solvable?
I think that this one is $$$O(logn)$$$:
Generate random number from $$$1$$$ to sum of elements of array $$$arr$$$. The answer will be minimum $$$i$$$ such that sum of elements of array $$$arr$$$ from $$$1$$$ to $$$i$$$ is greater than equal to this random number using binary search.
You need to clarify this. Why can't I for O(1) take first item from Q? What "get random numner" there means? What multiset is for in this task?
In this task "multiset" is not name of data structure.
Try this : https://en.wikipedia.org/wiki/Alias_method
That's what I was looking for. Thanks!
Sometimes I wonder what are the trends that determine whether a post would get straight up downvoted or not.
Now I do wonder too.