Yesterday I found interesting solution for 850B - Arpa and a list of numbers.
Let G=gcd of all numbers after all operations.
First observation was if I have some prime number p which divides G, then I can easy in O(number of different numbers in array a) calculate minimum cost to make list good. Now question is only for which prime numbers I will calculate minimum cost.
I have some MAGIC constant and I will calculate minimum cost for first MAGIC prime numbers and MAGIC most frequent prime numbers which are not in first MAGIC primes. Frequency of some p is increased by 1 if p divides a[i].
First idea was to set MAGIC=12, this will pass all official test data, but there is counter-example. We can choose some prime P which is not in first 12 primes and put in array a numbers: P, 2P-1, 2P-1, 4P-1, 4P-1, 6P-1, 6P-1, ... and so on while numbers are less than 10^6.
But there is way how to avoid this problem. We can see that numbers in array in that example grow very fast so N will be small and that means that we can calculate minimum cost for more primes, so if I set
MAGIC=min(3*10^7/number_of_different_numbers_in_array, number_of_primes_less_than_10^6)
then algorithm will work on that example.
Is there any counter-example for this algorithm and if counter-example doesn't exist, why is that?
Here is my solution: 30086367
Very nice solution mkisic, but can be optimized via bitset.
Why are you loving bitset so much?
Because, my friend, I was lost in the programming world until I discovered that bitset can be applied to optimize any and all solutions I encountered on my path (although some may require a lot more time). Also — I soon discovered that even solutions already optimized via bitset can be even more optimized with bitset. So in that sense, every solution can eventually run in around O(1) if you have the patience and the mastery of bitset usage. As I was still amazed by the power of my discoveries I was even more astonished that nobody had been using it to make obvious optimizations to their solutions. Since my discovery I have successfully made optimizations of about 147 algorithms and problems, including the most recent achievement of solving the 'Traveling Salesman' problem over lunch at McDonalds. Bitset is all about thinking outside the box, but if you start thinking about thinking outside the box — you are already back in the box. Bitset will take you outside the box if you trust it and know how to use it. The future is now. p.s. bitset has also improved my love-making abilities (i still never make love but i am no longer sad about it because i optimize algorithms and problems) p.p.s. yes, i do think bitset itself can be optimized via bitset and i am working on it
Common side effects of using bitset include: