### Omar_Morsi's blog

By Omar_Morsi, history, 4 years ago,

Can you provide a Greedy solution for the following problem ?

Given N <= 1e18 , M <= 10,000

Provide an array D = [d1, d2, d3, ... , dk] , such that d1 * d2 * d3 * ... * dk = N, di <= M, k should be minimized, or print impossible.

• +4

 » 4 years ago, # |   +1 Don't see why "find max divizor below M and divide" solution doesn't work.
•  » » 4 years ago, # ^ |   +15 m = 8, n = 216, optimal solution is 6 × 6 × 6, greedy will give 8 × 3 × 3 × 3.
•  » » » 4 years ago, # ^ |   0 Thx
 » 4 years ago, # |   -10 This may work:Find all primes <= M. Let size of this array be x. then for(int i=x-1;i>=0;i--) { while(d<=M && N % prime[i] == 0) { d *= prime[i]; } if(d > M) { cout<
 » 4 years ago, # | ← Rev. 3 →   +14 If anyone wants to test a solution (or look through solutions if you have coach mode), that's problem H here: http://codeforces.com/gym/101490Edit: actually, this problem wants the actual answer, not just the length of the answer so it's a bit different. My mistake.
•  » » 4 years ago, # ^ |   0 tfg All the solutions I saw for this problem were DP solutions, if you can provide any Greedy Solution for this problem I will be thankful.
 » 4 years ago, # |   +16 if you take the logarithm of N and all of its divisors that are at most M, then now you need to find a subset of minimal size that sums up to N (an element can be picked multiple times). This is basically knapsack with real numbers now. Since you want it greedy... Well I guess it could have some properties:For instance, some numbers from which you pick a subset are multiples of each other which could help the greedy solution.I don't think this one helps, but the numbers are pretty low... although the amount of numbers can be large.If I missed anything please say.
•  » » 4 years ago, # ^ |   0 Thank you Noam527, but I still can't find the Greedy Solution :|
 » 4 years ago, # | ← Rev. 2 →   0 Maybe this works, factorize N, for now, the set D is the prime factorisation of N. If any element of D is > M, print impossible.Otherwise keep removing the smallest element from the set D, let's call it A and find B the largest element in D such that A * B <= M, remove B and insert their multiplication back in the set. Keep doing this until you can no longer find two elements to multiply in the set.EDIT: you actually should keep picking the 2 largest elements from the set, but this solution is for the problem you described, not sure how it would work for problem H in the gym
•  » » 4 years ago, # ^ | ← Rev. 2 →   +4 KarimElSheikh Sorry for the late response.Assume that N = (2 * 3) * 5 * 11, M = 11 * 6 What you will do is taking in the first Box (11 * 5), second Box (6). Of course this will lead to one of the optimal solutions in this case, but wasn't it better if we took in the first Box (11 * 6) -> Leaving no gaps (trying to make use of the box as much as we can), and putting just 5 in the second Box ?Now look at this Example N = (2*3) * (2*3) * (2*3) * 5 * 5 * 5 * 23 * 23 * 23, M = 23 * 6 = 138 What you will do : First Box (23 * 5) Second Box (23 * 5) Third Box (23 * 5) Forth Box (3 * 3 * 3 * 2 * 2) Fifth Box (2) The optimal Solution is : First Box (23 * (2*3)) Second Box (23 * (2*3)) Third Box (23 * (2*3)) Forth Box (5 * 5 * 5)
•  » » » 4 years ago, # ^ |   +5 You're right, it looks like DP is the way to go
•  » » » » 4 years ago, # ^ |   0 Can you guys tell me how DP solution work with this one? How to find the smallest number of set possible out of the factors of N such that each set's product doesn't exceed M?
•  » » » » » 4 years ago, # ^ |   +5 dp(X) = min # of numbers to factorize X such that each # is <= Mdp(1) = 1dp(i) = min(1 + dp(i / d)) for all d <= M