Pixar's blog

By Pixar, history, 6 weeks 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  

»
6 weeks 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...)

  • »
    »
    6 weeks 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?

    • »
      »
      »
      6 weeks 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
»
6 weeks 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.

  • »
    »
    6 weeks ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it
    Solution
»
4 weeks 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?

»
4 weeks 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.