LUKYDRIV - Editorial

PROBLEM LINK:

Practice
Contest

DIFFICULTY:

Easy

PREREQUISITES:

DP, Basic number theory

PROBLEM:

A number is lucky if after repeated addition of digits, we get 9. Given a sequence of digits, task is to find out how many of its sub-sequences of length between 1 to 4 are lucky numbers.

QUICK EXPLANATION:

A number N is lucky iff N > 0 and N % 9 = 0. So here lucky sub-sequences are those 1-4 digit sub-sequences whose sum is 9, 18, 27 or 36. We can find this either using DP or some combinatorial arguments.

DETAILED EXPLANATION:

Repeated digital sum of a number is also called digital root of the number. It can be shown that digital root of a number N is N % 9. For a proof of this and other interesting facts about digital root, you can read its wikipedia page.

Now those numbers are lucky whose digital root is 9. All these numbers would be multiples of 9. Let’s see a DP solution first. Let dp[i][j][k] denote the number of ways of choosing k digits from the left most i digits of the sequence such that the sum of chosen numbers is j modulo 9. We finally need sum over k from 1 to 4 : dp[L][0][k], though we’d need to remove those cases where the produced number is a zero. How to find the number of those cases? Let there be K 0 digits in sequence. Any 1-4 of these give us a number which is 0 so we can subtract KC1 + KC2 + KC3 + KC4.

What is the recurrence for the DP? For every digit, we’ve two choices - whether to include it or not include it. So we can frame recurrence easily as follows :

dp[i][j][k] = dp[i-1][j][k] + dp[i-1][j'][k-1]     where j' is such that j' + S[i] = j (mod 9)

This method takes around O(length * 10 * 4) and might be a little too slow to clear the time limits.


There is an alternative method as well. Assume that number is 4 digits long. We
could move over all 4 digit numbers, see if sum of their digits is one of 9, 18, 27, 36
or not. If yes, we could find out in how many ways can we choose this 4 digit
number as subsequence from the given sequence. But it is not so easy to find out
this number quickly.

But hope is not lost! Note that order of digits is not
important for finding sum of digits. So we could as well move over all 4 digits
(producing each combination exactly once) and see how many times we can choose
such digits. For an example let’s say that we choose {1, 1, 7, 9} to be our
digit set. Further say our sequence has A1 occurences of 1,
A7 occurences of 7
and A9 occurences of 9. Then number of ways we can choose a sub-sequence where
these 4 digits are chosen is : A1C2 *
A7 * A9

ans = 0

for a from 0 to 9:
for b from a to 9
for c from b to 9:
for d from c to 9:
    sum = a + b + c + d
    if(sum > 0 and sum % 9 == 0)
        fill(used_count, 0)
        used_count[a] ++
        used_count[b] ++
        used_count[c] ++
        used_count[d] ++

        its = 1
        for i in 0 to 9:
            its *= (total[i] choose used_count[i])

        ans += its 

We can similarly write loops for the cases when number of digits is 3, 2, or 1.
Look at tester’s solution for a smart implementation where he hasn’t written
different loops for 3, 2 or 1 digits.

SETTER’S SOLUTION:

To be uploaded soon.

TESTER’S SOLUTION:

Can be found here.

6 Likes

“Let dp[i][j][k] denote the number of ways of choosing k digits from rightmost i digits of the sequence”
I think rightmost should be leftmost as S[i] is the i-th number counted from left.

1 Like

just one question,i had dp solution as well as TLE,what means a little bit slow?that means that dp solution won’t fit in time limits?

2 Likes

I’m more interested in “might be a little too slow”, is there solution that passed TLE with DP approach? I tried a lot with C++, but no success.

3 Likes

I used DP approach almost identical to one described above and got accepted (with luck :)). Note that the dp array may be only 2 dimensional since the first field (i) can be hold in the context (for loop), for more details see my solution.

2 Likes

@monkeybrain: I also used DP with 2D array but getting TLE , it’s not a standard Time Limit for such a problem !
here’s my code ,do you have any suggestion to improve it ?
http://www.codechef.com/viewsolution/1228348

tnx

@demo - I’ve corrected it though even the previous one wasn’t wrong - high-endian or little-endian, it’s more of a matter of personal choice :slight_smile:

Could someone please kindly tell me why my solution gets WA…
http://www.codechef.com/viewsolution/1255406