ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1531. Zones on a Plane

Is there some formula?
Posted by Mace(Lviv Polytechniс NU) 9 Jun 2007 14:09
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?
Posted by Romko [Lviv NU] 9 Jun 2007 19:18
Yes, there is.
Re: Is there some formula?
Posted by Cheryl Xie 7 Jan 2008 20:23
  Please,How to DP?
Re: Is there some formula?
Posted by Sergey Tihon 27 Jul 2008 18:43
If you know DP formula it's easy convert to simple math formula. It's very instresting problem =)
Re: Is there some formula?
Posted by Denis Koshman 1 Aug 2008 18:28
If you submit your solution several times, it may get 0.001 sec in one of submissions
Re: Is there some formula?
Posted by Denis Koshman 1 Aug 2008 19:44
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 :)