finding intersections in a given range ?
assume array of N (N<=100000) elements a1, a2, .... ,an, and you are given range in it L, R where 1<=L<=R<=N, you are required to get number of values in the given range which are divisible by at least one number from a set S which is given also, this set can be any subset of {1,2,....,10}. a fast way must be used because it may ask you for more than one range and more than one S (many queries Q, Q<=100000), so looping on the values each time will be very slow.
i thought of storing numbers of values divisible by each number in the big set {1,2,....,10} in 10 arrays of N elements each, and do cumulative sum to get the number of values divisible by any specific number in any range in O(1) time, for example if it requires to get number of values divisible by at least one of the following: 2,3,5, then i add the numbers of values divisible by each of them and then remove the intersections, but i didn't properly figure out how to calculate the intersections without 2^10 or 2^9 calculations each time which will be also very slow (and possibly hugely memory consuming) because it may be done 100000 times, any ideas ?
i thought of storing numbers of values divisible by each number in the big set {1,2,....,10} in 10 arrays of N elements each, and do cumulative sum to get the number of values divisible by any specific number in any range in O(1) time, for example if it requires to get number of values divisible by at least one of the following: 2,3,5, then i add the numbers of values divisible by each of them and then remove the intersections, but i didn't properly figure out how to calculate the intersections without 2^10 or 2^9 calculations each time which will be also very slow (and possibly hugely memory consuming) because it may be done 100000 times, any ideas ?
To show how to solve this, I'm going to start with a simpler case. To start, let's call that original array of N numbers A. Suppose you only needed to find the number of values in [L,R] that are divisible by 2. In other words, the set S is always {2}. To compute this, create a new array X. X[n] contains the number of values from A[0]-A[n] that are divisible by 2. Computing X is easy. Just go up through the A values. If A[i] is divisible by 2 then X[i]=X[i-1]+1, otherwise X[i]=X[i-1].
Once you have X then it's trivial to answer "how many numbers in A[L..R] are divisible by 2." The answer is X[R]-X[L].
But how to extend this to an arbitrary subset S? Certainly you should only compute the factors of A once. So maybe make an array Factors of N bitset<11> where Factors[i][j] means that A[i] is divisible by j. With this, you can quickly set X to be the number of items A[1..i] that are divisible by at least one number in S.
But you don't want to compute the whole range of X each time S changes. Maybe there are 100,000 queries and each one uses a different S. You could compute a shorter range of X each time, so when you're given L,R, check to make sure you've already computed X values up to R and add the new values if needed. But that might still be slow. I'm stuck on making this part fast and it feels like there should be a way to precompute almost everything you need.
Perhaps someone else has a good idea.
Once you have X then it's trivial to answer "how many numbers in A[L..R] are divisible by 2." The answer is X[R]-X[L].
But how to extend this to an arbitrary subset S? Certainly you should only compute the factors of A once. So maybe make an array Factors of N bitset<11> where Factors[i][j] means that A[i] is divisible by j. With this, you can quickly set X to be the number of items A[1..i] that are divisible by at least one number in S.
But you don't want to compute the whole range of X each time S changes. Maybe there are 100,000 queries and each one uses a different S. You could compute a shorter range of X each time, so when you're given L,R, check to make sure you've already computed X values up to R and add the new values if needed. But that might still be slow. I'm stuck on making this part fast and it feels like there should be a way to precompute almost everything you need.
Perhaps someone else has a good idea.
let's say that f(a) gives you how many numbers in the range are divisible by `a'
if you want to know `f(a or b)' you need to do `f(a) + f(b) - f( LCM(a,b) )'
then, to add `c': `f(a or b or c) = f(a or b) + f(c) - f(LCM(a,c)) - f(LCM(b,c)) + f(LCM(a,b,c))'
add more elements in a similar way. Sum `f(x)', subtract the pair combinations, sum the combinations with three elements, subtract with four...
So you need to store not only `f(a)' for all the elements in S, you also need `f( LCM(a,b,...,z) )' for any combination of them.
S has the numbers from 1 to 10, so you need to store 4*3*2*2 = 48 combinations.
> but i didn't properly figure out how to calculate the intersections without 2^10 or 2^9 calculations each time
suppose that `b' is divisible by `a', then `LCM(a,b) = b'
f(a or b) = f(a) + f(b) - f(b) = f(a)
that means that `b' is irrelevant and may be left out.
In conclusion, you may reduce the size of S. It will not have more that 5 elements.
if you want to know `f(a or b)' you need to do `f(a) + f(b) - f( LCM(a,b) )'
then, to add `c': `f(a or b or c) = f(a or b) + f(c) - f(LCM(a,c)) - f(LCM(b,c)) + f(LCM(a,b,c))'
add more elements in a similar way. Sum `f(x)', subtract the pair combinations, sum the combinations with three elements, subtract with four...
So you need to store not only `f(a)' for all the elements in S, you also need `f( LCM(a,b,...,z) )' for any combination of them.
S has the numbers from 1 to 10, so you need to store 4*3*2*2 = 48 combinations.
> but i didn't properly figure out how to calculate the intersections without 2^10 or 2^9 calculations each time
suppose that `b' is divisible by `a', then `LCM(a,b) = b'
f(a or b) = f(a) + f(b) - f(b) = f(a)
that means that `b' is irrelevant and may be left out.
In conclusion, you may reduce the size of S. It will not have more that 5 elements.
Topic archived. No new replies allowed.