hiteshn97's blog

By hiteshn97, history, 5 weeks ago, In English,

While solving I came up with an algorithm, but don't know the permutation and combinations to proceed further. The algorithm is as follows:

1) Input the numbers in a vector "v"

2) Make a vector "primes" consisting of the prime numbers using Sieve of Eratosthenes.

3) For every element in v, divide it by all primes smaller than it (if divisible).

4) Sort it

5) We will now have vector consisting of (1,1,1,1,2,2,2,3,3,5,5,6,6,6,7 ... types) i.e. all numbers except of perfect squares (1 will be there) Now for the part I could not solve :

6) I want to arrange this vector thus formed of length n in such a manner that no 1's appear together, no 2's appear together, no 3's appear together ...etc. For example, the given case : {1,4,2} after step 3: {1,1,2} after step 4 {1,1,2} (since already sorted) after step 5 {1,2,1} is the valid arrays.

7) I have to multiply this by a certain number but let's leave this for now.

How can I solve the part 6).. ?

 
 
 
 

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by hiteshn97 (previous revision, new revision, compare).

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I do not think such an approach will work. From what i understood, {12,9} will convert to {3,3} after step 4. Step 5 doesn't let {3,3} to be positioned adjacently. And the answer to this array will be 0. On the contrary, 12*9=108 is not a perfect square and hence both {12,9} and {9,12} are valid permutations!

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Oh damn.. I don't know how I missed this. I will test my algorithm more carefully from next time. Thank you for your time :)