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: 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[01101][2] — 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?