OJ Board

SRX you're talking about a different problem which asks to find the largest rectangle that doesn't contain any cell with it's value 0. For the maximal sum problem the best algorithm I know about is very complicated. It is better than the O(n^3) but is slower than O(n^3 / log n) so it doesn't really ...

You should try what misof said, it's pretty intuitive and it should be at most 30 lines of code.

http://www.hsin.hr/2003/national/first_ ... oblems.pdf

last problem.

You can find the official solution on the same page.

It's from the google coding jam practice rooms.

try google ...

halfplane intersection doable with duality in O(n log n) or by a naive algorithm in O(n^2).

I think he was referring to the problem of optimally using parenthesis so that evaluating a product of an array of matrices would finish in the minimal amount of time.

bugz you need infinite precision real numbers foe that ...

You can hash the n^2 intersection points in the dual plane, and get a easier O(n^2) solution but it's O(n^2) memory.

If the graph is acyclic then you can do it by topological sort. If it is not then the problem is NP.

I wonder if this sol runs in time on sgu: http://acm.sgu.ru/problem.php?contest=0&problem=145

Can you? I alwayes thought it is a hard problem, I never looked into it really hard. Could you give some detailes to the Dijkstra sol? I would be very interessted.

It's pretty complex, you could search for k shortest path on google or look over this paper: http://www.ics.uci.edu/~eppstein/pubs/p-kpath.html

http://www.exaflop.org/docs/cgafaq/cga2.html
(no special cases)

Search for Catalan Numbers.