11465 - Count the Polygons

All about problems in Volume 114. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

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! And about the solution:

Let's talk about another problem. Given N integers, how many way can you choose M integers whose sum exceeds S.
Let N = 6 and M = 4 and the set of numbers = { 1, 2, 6, 7, 10, 12 }. And also assume that S = 10.

The first thing is to divide these numbers into two sets arbitrarily. Lets consider like this :: A = {1, 2, 6} and B{7, 10, 12}.
The next thing to do is find all combinations in each set. That is 2^3 numbers in each set. Lets call these new sets AA and BB.
AA = {0, 1, 2, 6, 1+2, 1+6, 2+6, 1+2+6} = {0, 1, 2, 6, 3, 7, 8, 9}. Do the same thing with B to get BB.

Now pick each element in AA and find the other part in BB using binary search. Suppose we picked '2' from AA. Since the sum is 10, we'd be looking for how many numbers are there in BB whose value is at least 9 so that the total sum exceeds 10.
One thing to keep in mind is the number of integers that make up each combination. For example, taking 2 from AA means we have to look for values in BB whose elements are exactly made of 3 integers so that total number of elements taken is 4(1+3 :: 1 from AA and 3 from BB }.

The explanation might be a little esoteric but I hope it's enough to get you started. 