A number problem

Maniac · Post by **Maniac** » Thu Sep 09, 2004 10:42 am

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

Minilek · Post by **Minilek** » Thu Sep 09, 2004 2:01 pm

have you tried iterative deepening on this problem ?

i do not know how well it will perform since i have no bound on how many operations the answer will be, but it's worth a try maybe

misof · Post by **misof** » Thu Sep 09, 2004 2:11 pm

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.

Maniac · Post by **Maniac** » Fri Sep 10, 2004 1:24 pm

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 search-space... (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 9-digit 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?

Miguel Angel · Post by **Miguel Angel** » Fri Sep 10, 2004 7:57 pm

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.

Miguel Angel · Post by **Miguel Angel** » Fri Sep 10, 2004 8:39 pm

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 (D-1)..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!

little joey · Post by **little joey** » Fri Sep 10, 2004 8:51 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.

little joey · Post by **little joey** » Fri Sep 10, 2004 9:19 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 sub-optimal 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...

Miguel Angel · Post by **Miguel Angel** » Fri Sep 10, 2004 10:55 pm

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

;)

little joey · Post by **little joey** » Sat Sep 11, 2004 12:18 am

I see what you mean. DP-ing with a 4x1000000 array is feasible, I guess, although the implementation can be quite hairy, especialy for generating the parents using the S-operator (there are quite a lot of numbers leading to say 1234 using S). And will it be faster then DFS with memoization?

Maniac · Post by **Maniac** » Mon Sep 13, 2004 11:35 am

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 · Post by **little joey** » Mon Sep 13, 2004 3:56 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.

Maniac · Post by **Maniac** » Mon Sep 13, 2004 4:25 pm

*krijg nou wat* I'm startled but you're right, it's not memorization but memoization for some weird unlogical reason....

Miguel Angel · Post by **Miguel Angel** » Tue Sep 14, 2004 1:36 am

But well, then you only need to store maximum 15 numbers(with B&B surely)..and yeap DP it's TOO weird to do!, DFS is the best solution!

thincal · Post by **thincal** » Sat Sep 25, 2004 11:57 am

how to solve it?

OJ Board

A number problem

A number problem

Easy

I forgot

:)