PROBLEM LINKS
DIFFICULTY
MEDIUM
EXPLANATION
First of all, notice that there are exactly 1022 lucky number of length between 1 and 9. We can solve problem for each lucky number independently, then sum up all results and get total result.
Now we need to solve problem for some lucky number L (L[i] - i-th digit if number L, starting from right). If there is some number W[i] in input array W that has some digit on some postion which is greater than corresponding digit in L (i. e. there exits some j, that W[i][j] > L[j]), then we can delete W[i] from W (because if we pick that number to subsequence then we’ll never get lucky number L).
Now we should think about dynamic programming approach to solve problem for current lucky number L. You can read about this method here: http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg
Lets start think about what information we need to handle in DP state. Here we need 2-dimensional state space. Of course, we need to review all numbers of W, so first dimension of DP sate must be [pos], pos = [0; n) (0-based numberation of array W, n - size of W). State [pos] means that we already have reviewed all numbers up to position pos in array W and have picked some to our set. But what set? We don’t know that. We need some more information to know whenever we will achieve current lucky number in current set (using lucky sum operation). If we already have some set of numbers (with indexes up to pos) and some digits of lucky sum of all numbers in that set are already lucky, we need to now that. To achieve that we need to handle bitmask ( Mask (computing) - Wikipedia ) of digits that are already the same like in current lucky L, i. e. j-th bit of bitmask must be turned on if j-th digit of lucky sum of current selected set is equal to L[j] (it can not be greater than L[j], because of second paragraph). So, now we have new state of DP, now it is [pos][mask].
Now we should think about transitions of DP. If we are on state [pos][mask] we can do two things. First - do not choose W[pos] to current set. Then mask, of course, will not changes (because we do not change out current set) and we go to the sate [pos+1][mask]. If we choose W[pos], then we go to the state [pos+1][new_mask]. What is new_mask? This is new_mask created by turning on some bit of musk, which are corresponding to the positions of digits of W[pos] that are equal to L (i. e. if for some j W[pos][j] = L[j] and j-th bit is not turned on in mask, then new_mask should have j-th bit turned on. All bits that were turned on in mask must be also turned on in new_mask).
So, considering 2D DP approach we can handle all possible states which will include all subsequences. Please, read setters solution for further understanding of DP approach.
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.
