### Zzyzx's blog

By Zzyzx, 10 years ago,

Here is the link to the problem: http://mirror.codeforces.com/contest/401/problem/D

So I was trying the same DP approach as most people did, but with a slight change in the state.

What most people used as their DP state: < remainder, mask_of_18_bits >

where 'mask_of_18_bits' is used to denote whether i-th digit in number 'n' is used or not.

What I used as DP state: < remainder, zeroes_left, mask_of_18_digits >

Please note that here the mask is entirely different.

where 'zeroes_left' = number of 0s left in the number 'n' to be used.

and 'mask_of_18_digits' is defined in this way 'aabbccddeeffgghhii'

aa = number of 9s left in 'n' to be used,

bb = number of 8s left in 'n' to be used,

....

....

ii = number of 1s left in 'n' to be used

Here is the link to my submission: http://mirror.codeforces.com/contest/401/submission/5990314

but with my approach, I used std::map and that gives TLE at test case 80.

Can someone please suggest a workaround using the same idea? I want to be able to define a state in terms of counts of the digits 0-9.

• -18

 » 10 years ago, # |   +3 Take a look at my solution. I've used the same idea but encoded counts in binary bitmask.
•  » » 10 years ago, # ^ | ← Rev. 2 →   0 It's amazing how you encoded all that into just one long long variable. Can you please brief me a bit about your encoding and decoding process?EDIT: I have understood your method. Cool trick! Thanks for sharing!