Блог пользователя karan173

spoj OrderSet
Автор karan173, 12 лет назад, По-английски

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?

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

But treap should be easier to implement here.

→ Ответить
»
12 лет назад, # |
← Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

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 :)

→ Ответить
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      12 лет назад, # ^ |
      ← Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

      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
      → Ответить
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    thank you.

    → Ответить
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить
»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

My tiny solution for problem... :)

http://ideone.com/9uklMf

→ Ответить
»
10 лет назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить