## Search found 430 matches

Fri Oct 13, 2006 3:56 pm
Forum: Algorithms
Topic: How To Compute Shortest Distance Between Two Lines
Replies: 5
Views: 2521
You probably want the distance of line segments , not the distance of the entire (infinite) lines, right? There is no simple way to do this. The cases to consider are: - if they intersect, answer = 0 - if not: * compute the distance for each pair of endpoints * for each endpoint, find its orthogonal...
Tue Aug 29, 2006 11:54 am
Forum: Off topic (General chit-chat)
Topic: all-girl team
Replies: 6
Views: 3559
Apart from the rule that says "Beat all other teams in your region, and you advance to the World Finals"? No. Why should there be one?
Tue Aug 08, 2006 8:30 pm
Forum: Algorithms
Topic: Matrix Multiplication O(nlgn) problems
Replies: 5
Views: 1916
We live to learn
I didn't know this result before. So far I only read the abstract, but it seems pretty interesting. I will surely read the entire article when I have the time. Thanks for the link!
Mon Aug 07, 2006 10:14 pm
Forum: Algorithms
Topic: Matrix Multiplication O(nlgn) problems
Replies: 5
Views: 1916
And can that be done in O(n log n)?
Mon Jul 31, 2006 10:53 am
Forum: Algorithms
Topic: Point enclosed by segments
Replies: 4
Views: 1794
As I understood the original problem, this won't work. An O(n^2) solution should be reasonable. (Disregarding special cases,) test all pairs of segments for intersection, build a graph where vertices=intersections, edges=parts of segments. This graph is clearly planar. Find the face that contains th...
Sun Jul 30, 2006 11:22 pm
Forum: Other words
Topic: Dynamic Programming.
Replies: 4
Views: 2480
Dynamic programming is, first of all, a method of approach to solving (some) algorithmical problems . Reading articles about it won't be enough to bring you to the "advanced level" you speak about. The key thing for understanding DP is being able to spot the recursive pattern in the nature of the pr...
Wed Jul 26, 2006 10:35 pm
Forum: Algorithms
Topic: longest path
Replies: 7
Views: 2485
Hehe, I got what I asked for :D The clarifications are in place, of course. The intended formulation was "the problem is NP-hard and we don't know whether it is NP-complete ". My second point is just the translation of "we don't know whether it is NP-complete" into words. As of the other point, even...
Wed Jul 26, 2006 4:58 pm
Forum: Algorithms
Topic: longest path
Replies: 7
Views: 2485
Cosmin.ro: NP-what? :) The correct phrase here would be "is known to be NP-hard", meaning: - if we were able to solve this problem in polynomial time, we would be able to solve any problem from NP in polynomial time - it is not even known whether there is a non-deterministic polynomial algorithm for...
Wed Jul 26, 2006 12:49 pm
Forum: Algorithms
Topic: Line up problem ..
Replies: 5
Views: 2024
I think that you can get to worst-case O(N^2) using point-line duality. Transform the problem into "given N different lines, find the largest subset that pass through the same point", and then traverse the whole plane subdivision given by the N lines, and look for a vertex with the largest degree. O...
Wed Jul 26, 2006 12:41 pm
Forum: C++
Topic: Compile Error on using STL set...
Replies: 2
Views: 1641
I changed your comparison function to a more correct one:

Code: Select all

``````class comp {
public:
bool operator () (const Test &a, const Test &b) const
{
if (a.x < b.x || (a.x == b.x && a.y < b.y)) return true;
return false;
}
};
``````
now it compiles under all versions of g++ I found
Wed Jul 26, 2006 12:29 pm
Forum: Off topic (General chit-chat)
Topic: Will the thread "I win !!" eventually end?
Replies: 2
Views: 22549
Nuclear apocalypse
Fri Jul 21, 2006 3:34 pm
Forum: Other words
Topic: 2007 world finals IN JAPAN?
Replies: 20
Views: 10490
We (from Slovakia) are not travelling via the States, so it's possible to get to the IOI without obtaining US transit visa :) But I agree that visa may often cause problems, I do remember cases when contestants weren't able to participate for this reason, and it's always a sad thing when this happens.
Sun Jul 16, 2006 1:17 pm
Forum: Algorithms
Topic: how to find Derangement of a multiset
Replies: 2
Views: 1415
Just to clarify, what do you understand under "derangement"? For permutations, derangement is a permutation without fixed points. The best definition I could come up with for multisets: Suppose M is a multiset. Let sorted(M) be the vector containing all elements of M in sorted order. For example, if...
Sun Jul 16, 2006 1:09 pm
Forum: Off topic (General chit-chat)
Topic: I win !!
Replies: 361
Views: 122625
If it is really never ending, how can you win?
Sun Jul 02, 2006 9:52 pm
Forum: Algorithms
Topic: array sorted or not (bentley)
Replies: 2
Views: 1031
To 1), the answer is no. You can view the running of an algorithm as a game: the algorithm poses questions and tries to learn as much as necessary to decide whether the array is sorted. Imagine an evil opponent that wants to convince your algorithm that the array is sorted when it is not. If you don...