## Search found 95 matches

Sun Dec 31, 2006 6:27 am
Forum: Algorithms
Topic: Classic matrix problem
Replies: 5
Views: 2826
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 ...
Sat Oct 21, 2006 5:58 am
Forum: Algorithms
Topic: Problems using LCA form arhive.
Replies: 8
Views: 3910
You should try what misof said, it's pretty intuitive and it should be at most 30 lines of code.
Sat Sep 09, 2006 2:08 am
Forum: Algorithms
Topic: Maximum sum of n vectors -> in O(n lg n)
Replies: 15
Views: 4353
http://www.hsin.hr/2003/national/first_ ... oblems.pdf

last problem.

You can find the official solution on the same page.
Thu Sep 07, 2006 6:37 pm
Forum: Algorithms
Topic: Maximum sum of n vectors -> in O(n lg n)
Replies: 15
Views: 4353
It's from the google coding jam practice rooms.
Fri Aug 18, 2006 7:41 pm
Forum: Algorithms
Topic: algorithm to determine that polygon is star-shaped
Replies: 7
Views: 2626
Fri Aug 18, 2006 2:57 pm
Forum: Algorithms
Topic: algorithm to determine that polygon is star-shaped
Replies: 7
Views: 2626
halfplane intersection doable with duality in O(n log n) or by a naive algorithm in O(n^2).
Mon Aug 07, 2006 3:07 pm
Forum: Algorithms
Topic: Matrix Multiplication O(nlgn) problems
Replies: 5
Views: 1916
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.
Mon Jul 31, 2006 7:49 pm
Forum: Algorithms
Topic: O(log n) Fibonacci
Replies: 4
Views: 2727
bugz you need infinite precision real numbers foe that ...
Mon Jul 31, 2006 2:31 am
Forum: Algorithms
Topic: Line up problem ..
Replies: 5
Views: 2024
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.
Wed Jul 26, 2006 4:16 pm
Forum: Algorithms
Topic: longest path
Replies: 7
Views: 2485
If the graph is acyclic then you can do it by topological sort. If it is not then the problem is NP.
Thu Jun 01, 2006 1:27 am
Forum: Algorithms
Topic: Shortest path
Replies: 10
Views: 3672
I wonder if this sol runs in time on sgu: http://acm.sgu.ru/problem.php?contest=0&problem=145
Thu Jun 01, 2006 12:34 am
Forum: Algorithms
Topic: Shortest path
Replies: 10
Views: 3672
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.
Wed May 31, 2006 12:26 pm
Forum: Algorithms
Topic: Shortest path
Replies: 10
Views: 3672
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
Tue May 30, 2006 12:31 pm
Forum: Algorithms
Topic: Help on testing point inside a polygon
Replies: 5
Views: 1801
Mon May 29, 2006 3:11 pm
Forum: Algorithms
Topic: constructing permutations with limitations
Replies: 3
Views: 1243
Search for Catalan Numbers.