Sereja has an integer number A that doesn’t contain zeroes in its decimal form.
Also he has N integers B, B, …, B[N].
Let us first define function f for a number A as follows.
Now he has to reorder the digits of A such that f(A) is minimum.
Please help him in finding most optimal A.
A has upto 1000 digits. N=100 and B* is upto 10^6.
I haven’t found solution that is better than random, because of modulo function, so the best solution would be one, that can try as many A as possible.
So we need to optimize finding F(A). We can swap two digits of |A| and calculate F(newA) in O(N) time (because we can represent A mod B as (a0*100 + a1*101 + a2*102 …) mod B = (a0*100 mod B + a1*101 mod B + a2*102 mod B …) mod B).
So we can just find some random A and then try to swap some random not equal digits and check if it is better. Then we work with new A.
Also we can try next algorithm: fix some random A and swap some digits while we can make F(A) < F(newA). Then fix some new A and do it as many times as possible.
Other greedy techniques can also be used. Also techiniques like simulated annealing and evolutionary algorithms can be used.
Here’s an interesting and useful blog post on this: http://gauravsen.blog.com/2015/01/14/hello-world/