please share your approach to CPCOMP problem of OCT long challenge

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!

3 I suppose.

answer is 3

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 ( CodeChef: Practical coding for everyone ) 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?

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 CodeChef: Practical coding for everyone
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.