Is there some formula?

I used DP for solving this problem, and have AC in 0.015 sec. as many other Timus members. But, there are some members who take AC in 0.001 sec. So, my question is: is there some formula for this problem or this people take so incredible result with very hard optimization?

Re: Is there some formula?

Yes, there is.

Re: Is there some formula?

Please,How to DP?

Re: Is there some formula?

If you know DP formula it's easy convert to simple math formula. It's very instresting problem =)

Re: Is there some formula?

If you submit your solution several times, it may get 0.001 sec in one of submissions

Re: Is there some formula?

Start with sequence of anges 0, 90, 180, 270 (the inner square) and perform -45, +45 steps at every edge from previous stage. Then cut away 180 degree turns. After that number of remaining edges /2 will be the result for current stage. Of course, yhat won't work for big N, but it gives an idea on how to calculate number of 180-degree cut-outs at stage N. Case N=1 is special. Odd and even N should be treated separately. The rest is up to you :)