## Search found 147 matches

Sat Oct 13, 2007 5:14 pm
Forum: Algorithms
Topic: DAG path enumeration
Replies: 2
Views: 2112
DFS won't even solve the problem in polynomial time (BFS will, however).
Sat Oct 13, 2007 8:05 am
Forum: Algorithms
Topic: DAG path enumeration
Replies: 2
Views: 2112

### DAG path enumeration

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...
Tue Aug 22, 2006 10:39 pm
Forum: Off topic (General chit-chat)
Topic: Find Robert
Replies: 4
Views: 2801
Robert's body has being found today. Rest in peace.
Thu Aug 17, 2006 11:59 pm
Forum: Off topic (General chit-chat)
Topic: Find Robert
Replies: 4
Views: 2801

### Find Robert

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.
http://findrobert.com
Sun Aug 06, 2006 5:32 pm
Forum: Algorithms
Topic: minimum edge for deletion
Replies: 21
Views: 6440
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...
Fri Aug 04, 2006 8:42 pm
Forum: Algorithms
Topic: minimum edge for deletion
Replies: 21
Views: 6440
can anyone tell me if my algorithm above is wrong by showing me a flaw or come up with a counter example? an O(1) algorithm just seemed not right.
Fri Aug 04, 2006 8:19 pm
Forum: Algorithms
Topic: minimum edge for deletion
Replies: 21
Views: 6440
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.
Mon Jul 31, 2006 7:29 am
Forum: Algorithms
Topic: O(log n) Fibonacci
Replies: 4
Views: 2684
the n-th fibonnacci number can be find by raising the golden ratio to the power of n and round it.
Mon Jul 31, 2006 7:24 am
Forum: Algorithms
Topic: Point enclosed by segments
Replies: 4
Views: 1766
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.
Mon Jul 31, 2006 7:20 am
Forum: Algorithms
Topic: LCS again...help
Replies: 4
Views: 1973
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 ...
Mon Jul 31, 2006 7:12 am
Forum: Algorithms
Topic: minimum edge for deletion
Replies: 21
Views: 6440
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 ...
Mon Jul 31, 2006 7:03 am
Forum: Algorithms
Topic: Combinations
Replies: 7
Views: 2425
Mon Jul 31, 2006 7:01 am
Forum: Algorithms
Topic: Bipartite Graph Matching
Replies: 14
Views: 4508
I believe you either apply max-flow with BFS or hungarian algorithm or hopcroft-karp. the last is fastest. you can look up hungarian algorithm on google/wikipedia
Thu Sep 29, 2005 4:02 pm
Forum: Volume 109 (10900-10999)
Topic: 10902 - Pick-up Sticks
Replies: 24
Views: 12955
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).
Mon Mar 28, 2005 8:44 pm
Forum: Algorithms
Topic: USACO help
Replies: 7
Views: 3896
the 1s test case limit becomes a bottle neck for some much harder optimization problems, such as cryptcowgraph, which is just a pain.