i am unable to understand what thing is done in editorial
Pl help me in understanding editorial
@spagire4 Hey,there are 50 numbers in the array, so there can 250 possible subsets, that we need to consider. Of course if we are going to check each of the subsets, one by one checking if that has no co prime pairs, it will take a lot of time. We need to think of something else. When we are doing the above process, we are redoing lots of things. This is where Dynamic Programming comes into picture, to store and resuse the computed information.
Firstly, observe that there are only 15 prime numbers inside the first 50 natural numbers. Any number in the array will have only prime factors among these 15 number. This does mean we can store these as masks (or seive). Lets say we have number 6, with factors 2 and 3. Then we will set the first two bits of the mask. This means that in future, if we want to extend this set (of number 6), then we should avoid taking numbers that have factors of already set bits in this set (here the first two bits).
Okay, so here is the idea then. Firstly compute for each number in the array, the indices of the prime factors. So if number has a factor 2, we will store 1 in the list, if 5 then we will store 3, as 5 is the 3rd prime. Now lets define our DP recurrence. We will maintain a 2D array, dp[index][mask] which says, given a mask mask, what is the largest subset of co primes that can be generated from all the numbers in and after index position. So dp[index][mask] gives the answer to the question, what is the largest subset on and after index. This enalbes us to create a function rec(index, mask) whose initial call as (0, 0) {first 0 says all numbers from 0 and afterwards, second 0 says initally mask is empty} will give us the answer to the problem. There will be two options to consider, weather include the current index to the subset, or dont include it.
Dont include - Simply return rec(index + 1, mask).
Include - Firstly check if the current index is suitable to be included or not. Run a loop and check if mask is set for a position in the prime factor list we created in the beginning for this index. If there is any prime which is already in the mask, we cannot include to simply return the answer to rec(index + 1, mask). Othwerise, this is fit to be included, so tamper the mask to set all the bits for the positions which are prime factors of this number. Then returned value should be 1 + rec(index + 1, newMask). 1 indicates we included this number, and passed the newMask (setting all appropriate bits) and getting answer from rec(index + 1, newMask).
Ofcourse the answer should be the maximum of both the cases and that should be the return value of our call to rec(index, mask).
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.