UPD: Huge thanks to P_Nyagolov and halyavin for helping — finally solved it! Hope this thread can be useful to someone in the future.

Hello, Codeforces! I just want to thank all of you guyz for this wonderful place uniting these wonderful people. Place where you can improve yourself and if you having any troubles you won't be left alone. Thank you, community! Now to the topic.

I ask you to help me improve my algorithm, which gives TLE.

Here is the problem: For given N (1<=N<=1000) find the smallest positive integer with the sum of digits N which is divided by N. Samples: - input: 1; output: 1 - input: 10; output: 190 Time limit: 2sec.

My solution I used DP approach: dp[sum][rem] — smallest positive integer with the sum of digits sum and remainder after division by N is rem. Now for every integer dp[sum][rem] we iterate through all possible digits and add them to the end. With obtained number we try to improve dp[sum+lastDigit][(rem*10+lastDigit)%N]. Answer is dp[N][0].

But this solution is too slow and runs more than 4 seconds on max test.

Any tips will be appreciated.

UPD: How I solved the problem: instead of storing integers as strings, I stored length and first digit. Then went backwards as halyavin suggested. Here is my code

Hello, Codeforces!

You are on a contest. Invented and implemented solution. Tested it good amount of time. With absolutely confident motion you click SUBMIT and...

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 добавить вторую цифру в конец. Для каждой маски мы добавляем каждую цифру в каждое место. Я не пойму, как мы проделываем меньше работы, но рассматриваем все перестановки.

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