### egor.okhterov's blog

By egor.okhterov, history, 5 years ago,

Today I wasn't able to solve the problem D — Small Multiple.
For the whole contest I thought that it is some kind of DP problem, but then I looked at the editorial and it turned out to be a graph problem O_o.

I started looking at the code of the people who solved it and I found out that they are implementing the same idea (more or less). Particularly, I like this solution.

• Is it some kind of a standard problem/idea?
• Does anyone know where I can read about it more abstractly?
• Does anyone know some similar problems that require the same approach?

Here I'll keep the list of problems to train this idea:
1. D — Small Multiple
2. 0-K Multiple
3. INUMBER — Interesting number
4. Sums

• +35

 » 5 years ago, # |   +5 Ah, I had seen a similar problem before, but it took me 20 minutes before I realized this (so I ended up submitting F two seconds late...)
•  » » 5 years ago, # ^ | ← Rev. 2 →   +3 Could you tell us how did you reduce it further? How to prove for a given minimal sum of digits it is possible to construct using 0's and 1's?
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 If you have one number with the minimum possible digit sum, then obviously you can shift over some of the digits to get a number consisting of only zeroes and ones. For example, if K = 27 then you can transform 27 to (103 + 100)·101 + (1018 + 1015 + ... + 100)·100
 » 5 years ago, # |   0 It looks like I've found a similar problem to the original one: http://www.spoj.com/problems/INUMBER/I don't know how to solve it yet, but it looks like we can construct the same graph for it.
•  » » 5 years ago, # ^ | ← Rev. 4 →   0 SolutionConstruct a graph such that a node represents [Number % N, sum of digits].If you do a BFS from this graph and looping from 1 to 9 in the transition, it will yield the minimum number by construction. What remains is tracing the path, and getting the number.
 » 5 years ago, # |   0 I recently attempted this problem. Why does normal bfs tle? Is there a better way?
 » 5 years ago, # | ← Rev. 2 →   0 IIRC Sums uses similar idea. Essentially the technique for these problems is just coming up with a DP formulation, realizing one of the parameters is not used in the transition, and then building a graph for the other parameter and running some shortest path algo.
 » 4 years ago, # |   +8 I've solved 3 out of these 4, and the ideas were quite same and as I solved the first one, the ideas of the other ones came instantly. But I don't understand the complexity! Can someone explain it?
•  » » 4 years ago, # ^ |   +5 Assuming you used bfs where you store modded visited states (which is what I did), the complexity is O(MOD) because vis[i%MOD] = true then there is no point in visiting it again, thus you will visit each state 2 times at most, 2*MOD gives you O(MOD) complexity. This is assuming each transition is O(1)
 » 4 years ago, # | ← Rev. 2 →   +5 Another similar one: 1070A - Find a NumberUpdate: Another problem