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.

# | User | Rating |
---|---|---|

1 | Benq | 3783 |

2 | jiangly | 3741 |

3 | tourist | 3622 |

4 | Um_nik | 3536 |

5 | maroonrk | 3526 |

6 | inaFSTream | 3477 |

7 | fantasy | 3468 |

8 | ecnerwala | 3454 |

9 | QAQAutoMaton | 3428 |

10 | fivedemands | 3381 |

# | User | Contrib. |
---|---|---|

1 | Um_nik | 185 |

2 | adamant | 178 |

3 | awoo | 177 |

4 | nor | 169 |

5 | maroonrk | 165 |

6 | -is-this-fft- | 164 |

7 | antontrygubO_o | 153 |

8 | ko_osaga | 151 |

9 | dario2994 | 150 |

10 | SecondThread | 149 |

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.

↑

↓

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/03/2023 18:27:46 (l1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Don't see why "find max divizor below M and divide" solution doesn't work.

m= 8,n= 216, optimal solution is 6 × 6 × 6, greedy will give 8 × 3 × 3 × 3.Thx

This may work:

Find all primes <= M. Let size of this array be x. then

should produce di in descending order.

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/101490

Edit: actually, this problem wants the actual answer, not just the length of the answer so it's a bit different. My mistake.

tfg All the solutions I saw for this problem were

DPsolutions, if you can provide anyGreedySolution for this problem I will be thankful.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.

Thank you Noam527, but I still can't find the Greedy Solution :|

Maybe this works, factorize

N, for now, the setDis the prime factorisation ofN. If any element ofDis >M, print impossible.Otherwise keep removing the smallest element from the set

D, let's call itAand findBthe largest element inDsuch thatA*B<= M, removeBand 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

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)

You're right, it looks like DP is the way to go

Can you guys tell me how

DPsolution 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 exceedM?dp(X) = min # of numbers to factorize X such that each # is <= M

dp(1) = 1

dp(i) = min(1 + dp(i / d)) for all d <= M