egor.okhterov's blog

atcoder — D — Small Multiple
By egor.okhterov, history, 7 years ago, In English

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

  • Vote: I like it
  • +35
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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...)

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    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?

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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
      → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it
    Solution
    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I recently attempted this problem. Why does normal bfs tle? Is there a better way?

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
7 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like 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)

    → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

Another similar one: 1070A - Find a Number

Update:
Another problem

→ Reply