Problem setter: [aditya10_][1]
DIFFICULTY:
Medium
PREREQUISITES:
Dynamic Programming, Bit Masking
EXPLANATION:
We will take a mask of the number of items M. 1 at ith index represent that item of type i is included. Mask at any time represents the type of items which are ordered continuously from the left. We will find the cost of adding every type of item which was not there in the mask ie the bits which were unset.
Cost of adding an item of type X means the number of items to select such that item of type X occurs in succession. The item of type X here is added after the type of items which have already been placed continuously i.e. the bits which were set in the mask.
Dp array stores the cost of each mask.
The above can be represented as:
!
[2]
Now How to find the cost of adding a type of item X?
Let the total number of items be tot which are set in the mask. And the number of items of type x be c. Now the cost will be the number of items which are not of type x in the range
[tot+1,tot+x].
For this we will maintain an array which stores the frequency of each type of item. And a pref array pref[N+1][M+1]. pref[idx][x] represent the number of items of type x upto index idx.
![code2][3]
Author’s Solution: [click here][4]
Tester’s Solution: [click here][5]
[1]: https://www.codechef.com/users/aditya10_
[2]: https://discuss.codechef.com/upfiles/Capture_1xkltz8.PNG
[3]: https://discuss.codechef.com/upfiles/Capture1_TRPZSCD.PNG
[4]: https://ideone.com/25foEK
[5]: https://ideone.com/25foEK