Omar_Morsi's blog

Number Theory Problem
By Omar_Morsi, history, 7 years ago, In English

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.

  • Vote: I like it
  • +4
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

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

    → Reply
»
7 years ago, # |
  Vote: I like it -10 Vote: I do not like it

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<<d/prime[i]<<" ";
    }
}

should produce di in descending order.

→ Reply
»
7 years ago, # |
← Rev. 3   Vote: I like it +14 Vote: I do not like it

If anyone wants to test a solution (or look through solutions if you have coach mode), that's problem H here: http://codeforces.me/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.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
7 years ago, # |
  Vote: I like it +16 Vote: I do not like it

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.

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it +4 Vote: I do not like it

    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)

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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?

        → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

          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

          → Reply