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?
Try to write own self balancing BST. I have done it using treap.
There is also offline solution. Compress the numbers, then Segment Tree will solve the problem.
But treap should be easier to implement here.
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 :)
btw what's meant by "compressing" the nos.?
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:
thanks for the gr8 info!
Can you please post links to the other similar questions if possible? Thanks. :)
please can you copy your implementation to AVL tree, I'm looking for a good implementation to AVL tree in C++
thank you.
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
you'd better send your code to pastebin and give a link to it in your comment
Yeah, I changed it. Sorry for that...
thank you very much
what was the best runtime for your solution in the end ?!
Runtime was 0.65.
Now the time limit is 0.300 s. I wonder if that's an error... it doesn't seem correct.
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
Here's another implementation of AVL Tree.
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.
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.
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 ; )
Let's just say it was both :D Coordinate compression is frequently used with data structures such as BIT.
in my opinion, online solutions are my favourites.
Did you do it in Q * logQ * logQ or Q * logQ ?
My tiny solution for problem... :)
http://ideone.com/9uklMf
Pro Level (:
as mentioned in the comments (in spoj) try solving this after you're done :D