I notice there are some problems in binary search category where you have to find k-th element of a sequence like[Ntarsis' Set][K-th Not Divisible by n]. How can I develop this kind of problem solving approach.
№ | Пользователь | Рейтинг |
---|---|---|
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 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 156 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
9 | nor | 153 |
I notice there are some problems in binary search category where you have to find k-th element of a sequence like[Ntarsis' Set][K-th Not Divisible by n]. How can I develop this kind of problem solving approach.
Название |
---|
In problems where you need to find the k-th element in terms of a certain criterion (for example k-th smallest), you could store the numbers in a vector and sort them accordingly using a custom comparator. While this approach allows finding k_th element in O(log N), it does not support updates to the array (removal, insertion, modification ...). The problem with using std::set is iterator advancement has linear complexity. That is why a certain data structure called ordered_set is used. You can learn about them here:https://codeforces.me/blog/entry/11080. While this data structure may seem like a great alternative to set, this data structure should be used only when necessary as it has a huge constant factor and will result in TLE when used excessively. The problems you provided do not need this data structure, they can be handled with classic binary search with a check() function. If the check function tells you that the current element comes later than the k-th element (k+1th perhaps), you should adjust L or R accordingly. I hope this helps.