OJ Board

DFS won't even solve the problem in polynomial time (BFS will, however).

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 ...

Robert's body has being found today. Rest in peace.

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

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 ...

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.

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.

the n-th fibonnacci number can be find by raising the golden ratio to the power of n and round it.

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 ...

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 ...

google SEPA

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

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).

the 1s test case limit becomes a bottle neck for some much harder optimization problems, such as cryptcowgraph, which is just a pain.