micklepru's blog

By micklepru, history, 4 years ago, , UPD: Thank you for your help, sort it out for myself. Hope this may help someone else now.

Hello, Codeforces!

I ask you to help me understanding how does the algorithm work.

Here is the problem. Basically we have two integers N and M, we need to find how many numbers obtained by rearranging digits of N are divisible by M.

So naive solution is just go through all permutations of digits of N and check all of them. That gives us N! operations, which is unacceptably slow. Intuitively, we must go through all permutations anyway. And I am very confused about how do we not.

We use bitmask DP: dp[i][j] — amount of numbers, obtained by permutation some digits of N(specified by bitmask i), and remainder after diving it by M is j. For example N=12345, dp — amount of numbers, constructed with 2,3,5 (such as 352), and after division by M remainder is 2 (M=50, 352%50==2). For each bitmask i we iterate(variable k) through all unused yet digits((i & 1<<k)==0) and add it to the end of every permutation(i | 1<<k). Old permutations gave remainder j, now it will be (j*10+N[k])%M, where N[k] is k-th digit of N. So we increase dp[i | 1<<k][(j*10+N[k])%M] by dp[i][j].

Here is the code to make it easier: 12205724 Note: timesRepeat is used to eliminate duplicate permutations regarding repeated digits in N. (i||N[k]) is to get rid of leading zeros

Using DP, we descend from N! to (2^N)*N, which gives us accepted.

Consider the solution: seems like we iterate through every permutation. For example, bitmask 0110 can be obtained as 0100 adding third digit to the end or 0010 adding second digit to the end. I cannot understand how are we doing less work, but logically we go over every permutation.

Maybe it is stupid question, but I am really confused. Please help me to sort it out and tell when do we use such method. Can we use it to any kind of permutations? dp, Comments (5)
 » 4 years ago, # | ← Rev. 3 →   Since the possible mods are limited, if we used 4 numbers for example and our current modulo is 3 ,and another permutation of those 4 numbers gives also modulo 3, in the naive solution if we have 18 digits we would try the left 14 digit permutations twice, but the answer of this subproblem is saved in the DP table you don't have to recalculate it , you just add the numbers as you calculated them before!, So the complexity is cut to the number of subproblems you need to calculate!
 » First of all, the actual complexity is 2N * M * N.I'll try to explain why you don't need to go through all the permutations, then maybe the DP solution will start making sense. The key idea, like in every other DP problem, is that you don't need to know the exact intermediate state (in this case, the prefix of the permutation) to be able to compute the answer for the whole problem. Instead, you can define features of intermediate state that are important for your problem -- in this case, the subset of digits that have been used and the remainder modulo M that this prefix has. Two prefixes that consist of the same subset of digits and have the same remainder will "behave" in the same way with regard to the function you are trying to compute (i.e., the number of permutations that divide by M).This probably didn't make so much sense to you, so let's look at an example. Suppose M = 7 and N = 1122334. Look at the following two prefixes, both comprised of (multi)set {1, 2, 2, 3, 3}: 31232 and 12332. They both have remainder 5 modulo M = 7. You obviously have the same set of numbers that can be appended to these prefixes. On the other hand, for any digit X, when you append it to either of this prefixes, the resulting remainder will be the same for both of them. For example X = 1: , . If this confuses you, think about the rules of how modulo operation behaves for multiplication: , therefore the exact value of A does not matter, only does. Hence, you don't care any more if it was prefix 31232 or 12332 that you were trying to complete, the number of ways to complete it will be the same. This means that you could count how many prefixes are there comprised of {1, 2, 2, 3, 3} with remainder 5 modulo M and see in how many ways any of them can be completed and multiply these two numbers, instead of computing the number of ways to complete every one of these prefixes.Hope this helps a bit.