11691 - Allergy Test

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

Moderator: Board moderators

Post Reply
New poster
Posts: 7
Joined: Thu Jul 02, 2009 6:37 pm

11691 - Allergy Test

Post by liauys »

Hi everyone. Please help me. I tried to used a dp recurrence with complexity 7 * n * 2^n to solve this problem, but it is obviously too slow for n=20. Any hints on this? Really look forward for some enlightenments!! Thanks. :)
New poster
Posts: 1
Joined: Wed Jul 25, 2012 8:22 pm

Re: 11691 - Allergy Test

Post by RodrigoBurgos »

Hi liauys I see this post to try to find some help, because a get the same idea than you, after think some time, I find the answer to solve this problem, look, your dinamic is with a bit mask ( 2^n * maxSizeDaysOfTheTest ), well if you don't save it in a bit mask, you only save how many Allergy Test exist of size 1, size 2, size 3, size 4... size 7, your states in your dinamic programming will be less than a bit mask.
Post Reply

Return to “Volume 116 (11600-11699)”