Chasty's blog

What is coordinate compression?
By Chasty, history, 9 years ago, In English

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?

  • Vote: I like it
  • +1
  • Vote: I do not like it

Comments Comments (11)
| Write comment?
»
6 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

In Chinese: 离散化(ie. map larger values to smaller distinct values)

→ Reply
»
5 years ago, # |
  Vote: I like it +7 Vote: I do not like it

please explain cordinate compression someone i can't solve a problem relating to this please help me

→ Reply
»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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!

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 !

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Use unordered_map after choosing random modulo(hash function) to prevent anti-hash tests to make solutions to fail. See this.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +4 Vote: I do not like it

        Though I got an alternate solution from some blog, but thanks a lot !

        → Reply
»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Good problem http://usaco.org/index.php?cpid=207&page=viewproblem2

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It's when you take some coordinates, put them all in a hydraulic press. Then they become "compressed".

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Check this video out.

→ Reply