Shubham_1007's blog

How Do I solve problem ADADIG on spoj?
By Shubham_1007, history, 7 years ago, In English

Problem :ADADIG I am trying to solve this , my Approach is: For a given N : 1)If it is prime —> if single digit return 1 else return 0

2)else factorize N and find all combinations of its factor and add 1s to make the digital sum equal to be N and find all permutations of it and add them all and return this. for step 2 , I am unable to figure out How do I do that efficiently?

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

»
7 years ago, # |
  Vote: I like it +6 Vote: I do not like it

I really really enjoyed the problem! :)

OK, the solution I did is essentially the same you described.

  • Factorize N. If it has a prime factors  > 9, then there's no solution. Otherwise, it will be a number of the form 2a * 3b * 5c * 7d. Any number with digital product N will have c digits 5 and d digits 7, but the other digits are combinations of primes 2 and 3, so they're a bit trickier.
  • 4 = 22, 6 = 2 * 3, 8 = 23 and 9 = 32, but since there can't that many digits, we can just try all combinations for numbers of digits 2, 3, 4, 6, 8 and 9. There can't be more than 18 digits 2 because 219 > 3 * 105. Similarly, there can't be more than 11 digits 3, etc..
  • For every combination of digits, first check that they use the exactly the number of 2's and 3's we have. If they do, add the digits one by one. That is, first all digits 2, then all digits 3, etc.. To add k digits of some number to an already existing number of d digits, we have ways to do so. After adding all digits, we will have a number with sum s, so we have to fill it with n - s digits 1. Again, we use combinatorics, if we have d digits already and o ones, we have to distribute the ones.
  • The binomial coefficients must be precalculated in order to avoid getting TLE. We do that with the triangle form, only going up to 20 in the second column (we don't need more than that).
→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Awesome explanation ,but can there be a better approach if not to try all combinations?

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      You can do some pruning to consider less combinations of mixing 2's with 3's, but even if you try all combinations, including those that exceed the amount of primes you have and those that don't use all of them, there will be only 18 * 11 * 9 * 7 * 6 * 5 = 374220, so trying to make it more efficient is not worth it in my opinion.

      → Reply