Search found 147 matches

by bugzpodder
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).
by bugzpodder
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...
by bugzpodder
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.
by bugzpodder
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
by bugzpodder
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...
by bugzpodder
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.
by bugzpodder
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.
by bugzpodder
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.
by bugzpodder
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.
by bugzpodder
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 ...
by bugzpodder
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 ...
by bugzpodder
Mon Jul 31, 2006 7:03 am
Forum: Algorithms
Topic: Combinations
Replies: 7
Views: 2425

google SEPA
by bugzpodder
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
by bugzpodder
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).
by bugzpodder
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.

Go to advanced search