11691 - Allergy Test

[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.

[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.