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.
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.
since upto 9 digit sum will increase, but when we will encounter 10, sum will decrease, then why we r still adding 1?
ye, I still don't understand this point.
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
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.