spirited_away_'s blog

By spirited_away_, history, 5 months ago, In English,

In problem small multiple , you are asked to the smallest possible sum of the digits in the decimal notation of a positive multiple of K.

what i did was i ran a loop from 1 to 70000000 and compute answer for each i. It gave WA in some test cases. 16/66 MY solL:

The editorial mentions Construct a graph with K vertices, start from 1 and answer will be minimum distance from 1 to 0 , +1.

Though i understood the editorial, But i couldn't get the proof behind it. why it will give right answer. Why we are creating only k vertices and considering each number as x % k.

Can anyone who solved it, explain the logic behind it. Or any other approach for solving this problem.

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

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

Can someone explain me these lines in the editorial , :

Note: Isn't the trouble with '9' important? Suppose that the algorithm above finds an invalid solution that contains a digit "10" at position i. However, due to the periodicity of powers of tens, (whenKis comprime to 10) we can find another j such that 10^i and 10^j are the same in modulo K, so we can move one digit fromi to j. Even when K is not coprime to 10, we canmake it periodic by attaching sufficient number of zeroes at the end.

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

    since upto 9 digit sum will increase, but when we will encounter 10, sum will decrease, then why we r still adding 1?

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

      i implemeted the editorial , https://atcoder.jp/contests/abc077/submissions/5545298

      but still couldn't understand the last part , someone pls tell .

      • »
        »
        »
        »
        5 months ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

        what i understood is, Your sum of digits only decreases on some multiple of 10.

        Say 109 -- > 110

        suppose k = 11, so answer will be 2.

        i.e cycle --> 1-->10--->0. so 0+1 = 1 + extra(1) = 2.

        so there are 2 cases arises, some multiple of 10 will be in answer, else not.

        here we will proof if some multiple of 10 is in answer, either we have already hit it or its first one itself.

        so 110 is a multiple of 10*11, so if its in answer then obviously we can remove extra leading zeros, until no zeros left. so 110 --> 11

        since we already hit 11 in our answer,either we will not hit 110 ever or if 11 is not in answer, we will surpass it.

        so in either case, it will not affect our answer. You can dry run for other cases too.

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

      ye, I still don't understand this point.

      • »
        »
        »
        »
        5 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        i think only way is to try dry run on test cases like this. the solution of this problem is really out of box thinking, even if u get graph concept u will stuck in multiples of 10 unimportance which can only be observerd by testing on various testcases

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

          seems like we don't need those observations required in editorial , normal dijkstra with (sum%N) as the state works checkout this submission https://arc084.contest.atcoder.jp/submissions/1737958 , but with this logic iam not sure of the time complexity (How many states will we visit , it will definitly be less than N*(least digit sum which is also a multiple .) ) , the editorial gives a clear upper bound though.