please share your approach to CPCOMP problem of OCT long challenge

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.

@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.

2 Likes

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.

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.

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

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?

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.