|
|
back to boardHow alogorithms with n^3/2 may be faster? Probably with lower constants in the compexity calculation. ..but I doubt there are many O(n^3/2) solutions better then the O(nlogn) can anybody give me link about Interval Tree? I think that to solve we should have dynamic container
with operations
delete- O(lgn)
take_k_th - O(lgn)
try write the program (5 rows) in these terms.
After this find anywhere such data type
for example on base of red-black trees.
If you will read interval trees it will take long time
because all typical tasks in this theory far away of 1521/
Edited by author 26.02.2007 23:14 Now I has made realization of this plan
according with Cormen's augmented red-black
tree sytucture for which an additional field : size belongs to each vertex of balanced tree.
But have only 0.821 AC. Interval tree automatically
balanced but how make it augmented with such field ?
In all cases I very glad because this balanced structure
rather helpful.
For example interesting problem 1424 needs another augmented red-black tree (also as in Cormen) when in grredy algotithm we check next interval may or may not to
include it in optimal set
of intervals formed to this moment.
Edited by author 16.09.2007 18:54
Edited by author 16.09.2007 18:55 Binary Search Tree is faster then red - black trees in this case. I solved it using BST in 0.281 sec. At first I constructed balanced BST with n numbers and then there is a simple algorithm to delete and find n - th element in the tree
Edited by author 18.09.2007 18:49 Yes. Order 1,2,3,...N predescribed and we can use random tree. But this situation rather seldom and very often
we have dynamic data base. |
|
|
