spirited_away_'s blog

Atcoder abc077 , Problem : small multiple.
By spirited_away_, history, 5 years 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

Comments Comments (5)
| Write comment?
»
5 years 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.

→ Reply
  • »
    »
    5 years 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?

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

      ye, I still don't understand this point.

      → Reply
      • »
        »
        »
        »
        5 years 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

        → Reply
        • »
          »
          »
          »
          »
          5 years 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.

          → Reply