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

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

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
  • Проголосовать: не нравится

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

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

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

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

But treap should be easier to implement here.

»
14 лет назад, скрыть # |
← 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 :)

»
13 лет назад, скрыть # |
 
Проголосовать: нравится 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.

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

My tiny solution for problem... :)

http://ideone.com/9uklMf

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

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