Discussion @ 1776. Anniversary Firework @ Timus Online Judge

Please explain algo faster than N^4

Posted by Vasily Slesarev 21 May 2011 15:51

I know dp algorithm, but it is too slow - O(N^4).
Please explain faster algorithm.

Re: Please explain algo faster than N^4

Posted by AterLux 23 May 2011 12:16

Here algorithm O(1): use precalculated array ;)

Re: Please explain algo faster than N^4

Posted by Vasily Slesarev 23 May 2011 20:16

Thank you)

Re: Please explain algo faster than N^4

Posted by Jonathan Paulson 8 Sep 2011 11:04

It is possible to use a different DP state and calculate each of N^2 cells in O(N) time (N^3 DP algorithm)

Discussion of Problem 1776. Anniversary Firework