Обсуждение @ 1073. Квадратная страна @ Timus Online Judge

PSV If you use DP [3] // Задача 1073. Квадратная страна 24 окт 2006 05:32

Firstly it's comfortable to use recursive scheme of DP.
Secondly : I've STAK_OVERFLOW when tried to take DP form 1 to sqrt(n), but AC when sqrt(n) downto 1. I don't know what's the differnce but result depend of it

elmariachi1414 (TNU) Re: If you use DP [2] // Задача 1073. Квадратная страна 25 ноя 2006 18:24

I think, you don't need DP in this problem. It can be solved with simple O(n^1.5) algorithm.

AlainDelon Re: If you use DP [1] // Задача 1073. Квадратная страна 2 дек 2007 12:20

would you please further explain the O(n^1.5) and non-DP approach?

Thanks,

Alias (Alexander Prudaev) Re: If you use DP // Задача 1073. Квадратная страна 2 дек 2007 18:13

i don't know why it is not dp, but i think he was mentioned BFS

Обсуждение задачи 1073. Квадратная страна