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?
# | 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 |
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?
Name |
---|
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.