sourabh912's blog

By sourabh912, 12 years ago, In English

Hi All,

I am trying this problem. I think it can be solved using Dynamic Programming with bitmasking. Please explain how to approach this problem. I have been able to come up with the following solution but not sure if I am thinking in the right direction.

1) With bitmasking I will look at all the possible combinations of pizzas(from i=1 to i=1<<n).

2) Solution for say i=10010011(written in binary) will be min(solution for (00010011),solution for (10000011),solution for (10010001),solution for (10010010)). When finding solution of 10010011 from 00010011, I will check if the discount are available from the pizzas that are set to 1 in 00010011 and will avail maximum discount possible. For all this I am using 1-D array.

Thanks

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

there is 3^15 states. a[i] = 0, if pizza is not bought. a[i] = 1, if pizza i is bought and it's coupon was not used, a[i] = 2 if pizza i is bought and it's coupon was used. About 14 millions of states looks too big, but i think it is author's solution because TL is 5 seconds. use bitmasks for fast checks for coupons.