Coprime Components. Please share your idea on how to solve this task for 100 points. asked 20 Oct, 18:56

Tons of opportunities for optimisation, but actually not required as the max time ~ 0.15 seconds. I really liked the problem. Thanks to the author. answered 20 Oct, 21:32
Can you provide a proof for pt 121k ?? And I will stop complaining about weak TC. Only 3 TC (for 50 pts) had no of distinct no <5k and for them I bf. For others answer was simply no of set with size 1 + one large set containing rest of elements. If possible please prove that above assumption is correct. I will take back my claim of weak TC.
(20 Oct, 22:28)
1
@aryanc403 See my answer https://discuss.codechef.com/questions/137838/pleaseshareyourapproachtocpcompproblemofoctlongchallenge/137882
(20 Oct, 23:19)
2
@algmyr  thanks for the nice clarification with example, just saw the comment, but you already answered it. @aryanc403 , I hope it is clear now. And yes, probably the most complex case could be constructed (without 1 and any primes > 100K or even 60K ), I'm also agree that the test cases were a bit weak, specially initially, and then later adjusted a bit.
(21 Oct, 01:07)
One observation that severely limits things is that you can't have too many unique primes among your numbers. If you have > 6 unique primes in your list you're already forcing numbers $> 2\times10^5$ for things not to be connected.
(21 Oct, 01:43)

Regarding the 121k in @lboris answer, and to answer @aryanc. You can easily verify this for yourself by just writing a program like
which will print 121581. answered 20 Oct, 23:18
Thank you very much. Can you write one program which can split these no in 2 sets which has nos like. {2.3.5,7.11.13,17.19.23} and {7.3.5,17.11.13,2.19.23} these 2 sets are 2 different conected components. And nos like these were present in 4 test cases. But those TC has no of unique no less than 5k so brute force for them was enough. And that is the reason why I'm complaining for weak TC.
(20 Oct, 23:37)
The sets you're describing (triplets) will not be large at all. You can only continue until the product exceeds $2 \times 10^5$. This means the smallest factor can't be larger than around 60.
(21 Oct, 01:38)

