undefined_error_'s blog

By undefined_error_, history, 5 years ago, In English

Hi, I am trying to solve the problem for a while but couldn't finish. Can anyone please help me in details that how can I solve the problem.

Problem Link: https://ibb.co/b5DgKwN

Thanks in advance. :) Sorry for my poor english. :)

| Write comment?
»
5 years ago, # |
Rev. 6   Vote: I like it 0 Vote: I do not like it

I think that this problem can be solved using binary search. If a number X is divisible by M, then X = F * M. And we can binary search this F.

   int l = 1, r = N / M + 1;
   int n_cnt = cnt(N);
   while(l < r){
      int mid = (r + l) / 2;
      if(cnt(mid * M) == n_cnt)
         r = mid;
      else
         l = mid + 1;
   }

In function cnt we just count amount of digits in our number like this:

int cnt(int x){
   int cnt = 0;
   while(x != 0)
      x /= 10, cnt ++;
   return cnt;
}

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Are you considering here that N can be 10^100? If N was <= 10^18 then we can compute without binary search

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Ohh, sry. Didn't notice the constrains

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Let's say number of digits in N is x therefore you have to find smallest multiple of M which is greater than 10^(x-1). Let's call the number to be multiplied as K and number of digits in M as y. If M is perfect power of 10 then K will be 10^(x-y)(i.e if N = 100, M=10, K = 10), otherwise K will have (x-y) digits(i.e if N = 100(=10^2), M = 5(=5x10^0) then K = 20 which has 2 digits). Now as you know number of digits in K, now start from most significant digit and for each digit position i find largest number which when multiplied with M gives number smaller than 10^(x-1) and set that value there. Then finally add 1 to K to get the number just greater than 10^(x-1) as number K which we had found gives multiple just less than 10^(x-1). code to multiply strings https://www.geeksforgeeks.org/multiply-large-numbers-represented-as-strings/

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    you have to find smallest multiple of M which is greater than 10^(x-1)

    You misunderstood the statement. The priority is to minimize the number of different digits.

»
5 years ago, # |
Rev. 4   Vote: I like it +17 Vote: I do not like it

The problem can be reduced to knapsack mod $$$M$$$ : define $$$dp_{i,j}$$$ as the minimal number of digits to change, knowing that first $$$i$$$ digits of $$$X$$$ are fixed, and that the current value of $$$X \bmod M$$$ is $$$j$$$.

Let $$$D \leq 100$$$ the number of digits in $$$N$$$. There will be $$$O(D \cdot M)$$$ states and $$$10$$$ transitions. Reconstruction of $$$X$$$ is easy. Final number of operations will be around $$$10^9$$$, my code works in less than 200ms on custom invocation of Codeforces (optimize cache usage, don't use long long, substract instead of using modulo operator).