karan173's blog

spoj OrderSet
By karan173, 12 years ago, In English

i am looking to solve the problemORDERSET. I was thinking about using Binary Index Tree but i dont think we'll be able to create such a large array(x<=10^9). Also i suppose the problem can be solved with a self balancing BST but the standard Java implementations dont provide efficient rank functionality. (it is O(n) in TreeSet) So are there some alternate ways to solve this problem besides implementing my own self balancing BST?

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

Comments Comments (25)
| Write comment?
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Try to write own self balancing BST. I have done it using treap.

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

There is also offline solution. Compress the numbers, then Segment Tree will solve the problem.

But treap should be easier to implement here.

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

Try #1: I tried to solve this problem by building a segment tree with dynamic memory

Result: Time limit exceeded

Try #2: Switched iostream to stdio

Result: Time limit exceeded

Try #3: I compressed the numbers and then built a static segment tree

Result: Time limit exceeded

Try #4: Switched iostream to stdio

Result: Time limit exceeded

Try #5: I coded an AVL Tree class to see if that would make it run in time

Result: After extensive debugging, Time limit exceeded

Try #6: Last thing to try, again switch from iostream to stdio

Result: Accepted

This problem gave me a thousand headaches and, by the way, the AVL Tree class was the hardest thing I ever had to code in my life.

But I'm glad I did it. Additional knowledge is always a good thing :)

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

    btw what's meant by "compressing" the nos.?

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

      If you are given N numbers, compression is assigning numbers from 1 to N to the numbers given in the input. You can do that in the following way...

      1) Read the input and store the numbers in an array.

      2) Sort the array.

      3) Walk the array in order, assigning to each DIFFERENT element an integer. You can do that with a map that says Compressed[n] = x, and another one that says Original[x] = n, if you ever need to know what the original number of compressed x was.

      Compression is a very useful technique. In the case of this problem, it's useful because you can then build a segment tree with 2^19 nodes using the compressed numbers instead of the original ones.

      Other problems where you can use compression are:

      • USACO Contest December — Bronze Problem 3
      • USACO Contest January — Bronze Problem 1
      • Codeforces Problemset — Colorado Potato Beetle
      • Many others
      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        thanks for the gr8 info!

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

        Can you please post links to the other similar questions if possible? Thanks. :)

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

    please can you copy your implementation to AVL tree, I'm looking for a good implementation to AVL tree in C++

    thank you.

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

      This is the AVL Tree class I coded for this problem. It's the first time I coded an AVL Tree, so I doubt it's good, but it worked. Here it is...

      Link here --> http://pastebin.com/iXejKdKs

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

        you'd better send your code to pastebin and give a link to it in your comment

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

          Yeah, I changed it. Sorry for that...

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

        thank you very much

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

        what was the best runtime for your solution in the end ?!

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

          Runtime was 0.65.

          Now the time limit is 0.300 s. I wonder if that's an error... it doesn't seem correct.

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

            yes :D the same for me. It took 0.60 and i just want to be sure maybe it's something like a new compiler or another stuff

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

      Here's another implementation of AVL Tree.

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

    an old but effective trick is to replace "endl" by "'\n'".i did it by segment tree but it wasn't iterative so i think you could(if you didn't) do it faster by using this way.

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

Solved it using Binary Indexed Tree, the coolest data structure in the world. And don't bother for the 10^9 thing. That's just maximum value which just fits in an 32bit int. The catch is, query is at most 200000. So you just need an array of at most size 200000. After that cached the input, updated, deleted etc. Btw, got TLE at first attempt. Then just replaced all long longs with int and got AC. I know it's a bit awkward , but for old systems like in SPOJ(Cluster: Pyramid (Intel Pentium III 733 MHz) it takes more time to deal with long long than with int. Try it.

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

    In fact, It was not BIT that did a great job for you in solving this problem. Instead, coordinates' compression was a vital part... not BIT ; )

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

      Let's just say it was both :D Coordinate compression is frequently used with data structures such as BIT.

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

    Did you do it in Q * logQ * logQ or Q * logQ ?

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

My tiny solution for problem... :)

http://ideone.com/9uklMf

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

as mentioned in the comments (in spoj) try solving this after you're done :D

→ Reply