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
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.
goo.gl_SsAhv Can you please elaborate your approach a bit.