A number problem
Moderator: Board moderators
A number problem
I'm looking at this problem but don't see a very elegant or fast solution. Does anybody have a good idea for an algorithm solving this problem?
It's problem B of
http://www.acm.inf.ethz.ch/ProblemSetAr ... 7/ek97.pdf
It's problem B of
http://www.acm.inf.ethz.ch/ProblemSetAr ... 7/ek97.pdf
This doesn't look much like a number problem to me. My solution would be to solve this problem backwards  start from 1 and use BFS to determine the best solution for each number. You may stop the search when you know the answer for N<=20000. Then you answer the queries in O(1) time each.
The idea of the BFS: suppose that the best solution for 25 is MMS. By extending this solution we obtain (not necesarily best) solutions for more numbers. E.g. for 50 and 51 DMMS is a solution. If we already have a better solution, we discard this one, otherwise we enqueue the number we just found and this is the best solution for it. By cleverly using BFS we process each number at most once.
The idea of the BFS: suppose that the best solution for 25 is MMS. By extending this solution we obtain (not necesarily best) solutions for more numbers. E.g. for 50 and 51 DMMS is a solution. If we already have a better solution, we discard this one, otherwise we enqueue the number we just found and this is the best solution for it. By cleverly using BFS we process each number at most once.
Minilek, there is a simple bound: keep on dividing and you'll always get 1. For n<=20000, this means that the number of operations is always smaller than 15. So iterative deepening is an option, but if you need 13 operations it's still a very large searchspace... (maybe not too large though!)
Misof, I have thought about that approach, but there is a problem. Conisder n = 5^6 = 15625. One (short) way to get to 1 is MMMMMMS, i.e. multiply by 2^6 to get one million and then sort.
So during the BFS, we need also consider numbers much larger than 20000 (maybe even up to one billion, since that's the limit of the 9digit display). I understand that we can stop whenever we have dealt with all numbers under 20000 but that doesn't mean the queue can't fill up with millions of numbers... Do you see what I mean?
Let S(n) be the set of numbers that can be reduced to 1 in n steps. Then
S(0) = {1}
S(1) = {2,3,10,100,1000,10000,100000,1000000,10000000,100000000}
S(2) = {4,5,6,7,20,21,200,201,....,200000001,5,50,....,50000000,30,300,...,300000000}
S(3) = {8,9,11,12,13,14,15,40,42,....}
As you can see, this queue blows up exponentially I think.
Can you guys think of a suggestion?
Misof, I have thought about that approach, but there is a problem. Conisder n = 5^6 = 15625. One (short) way to get to 1 is MMMMMMS, i.e. multiply by 2^6 to get one million and then sort.
So during the BFS, we need also consider numbers much larger than 20000 (maybe even up to one billion, since that's the limit of the 9digit display). I understand that we can stop whenever we have dealt with all numbers under 20000 but that doesn't mean the queue can't fill up with millions of numbers... Do you see what I mean?
Let S(n) be the set of numbers that can be reduced to 1 in n steps. Then
S(0) = {1}
S(1) = {2,3,10,100,1000,10000,100000,1000000,10000000,100000000}
S(2) = {4,5,6,7,20,21,200,201,....,200000001,5,50,....,50000000,30,300,...,300000000}
S(3) = {8,9,11,12,13,14,15,40,42,....}
As you can see, this queue blows up exponentially I think.
Can you guys think of a suggestion?

 Learning poster
 Posts: 60
 Joined: Tue Aug 13, 2002 2:39 am
 Location: Mexico
Easy
Well, I think you elevated the complexity of this problem . It's just DP, you need an array of [20,000][4], where [Num][Op] indicates the minimum number of operations as Op as first operation(ie. DMMS, the D) and number Num. You can see that with this model you can manage minimum length and lexicographic order:).
Greetings.
Greetings.
Miguel & Marina

 Learning poster
 Posts: 60
 Joined: Tue Aug 13, 2002 2:39 am
 Location: Mexico
I forgot
Till 40,000; but calculating till 20,000..There's no sense to make a number till a very big one of 9 digits, we may need at least 14 M operations to make 20,000 a number bigger than 9 digits, surely we can make 20,000 into 1, in 14 D operations;).
The only "valuable" way it can decrease monotonically is when the number multiplied by 2 generates many zeros at end. Two ways: achieved by a zero, in which multiplying by 2 is redundant (we can apply sort directly and decrease the number) and with a 5, in which the result come back to the first point, we may sort and back to a number smaller.
Conclusion: we need at least one multiply for every number of D digits, then a sort will decrease the number at least (D1)..of course the answer can have more M's, but en every step that M will be smaller than 2, 3 operations before.
I don't know if I explained logically, I'm not so good trying to device such things.
Good luck!
The only "valuable" way it can decrease monotonically is when the number multiplied by 2 generates many zeros at end. Two ways: achieved by a zero, in which multiplying by 2 is redundant (we can apply sort directly and decrease the number) and with a 5, in which the result come back to the first point, we may sort and back to a number smaller.
Conclusion: we need at least one multiply for every number of D digits, then a sort will decrease the number at least (D1)..of course the answer can have more M's, but en every step that M will be smaller than 2, 3 operations before.
I don't know if I explained logically, I'm not so good trying to device such things.
Good luck!
Miguel & Marina

 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
Miguel Angel,
Your DP solution will not work. Consider 19625 for which the optimal sequence is MMTMMMSDD.
The intermediate numbers are: 19625, 39250, 78500, 87500, 175000, 350000, 700000, 7, 3, 1.
This might be an extreme case, and it might be true that the maximal number to consider is much smaller than a nine digit number, but [20000][4] is far too small. And [1000000][4] is starting to get infeasible.
My DFS plus memoization calculates the 20000 strings in about 2 minutes. I think this is about as fast as it gets.
Your DP solution will not work. Consider 19625 for which the optimal sequence is MMTMMMSDD.
The intermediate numbers are: 19625, 39250, 78500, 87500, 175000, 350000, 700000, 7, 3, 1.
This might be an extreme case, and it might be true that the maximal number to consider is much smaller than a nine digit number, but [20000][4] is far too small. And [1000000][4] is starting to get infeasible.
My DFS plus memoization calculates the 20000 strings in about 2 minutes. I think this is about as fast as it gets.

 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
I just verified: the maximal intermediate number in an optimal sequence is 1000000. It is reached for 15625 in the sequence MMMMMMS. But this doesn't mean that you don't need (much) bigger intermediate numbers during the evaluation of suboptimal sequences.
For instance: 19940 has the optimal sequence SDDSDDDDDS with a length of 10. During the search you will have to consider the alphabeticaly smaller MTMTMTMTMT which leads to 988422100 (if I made no mistakes in my hand calculation), a nine digit number...
For instance: 19940 has the optimal sequence SDDSDDDDDS with a length of 10. During the search you will have to consider the alphabeticaly smaller MTMTMTMTMT which leads to 988422100 (if I made no mistakes in my hand calculation), a nine digit number...

 Learning poster
 Posts: 60
 Joined: Tue Aug 13, 2002 2:39 am
 Location: Mexico
:)
Yeap you are right!. 15625 in fact it's the biggest power of 5 that it's less than 20000, so for sure can extend till 6 zeros(for every 5), and then sort, so I should have realized about that..But then if the number of 19940, doesn't take that longest sequence, why to take it?..well well until you realized that , you can know..So, finally you can build a 1000000x4 array, of shorts, it's not the big deal in memory, and if done correctly it mustn't take so much operations..;)
Miguel & Marina

 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
I think little joey's right: even if 1000000 is an upperbound of the max. number needed (and how do we know this without calculating everything in another way?), it might not even be very fast....
little joey, you say you use DFS with memorization. Do you memorize till a certain max number than, i.e. the first million numbers for example?
If the fastest solution will take 2 minutes then I don't like the problem. I spend time on finding a fast solution and it doesn't exist....
little joey, you say you use DFS with memorization. Do you memorize till a certain max number than, i.e. the first million numbers for example?
If the fastest solution will take 2 minutes then I don't like the problem. I spend time on finding a fast solution and it doesn't exist....

 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
I memoize only the first 20000 numbers, extending it to 1000000 didn't speed it up significantly. I think the chance that a big number get's hit again is not so great.
The problem description doesn't say how many input numbers there are to be expected, but if it's reasonably small, say 100, the program could still finish within a second.
BTW it's called memoization not memoRization don't know why.
The problem description doesn't say how many input numbers there are to be expected, but if it's reasonably small, say 100, the program could still finish within a second.
BTW it's called memoization not memoRization don't know why.

 Learning poster
 Posts: 60
 Joined: Tue Aug 13, 2002 2:39 am
 Location: Mexico