baukaman's blog

World Finals problem: Factors
By baukaman, 11 years ago, In English

This problem is a very beautiful one. Thanks to kattis we can solve it. Direct link to the problem. The problem statement is easy.

I got WA on test 2. My approach is: take number(initially equal to 1) multply it to current prime or next prime. (which we keep track of). Number of this operations is bounded. (~ 3000000 possibilities). And we can apply some greedy. In doing above we ensure that previous primes count is not less than current. So in factorization we will have more 2's than 3, more 3's than 5 etc.

Once we have some combinations of primes we use formula: S! / (s1! * s2! *s3! *...*sk! ) for example number of different permutationos of number 2*2*2*3*3 is 5!/(3!*2!).

finally, answer. We are given 1000 numbers to handle. We just memorise it in some set and try to find the answers.

Please help me out from this situation or describe your approach.My code can be found here.

Big Thanks in advance.

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

»
11 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

I started off by observing that since the number to factorize has to be < 2^63, this means we have <= 62 prime factors for any number.

Then, we note that if we fixed the numbers of distinct prime factors, let's say... 4 distinct prime factors, the amounts are [2,5,6,7] the minimum integer to be formed is just the first 4 smallest primes, with the smallest prime taking the largest power and so on. In this example, it would be 2^7 * 3^6 * 5^5 * 7^2.

Thus, we can just start with a number 62, and bruteforce all the possible ways any number <= 62 can be spread to create an array in such a way that the array is of descending values as you increase in index. E.g. If we start with the number 3, the possible ways are [3], [2,1], [1,1,1], [2], [1,1], [1]. While doing this, we should also keep track of the smallest number that is formed by multiplying the primes according the number, and immediately cut off if this current running multiplication result is > 2^63. Running this leads to a nice finding that there are only around 40,000 numbers to keep track of.

Here is my code: http://pastebin.com/CC8ysxbd

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

    nice! Thank you!

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

    Actually BigInteger does the great job.

    I finally been able to find out tricky test: n = 8503697224294272000

    Answer does exist! (not 0)

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

Yahoo, editorial is already there!

→ Reply