LUCKY3 - Editorial

PROBLEM LINKS

Practice
Contest

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 ( http://en.wikipedia.org/wiki/Mask_(computing) ) 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.

1 Like

@witua
@laycurse

Consider this test case:

10

2 44 774 3331 7542 45 132110 74 77792 6

For this. both developer’s as well as testers soltion give answer as 30, where as when I worked out this problem on paper, I could find just 22 subsequences, which are:

  1. 44
  2. 74
  3. 774
  4. 44, 74
  5. 44, 774
  6. 74, 774
  7. 44, 74, 774
  8. 2, 44
  9. 2, 74
  10. 2, 774
  11. 2, 44, 74
  12. 2, 44, 774
  13. 2, 74, 774
  14. 2, 44, 74, 774
  15. 7542, 774
  16. 7542, 44, 774
  17. 7542, 74, 774
  18. 7542, 44, 74, 774
  19. 2, 7542, 774
  20. 2, 7542, 44, 774
  21. 2, 7542, 74, 774
  22. 2, 7542, 44, 74, 774

I couldnt think of any more subsequence, can you please help me in finding out, what am I missing here? I know it would be a pretty basic thing, but currently I am clueless

One hell of an explanation, simply amazing!! Loved the problem and the editorial. I know it’s two years late but still its a gem :smiley: