Hi all. Could some please make me understand what it is with an example? I'll appreciate it. DO you have some problems to apply it?
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3985 |
| 2 | jiangly | 3814 |
| 3 | jqdai0815 | 3682 |
| 4 | Benq | 3529 |
| 5 | orzdevinwang | 3526 |
| 6 | ksun48 | 3517 |
| 7 | Radewoosh | 3410 |
| 8 | hos.lyric | 3399 |
| 9 | ecnerwala | 3392 |
| 9 | Um_nik | 3392 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 169 |
| 2 | maomao90 | 162 |
| 2 | Um_nik | 162 |
| 4 | atcoder_official | 161 |
| 5 | djm03178 | 158 |
| 6 | -is-this-fft- | 157 |
| 7 | adamant | 155 |
| 8 | awoo | 154 |
| 8 | Dominater069 | 154 |
| 10 | luogu_official | 150 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 22.12.2024 20:42:01 (j3).
Десктопная версия, переключиться на мобильную.
При поддержке
In Chinese: 离散化(ie. map larger values to smaller distinct values)
please explain cordinate compression someone i can't solve a problem relating to this please help me
Let's say that in a problem, you're required to store N (1 <= N <= 10^5) elements and perform some operations on those elements (say put them in a Segment Tree). Normally, if the elements were also in the range (1, 10^5), inserting them into a data structure would be a cinch.
Say, for example, the elements are now in the range (1, 10^12). Now simply inserting elements into a Segment Tree is not possible because you cannot allocate memory for 10^12 integers. This is where coordinate compression comes into play.
Let's read in all of the possible numbers, sort them, and assign each of them a number based off of increasing order. Because N is <= 10^5, the maximum number you assign is going to be 10^5. Thus, by compressing the "coordinates", we maintain the relative order of points in a memory-efficient manner.
I hope this helps!
Hey, thanks for the nice explanation. I have a doubt,
If we have numbers ranging 0,10^9 and i want to update and access their frequency in O(1). Unordered_map,map gave me TLE. Can there be a better than O(lgn) way, using coordinates compression to solve this problem ?
Thanks !
Use unordered_map after choosing random modulo(hash function) to prevent anti-hash tests to make solutions to fail. See this.
Though I got an alternate solution from some blog, but thanks a lot !
You're welcome!
Good problem http://usaco.org/index.php?cpid=207&page=viewproblem2
It's when you take some coordinates, put them all in a hydraulic press. Then they become "compressed".
You're a funny guy
Check this video out.