Search found 147 matches
Given a DAG (directed acyclic graph), a start and end vertex, enumerate all path lengths between them. What is the fastest algorithm? The best I've seen is to use matrix multiplication which is O(n^e(logn)) where e is the exponent for matrix multiplication. Is there a O(n^2 logn) solution? n is numb...
- Thu Aug 17, 2006 11:59 pm
- Forum: Off topic (General chit-chat)
- Topic: Find Robert
- Replies: 4
- Views: 2802
Robert Barrington Leigh, a competitor representing Univeristy of Toronto at World Finals 2006, has gone missing since late Sunday night (Aug 13). Lets hope for the best.
in Chinese postman you can run a min-cost matching on a general graph with vertices the odd degree vertices in the original graph and cost the shortest path between the vertices because you are allowed to count the cost of any edge more than once or twice - here you can only count the cost of an ed...
Dimitar look at my first post in this topic. (observation 1). Also, my algorithm for the IOI practice can be simplified to just a O(1) check on the number of vertices is even, since the graph is connected and so there must be an odd number of odd vertices.
essentially you want to find a ray that goes between your point and end point of another line segment to see if it intersects any other line segments. if no then report no, otherwise report yes.
essentially you backtrack through your matrix. Recall that LCS is defined as: f(i,j)=max(f(i-1,j-1)+1, f(i-1,j), f(i,j-1)) if x ==y[j] =max(f(i-1,j),f(i,j-1)) if x !=y[j] hence you want to find all possible paths from f(M,N) to f(0,0), with an edge between f(i,j) and f(i-a, j-b) if the max value of ...
this is from the IOI 2006 practice right? (or close to it anyways, since the problem asks for all vertices to have odd degree but I think the same algorithm works) http://www.ioi2006.org/practice/highways.pdf Please state your source if its different. I've come up with this algorithm, i am not sure ...
- Thu Sep 29, 2005 4:02 pm
- Forum: Volume 109 (10900-10999)
- Topic: 10902 - Pick-up Sticks
- Replies: 24
- Views: 13016
well, maybe we could either build an AABB tree, or maybe even do some quad-partitions of the plane (each line segment is gonna intersect at most three of the four squares). this should be sub-n^2 algorithm (still n^2 in the worst case).