Блог пользователя micklepru

Автор micklepru, история, 9 лет назад, перевод, По-русски

UPD: Большое спасибо за помощь, наконец разобрался что к чему. Надеюсь, теперь это поможет кому-нибудь ещё.

Привет, Codeforces!

Помогите разобраться с алгоритмом.

Собственно задача Если коротко, то у нас есть два целых числа N и M, мы должны посчитать количество чисел, которые могут быть получены из числа N перестановкой цифр, и которые делятся на M.

Решение "в лоб" — просто пробежаться по всем перестановкам цифр числа N и проверить каждую. Это дает нам N! операций, что слишком медленно. Интуитивно понятно, что нам в любом случае прийдется проверить каждую из перестановок и я не могу понять, как мы этого избегаем.

Используем ДП с битовыми масками: dp[i][j] — количество чисел, полученных перестановкой некоторых цифр N(которые определены маской i), и остача от деления на M равна j. Например, N=12345, dp[01101][2] — количество чисел, сложенных из 2,3,5 (такие как 352), и остача от деления на М равна 2 (M=50, 352%50==2). Для каждой маски i мы пробегаемся(переменная k) по всем еще не использованным цифрам((i & 1<<k)==0) и добаляем их в конец каждой перестановки(i | 1<<k). У старой перестановки остаток j, у новой — (j*10+N[k])%M, где N[k] — k-я цифра N. Увеличиваем dp[i | 1<<k][(j*10+N[k])%M] на dp[i][j].

Вот код для лучшего понимания: 12205724 Заметки: timesRepeat используется, чтоб избавится от повторяющихся перестановок, которые возникнут если в N есть повторяющиеся цифры. (i||N[k]) для избавления от лидирующих нулей

Используя ДП, мы снизили сложность от N! до (2^N)*N, что позволяет нам сдать задачу.

Рассмотрим данное решение: выглядит так, что мы пробегаемся по всем возможным перестановкам. Например, маска 0110 может быть получена как 0100 добавить третюю цифру в конец или же к 0010 добавить вторую цифру в конец. Для каждой маски мы добавляем каждую цифру в каждое место. Я не пойму, как мы проделываем меньше работы, но рассматриваем все перестановки.

Возможно это очень глупо, но я никак не вьеду. Помогите разобраться и подскажите, когда мы можем использовать такой приём. Можем ли мы применять его для любых перестановок и задач над ними?

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
9 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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!

»
9 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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.

»
9 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

You write: "For example, bitmask 0110 can be obtained as 0100 adding third digit to the end or 0010 adding second digit to the end." Now consider the next step: the bitmask 0111 can among others be obtained from 0110, and now your two ways of reaching 0110 are taken care of using one operation only.

It might help to look at the following somewhat silly DP to calculate the number of permutations:

dp[0] = 1;
for (int mask = 1; mask < (1 << N); mask++)
    for (int i = 0; i < N; i++)
         if (mask & (1 << i))
             dp[mask] += dp[mask ^ (1 << i)];

Here, dp[mask] is the number of ways to obtain mask, and dp[(1 << N) - 1] is of course N!.

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

in this comment it is well explained. however, this maybe a hard example for dp magic i suggest you to see this problem. it is somehow easier, at least no need to mask anything here. in short the problem states that you have(n <= 10000) number and (k <= 100) after you read this n numbers you have to say whether we can put operations between the numbers (+, -) that the final result will be divisible by k or not. as a naive solution we have (n-1) gabs between the numbers and we are to choose to put + or - this is 2^(n-1) possibilities! then for each possibility we calculate the result and see if it's divisible or not. However we can see that we are not interested in the final result, we are interested in its modulo on k, and from there we can see how dynamic programming will work just define state dp[i][j] = can we put operations between numbers (0 ... i) to reach modulo j on k, and the transition is simply dp[i][j] = dp[i-1][(j+A[i])%k] || dp[i-1][(j-A[i])%k], so we reduced O(2^(n-1)) to O(n*k) !

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

При добавлений новой цифры, как он изменит остаток?

remainder = (remainder * 10 + added) % mod

Значит, при добавлений новой цифры тебе важно только какие цифры до нее. Тебе не важно, в каком они порядке.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can Anybody show me the whole procedure for following input?

Input: 123 3 Output: 6

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Жыл один парень и однажды его сбила машина, ноги отказали и он не мог ходить(((( друзья помогали но потом перестали а девушка бросила... И вот он отчаялся и решил спрыгнуть из моста, но когда он уже свесился с перил какойто прохожий расказал ему про дп с битовыми масками.. парень не поверил но прыгать не стал, а поехал домой, зарегался на кодфорсе и стал изучать дп с битовыми масками. И вот когда он сдал задачу на контексте этой техникой, парень уверовал по настоящему и произошло чудо ОН ВСТАЛ И НАЧАЛ ХОДИТЬ!!! И стех пор никогда больше не болеет!