Yup. I generated your testcase on my PC and my soln. is taking over 10 sec to execute. Would definitely have got TLE with such test case!
Btw what is correct answer for this TC??
3 I suppose.
answer is 3
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:
- Run a sieve to calculate, for each number x, its radical (x but without repeated primes), mu(x), which is the möbius funcion, and then compute all the divisors of x.
- Replace each number by its radical
- Lets define the following procedure p: given a set x of numbers, p(x) will find, for each squarefree integer < 2e5, a number in x coprime to it, or -1 if such number doesnt exist. This procedure will run in O(n log^2 n) time:
- for each squarefree number m, make an array of size 2e5/m that stores, at index i, the number of multiples of m in x less than or equal to im. This can be done with prefix sums and because the harmonic sum is ~log n, this takes n log n time
- For each number y, the amount of coprimes to y less than some bound t is the sum over all of its divisors d of mu[d] × arr[d][t/d] (see answer to this stackoverflow question for more details) , where arr[d] is the array we built at step 4. We can use this to find with a binary search, the smallest integer in x coprime with y in O(log n × amount of divisors of y). Since the sum of the number of divisors is n log n, this can be done for every number x in n log^2 n time. Thus we finished describing procedure p
- Now lets do the following: we will do a number of steps in which every conected component which isnt yet complete will merge with another component. Its easy to se there will be at most log n steps until all conected components are complete.
- In each step, we will split the conected components in two groups many times, such that any two components will appear in different groups at least once. This can easily be done in log n splits by iterating 0 <= e < log n and putting all conected components whose label has the e-th bit set into one group and the rest in the other
- For each of these splits, we can use procedure p to find all conctions from every number to a number in goup 1, and then do the same to find all connections from all the numbers to a number in group 2, and use the union find datastructure to join the components connected by these connections
- If we do that, at the end the union find datasrructure will have all the components. Care has to be taken to deal with equal numbers in the input, but that has already been handled in other comments
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”.
2 Likes
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?
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”.
There are plenty of optimisation opportunities that I already had in mind when implementing the basic version, but looking at execution time I’ve realised - they all not required…
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?
(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)
“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?
@furious__ can you please explain the part where there are no primes in the input array ,how you have managed bfs there.
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 big-integer.
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 big-integer. 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.
1 Like