@lboris why do you sort by number of primes, then by the primes themselves? answered 22 Oct, 23:25
2
Very good question. (Seriously! Well done.) The answer is: in that way you maximise the number of qwords that will be all 1s (0xfff...) and guaranties skipping most of them before finding which index is required to be united with the current "x".
(23 Oct, 00:17)
i see. so if say the sequence is [(2), (2, 3), (2, 5), (7, 11), ...], when we arrive at (7, 11), we will be unioning with all the three previous ones? or do you do something different? because you said "index"; do you find one particular index to union with or union with all valid ones?
(23 Oct, 03:38)
Union with all valid, to be more precise  with all the indices that according to the mask have none of the primes which present in "x".
In your example if "x" is 2, then corresponding bitset for numbers will be: 1110... when I arrive to this "0" (which correspond to (7,11)) I will union "2" with "7,11".
(23 Oct, 04:36)
yeah, that's how i understood it too. i implemented your idea in python ( https://www.codechef.com/viewsolution/21156377 ) but it TLE's on 4 cases. you think it's a python problem, or did i miss a vital part of the algo?
(23 Oct, 07:41)
(by the way, it was actually slower when i included the sorting by number of primes/primes, so i removed that part; that's also why i was asking about your rationale for the sorting)
(23 Oct, 08:51)
"guaranties skipping most of them before finding which index is required to be united with the current "x"." @lboris can you please elaborate this a little more?
(23 Oct, 10:57)
Your solution in Python is slightly wrong, instead of creating the mask as array of integers (or longs) you create it in python as one big number, that means that every time you do operation on entire set (effectively falling back to O(N^2)/2 ) , you also in the solution create the mask upfront, which is wrong again, you don't need this extra run through the array. The comment space is too small, take a look at the solution https://www.codechef.com/viewsolution/20592710 specially understand the line: "if ((~bs) != 0) { "  that what makes it to skip most part...
(24 Oct, 00:33)
In your python solution make mask a list of integer (32 bit each) rather then single biginteger.
(24 Oct, 00:35)
showing 5 of 8
show all

If there is atleast 1 prime number in the input array , i will pick one prime number and also i will find all the numbers whose gcd with our current prime number is 1 , at the same time i will erase those numbers from the multiset (initially i inserted all the input elements into it) ! Now they will be in a single component , for the rest of the elements , they wont form components among themselves (because , they all are having our picked prime number as their prime factor ) ! Either they will join the earlier component (because there can be some integer in the formed component whose gcd with our current element is 1) or they will form a separate component each of size 1 ! This can be done by inclusionexclusion in O(64) time (I mean , checking whether there is an element in the initial component whose gcd with our current element is 1) ! If there are no primes in the input array , i will just find the components using BFS ! Feel free to ask if you have any doubts ! answered 20 Oct, 22:06
I also used inclusion exclusion principle to find which no for a singleton set. And added one assuming that rest of no form a single large set. Sadly this passes for all test cases except 4 ( 1 from smallest set anf 3 from largest ). But all test cases had no of unique no < 5000 ( after reducing then as used by @lboris simply used if else and brute forced for these tc to get 100 pts.
(20 Oct, 22:35)
ohh ! I had hard time with this question bro , felt that the tc are really weird !
(20 Oct, 22:43)

Got stuck too. I would love to know the idea behind it. Solved it by just connecting the 200 numbers with the largest degree to other numbers. Man, the tests are weak as hell. answered 20 Oct, 20:06

To @pluristiq and @pk301 in regard to sorting: Your solution in Python is slightly wrong, instead of creating the mask as array of integers (or longs) you create it in python as one big number, that means that every time you do operation on entire set (effectively falling back to O(N^2)/2 ) , you also in the solution create the mask upfront, which is wrong again, you don't need this extra run through the array. The comment space is too small, take a look at the solution https://www.codechef.com/viewsolution/20592710 specially understand the line: "if ((~bs) != 0) { "  that what makes it to skip most part... In your python solution make mask a list of integer (32 bit each) rather then single biginteger. In this case you will see that most of the integers in this array are subject to skipping (otherwise you would very quickly finish with single group), the sorting helps to order it in such way. answered 24 Oct, 23:30

You can reduce the number of primes this way. First, you need to use an O(n log log n) prime sieve. 0) If 1 is in the set, then there is one component. 1) Record the number of instances, n, of each number x. If in the end, the number is in a component of size one, then there are n components. If the number is in component of size > 1, then all numbers in the component contribute to a single component (the number of instances don't matter). 1) Reduce multiple powers of a prime to one. 2) If a prime is either unique to particular number or functionally dependent on another prime (a prime always occurs with another prime), you can erase that prime from all the numbers. That is, remove the prime from each number that is a multiple of that prime and add all the instances of that number to the new number without the prime factor. (Be careful if two primes always cooccur; get rid of one) 2a) After erasing the prime p from number x, the new number becomes x'=x/p without the prime. If x' is the only number left, then the number of instances of x' is the final answer. 2b) If x' becomes 1, then all the other numbers are in in the same component as x' and the answer is 1. 3) Find all numbers that contain just one prime and toss them into a hashset. All these primes together belong to the same component C. 3a) If the number of primes is in the hashset is greater than 7, the final answer is one component. 3b) If the product of all those primes is greater the largest number in whole set, then the final answer is one component, because each number from the whole set will be missing at least one prime from the hashset. 3c) Go through all the other numbers. If that number does not contain all the primes in the hashset, then add that number to the component C. 3d) Later in the search phase when we compare numbers together, we can ignore all the primes in hashset, because we tested them already. You can also ignore any number that contained at least one prime from the hashset, because all the other numbers not in component C will have contained every prime from the hashset as a factor and there not be coprime. After this, the number of distinct numbers has fallen sharply. We also eliminated a large number of candidates to pair off from step 3d. This is important because, if the test cases weren't weak, there would be O(n^2) number of pairs that are coprime. So, testing neighbors would TLE even if using a prefix tree solution to prune neighbors. The number of valid neighbors would still be O(n^2). We can take advantage of another optimization. The number of componentsignoring multiple instances of the same numberswill be very small. Then, you can build a disjoint set (unionfind data structure). Although, I didn't brute force, I suspect it would not TLE. The number of values to compare will be a tiny fraction of the original set. You can compare each number to a small group (~20) of numbers containing the least frequent primes. You can also AC by comparing each number to 20 randoms numbers like I did after grouping numbers by their lowest prime factor and not comparing those within the same group. answered 20 Oct, 23:55

Here is a solution with running time O(n log^4 n). It got tle but I believe with some optimizations it can pass the testcases. I will purposefully ignore off by one error in this solution:
answered 21 Oct, 21:05

@furious__ can you please explain the part where there are no primes in the input array ,how you have managed bfs there. answered 23 Oct, 13:08

Just wait... SnackDown 1A has a problem similar to it.