Discussion @ 1181. Cutting a Painted Polygon @ Timus Online Judge

DP for O(n^3)

Posted by [Ural SU] GetTester 6 Nov 2009 14:02

I got AC with O(n^3) solution, based on DP.
I suppose, that testcases are too weak. Anyway, I think, that it's not normal to get AC for O(n^3) solution.
)

Re: DP for O(n^3)

Posted by tiancaihb 7 Nov 2009 04:15

My solution is n3, but it doesn't have to check all posibilities. Some part of array f[][] is never used. Besides, I don't know a better way.

Re: DP for O(n^3)

Posted by ASK 17 Mar 2010 21:32

It is not O(n^3): the expected number of tests for each sub-interval is 2 and thus DP is O(n^2).

Discussion of Problem 1181. Cutting a Painted Polygon