Search found 430 matches

by misof
Fri Nov 24, 2006 10:48 am
Forum: Algorithms
Topic: Heap Data Structure - implementations
Replies: 4
Views: 2446

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'...
by misof
Thu Nov 23, 2006 4:54 pm
Forum: Algorithms
Topic: Heap Data Structure - implementations
Replies: 4
Views: 2446

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).
by misof
Sat Nov 18, 2006 12:50 am
Forum: Algorithms
Topic: Array moving left
Replies: 6
Views: 2216

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).
by misof
Sat Nov 18, 2006 12:49 am
Forum: Algorithms
Topic: Array moving left
Replies: 6
Views: 2216

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 ;)
by misof
Mon Nov 13, 2006 2:16 pm
Forum: C++
Topic: input a iteger like a string
Replies: 3
Views: 2208

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?
by misof
Thu Oct 19, 2006 7:12 pm
Forum: Algorithms
Topic: Problems using LCA form arhive.
Replies: 8
Views: 3928

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.
by misof
Thu Oct 19, 2006 7:05 pm
Forum: Volume 111 (11100-11199)
Topic: 11123 - Counting Trapizoid
Replies: 16
Views: 5725

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...
by misof
Thu Oct 19, 2006 10:45 am
Forum: Bugs and suggestions
Topic: 656 - Optimal Programs
Replies: 2
Views: 1810

Your program is wrong, you have an overflow. Note the condition that the absolute value of no intermediate result may exceed 30000.
by misof
Wed Oct 18, 2006 11:04 am
Forum: Algorithms
Topic: how to choose the num ???
Replies: 13
Views: 4242

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...
by misof
Tue Oct 17, 2006 5:52 pm
Forum: Algorithms
Topic: how to choose the num ???
Replies: 13
Views: 4242

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...
by misof
Tue Oct 17, 2006 12:40 am
Forum: Volume 111 (11100-11199)
Topic: 11122 - Tri Tri
Replies: 29
Views: 8850

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...
by misof
Sun Oct 15, 2006 1:36 pm
Forum: Other words
Topic: concrete mathematics
Replies: 1
Views: 1936

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...
by misof
Sun Oct 15, 2006 11:07 am
Forum: Volume 111 (11100-11199)
Topic: 11118 - Prisoners, Boxes and Pieces of Paper
Replies: 7
Views: 3221

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...
by misof
Sat Oct 14, 2006 9:58 pm
Forum: Algorithms
Topic: how to choose the num ???
Replies: 13
Views: 4242

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?
by misof
Sat Oct 14, 2006 11:04 am
Forum: Algorithms
Topic: search
Replies: 1
Views: 1286

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 ...

Go to advanced search