11465 - Count the Polygons

Moderator: Board moderators

andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

11465 - Count the Polygons

I think this problem is solvable by DP. During the contest I thought about this state: dp[j] = Numbers of ways I can select some subset of the first i edges such that their sum is >= j, but it is extremely big to memoize..., would need about 4 gigabytes of memory .

Any advice on how to solve this?
Thanks.
Last edited by andmej on Sat Jul 12, 2008 11:52 pm, edited 1 time in total.
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

Robert Gerbicz
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:

Re: 11465 - Count the polygons

There is a method to solve the problem in O(u*2^u) time and O(2^u) memory where u=N/2.
I've done this on the contest. This algorithm took 1.32 sec.

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Re: 11465 - Count the polygons

Robert Gerbicz wrote:There is a method to solve the problem in O(u*2^u) time and O(2^u) memory where u=N/2.
I've done this on the contest. This algorithm took 1.32 sec.
This was also my solution. However, the alternate solution was written using backtracking with a lot of pruning and time taken for the latter was lower.

andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

Re: 11465 - Count the polygons

Can you describe the algorithm in more detail? I still don't know how to solve it. Thanks.

By the way, nice problem Sohel.
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Re: 11465 - Count the polygons

andmej wrote:By the way, nice problem Sohel.
Thanks!