## Search found 430 matches

Fri Nov 24, 2006 10:48 am
Forum: Algorithms
Topic: Heap Data Structure - implementations
Replies: 4
Views: 2470
STL vector is a dynamic array, i.e. its size can increase when needed, the cost is amortized constant time per insert. If you have large objects, you can always store pointers to them in the priority_queue -- and these are the only pointers you need. My general opinion on these issues is that there'...
Thu Nov 23, 2006 4:54 pm
Forum: Algorithms
Topic: Heap Data Structure - implementations
Replies: 4
Views: 2470
Why exactly would you need a pointer-based implementation? Arrays are faster, and usually require less memory.

In contests, I usually use STL's priority_queue (built on top of a vector).
Sat Nov 18, 2006 12:50 am
Forum: Algorithms
Topic: Array moving left
Replies: 6
Views: 2243
niklaus: Use a segment tree (aka interval tree) to store the number of elements that are still present in the corresponding array segment. This way you can find the k-th element in O(log N).
Sat Nov 18, 2006 12:49 am
Forum: Algorithms
Topic: Array moving left
Replies: 6
Views: 2243
ayon: your erase is (obviously) linear in the vector's size.
Try it with a vector that has 10 million elements, 100 times in a row
Mon Nov 13, 2006 2:16 pm
Forum: C++
Topic: input a iteger like a string
Replies: 3
Views: 2244
What do you mean by saying "can't use scanf"? What you need is easily done using scanf("%s"). Is this somehow forbidden and you need another possibility?
Thu Oct 19, 2006 7:12 pm
Forum: Algorithms
Topic: Problems using LCA form arhive.
Replies: 8
Views: 3960
For each vertex V and each X, compute and store the vertex (2^X) steps above the vertex V.

This can be done in O(N log N).

Think how to do it, and then how to use this information to find the LCA for a pair of vertices in O(log N) time.
Thu Oct 19, 2006 7:05 pm
Forum: Volume 111 (11100-11199)
Topic: 11123 - Counting Trapizoid
Replies: 16
Views: 5781
the qsort() function from <stdlib.h> is C, not C++ the C++ way is using sort() from <algorithm> To use any of them, you just need a custom comparison function. For C: // warning, not tested int cmp(const void *aa, const void *bb) { struct myStruct *a = (struct myStruct *)aa; struct myStruct *b = (st...
Thu Oct 19, 2006 10:45 am
Forum: Bugs and suggestions
Topic: 656 - Optimal Programs
Replies: 2
Views: 1824
Your program is wrong, you have an overflow. Note the condition that the absolute value of no intermediate result may exceed 30000.
Wed Oct 18, 2006 11:04 am
Forum: Algorithms
Topic: how to choose the num ???
Replies: 13
Views: 4288
But how what can I do if less than L/2? Divide&conquer? I don't know how to do. In this case you should RTFP (Read The Fine Problem statement) and notice that in the discussed problem you are guaranteed that the L/2 bound will hold. In the general case finding the most frequent element cannot be do...
Tue Oct 17, 2006 5:52 pm
Forum: Algorithms
Topic: how to choose the num ???
Replies: 13
Views: 4288
hi misof :) I don't know the tricky solution which you talk about, can you tell me more ? And you say there is the standard solution: load all numbers into memory, and find the median. can you say clearly about this, I am intertesting about what you say. Oh, by the way :Time limit: 5 Seconds Memory...
Tue Oct 17, 2006 12:40 am
Forum: Volume 111 (11100-11199)
Topic: 11122 - Tri Tri
Replies: 29
Views: 8944
The O(n) algorithm to find intersection of 2 convex polygons is related to the idea of rotating calipers. G.T. Toussaint. A simple linear algorithm for intersecting convex polygons. The Visual Computer. 1: 118-123. 1985. Rotating? :D Just sweeping left to right is enough. Imagine a vertical line th...
Sun Oct 15, 2006 1:36 pm
Forum: Other words
Topic: concrete mathematics
Replies: 1
Views: 1945
Free: No. If you ask the original question without the word free, the answer would be yes, but I'm not going to point you to any sources. If you decide you want to go this way and look hard enough, it should be possible to find a copy. However, if you can afford it, the book is definitely worth owni...
Sun Oct 15, 2006 11:07 am
Forum: Volume 111 (11100-11199)
Topic: 11118 - Prisoners, Boxes and Pieces of Paper
Replies: 7
Views: 3249
The puzzle is indeed fascinating, the correct answer is far from what one would expect. For those who are not getting the trick, the problem statement contains the following important sequence: "The prisoner opens n/2 boxes of his choice, one by one ." (emphasis mine) Abednego, thanks for showing us...
Sat Oct 14, 2006 9:58 pm
Forum: Algorithms
Topic: how to choose the num ???
Replies: 13
Views: 4288
There is a tricky solution that only needs O(1) memory and O(N) time.

And there is the standard solution: load all numbers into memory, and find the median. Is there a memory limit such that this second solution won't work?
Sat Oct 14, 2006 11:04 am
Forum: Algorithms
Topic: search
Replies: 1
Views: 1300
First, you want an O(log n) algorithm, not an o(log n) one, those two notations mean different things. Second, consider an array with N-1 zeroes ('0') and a single one ('1'). The one can be on any position in the array, still it will satisfy your conditions. On the other hand, the best algorithm to ...