LashaBukhnikashvili's blog

LIS2 ,2D Trees
By LashaBukhnikashvili, 10 years ago, In English

I am trying to solve this problem,I need your helps ;)

Is any idea to solve it,without 2d Trees? or what kind of 2d Trees should I use,that dont use O(n*m) memory,and update,query as much fast as it possible(like a logNlogM)

P.S I was reading material about fenwik tree,but it needs O(n*m) memory(sorry for my poor english )

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it -11 Vote: I do not like it

think it up yourself

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

    Probably he alredy tried if he asks for help?

    → Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Compress the pairs into numbers 1..X (UTFG compressing coordinates), then it's a classic LIS in .

Is wrong. At least for this operator (which, in fact, is not actually a comparison operator, so it technically isn't an increasing sequence because the term "increasing" remains undefined; it's actually a pair of LIS with common indices in 2 sequences). Well, an obvious extension to compressed 2D segment trees works, and I found an answer on Stack Overflow about it.

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

    Thanksss, I GOT IT :)

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

    No, you can't compare 2 pairs (x1, y1) and (x2, y2) if x1 < x2 and y1 > y2. As far as I know, there is no way to solve this without 2D tree. Using set from C++ can simplify the implementation for this problem.

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

      Yeah, I found out already. The problem is that I didn't read beyond "pair (a,b) is less than (c,d) if" because there is just one comparison operator on pairs.

      → Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it 
    I think you could maybe sort all pairs by their x coordinates. and then you could build a segment tree by their y coordinates

    . Oh I am wrong

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

    can you explain what UTFG compressing coordinates is? I googled it but couldnt find anything.

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

Need help again,if you can please tell my idea to solve this problem without 2d trees :\

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

    A solution without trees was explained by Xellos up here.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it -7 Vote: I do not like it

      And is wrong. More specifically, is wrong for the inequalities from the problem statement.

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

        The explanation you linked from stack overflow, on the other hand, doesn't need an implementation of 2d trees and is correct.

        My accepted code on SPOJ has 55 lines.

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

    I think flashmt is right. I think you can use range tree which is a 2d tree :D

    → Reply
»
10 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Notice that when you call update for fenwick you just update O((logN)d) nodes. If any node is not updated then it's value is zero. So you dont need O(NM) memory at all. O(M(logN)d) is enough.

PS: d means dimension

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

    How would you remember the nodes to avoid O(N2) memory? The most obvious way to store Fenwick trees this way is using a map instead of a vector, but that adds a nasty factor of to the complexity.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      Hash tables would be more usefull. So we can get rid of that O(logN)

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

        While introducing a large constant. So much win...

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

          We are not dealing with that huge constant. It is much more better then red-black trees in current realistic world limits too.

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

            So, you're saying that we use a hashmap and still aren't dealing with the huge constant that it involves because... magic?

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

              Im just saying that constant is not huge but obviously exists.

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

                Here, it would appear that inserts have only about twice better performance for hashmap than map in C++, while fetches are much faster. And we still need to do a lot of inserts.

                If you want to convince me, you'd need to provide a better argument than that you're saying, because I'm saying hashmap is a bad idea here and if anything then quicksort on subFenwick trees (1D) with many accessed elements and bubblesort on those with few (~5?) is faster.

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

                  Well, i dont care about convincing you. From my point of view twice faster hash table is tolerable.

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  10 years ago, # ^ |
                  ← Rev. 2   Vote: I like it 0 Vote: I do not like it

                  Did you get AC on that problem ? (if not and you're still satisfied, then it isn't a good attitude for competitive programming :D)

                  It's SPOJ and SPOJ is slow, if map is a factor of 20 and hashmap is a factor of 10 then it's just a question of getting TLE with 6 or 3 seconds...

                  Also: how hash always works.

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

      We can avoid this by preprocessing. Let's simulate all the queries to find out for each value of x, which values of y we will need to access.

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

        I realize that we can find these values, but there is still of them in total and we still need to sort them or map them or something. How else would you determine that query q1 and q2 both access the same vertex (x, y)?

        Quicksorting (map and hashmap are both slow IRL) all y for all x would probably be enough to pass this on any fast online judge (I'd comfortably go code it if it was CF), but SPOJ isn't fast in any way, that's why I'm doubting stuff so much.

        → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
          ← Rev. 7   Vote: I like it 0 Vote: I do not like it

          That's exactly what I did for this problem on SPOJ. Since we break N(logN)2 values into N different lists of x, the sorting part runs quite fast. After we get all y sorted for all x, when processing a query (x, y), we only need to find the actual index of y once for each of logN x values (by binary search) so it would cost O(N(logN)2) in total.

          → Reply