Обсуждение @ 1776. Праздничный фейерверк @ Timus Online Judge

Online Judge

Задачи

Авторы

Соревнования

Please explain algo faster than N^4

Послано Vasily Slesarev 21 май 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

Послано AterLux 23 май 2011 12:16

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

Re: Please explain algo faster than N^4

Послано Vasily Slesarev 23 май 2011 20:16

Thank you)

Re: Please explain algo faster than N^4

Послано Jonathan Paulson 8 сен 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)