 # LUCKY3 - Editorial

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).

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

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 