Zzyzx's blog

Codeforces Round #235 (Div. 2) problem D doubt
By Zzyzx, 11 years ago, In English

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.

  • Vote: I like it
  • -18
  • Vote: I do not like it

»
11 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Take a look at my solution. I've used the same idea but encoded counts in binary bitmask.

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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!

    → Reply