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
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...)
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?
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
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.
Construct 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.
I recently attempted this problem. Why does normal bfs tle? Is there a better way?
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.
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?
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)
Another similar one: 1070A - Find a Number
Update:
Another problem