Discussion @ 1073. Square Country @ Timus Online Judge

If you use DP

Posted by PSV 24 Oct 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

Re: If you use DP

Posted by elmariachi1414 (TNU) 25 Nov 2006 18:24

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

Re: If you use DP

Posted by AlainDelon 2 Dec 2007 12:20

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

Thanks,

Re: If you use DP

Posted by Alias (Alexander Prudaev) 2 Dec 2007 18:13

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

Discussion of Problem 1073. Square Country