Search found 430 matches

by misof
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...
by misof
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?
by misof
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!
by misof
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)? :)
by misof
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...
by misof
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...
by misof
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...
by misof
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...
by misof
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...
by misof
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
by misof
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 :P
by misof
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.
by misof
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...
by misof
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?
by misof
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...

Go to advanced search