Lakh's blog

Help Needed in a Range Query Problem
By Lakh, history, 7 years ago, In English

I am trying to solve http://codeforces.net/problemset/gymProblem/101102/J . The summarized form of the problem is as follows:

There are T testcases. In each testcase You are Given an array of size N and Q queries. (N,Q<=10^5).Array elements<=10^9 In each query you are given range [L,R] and a set of distinct integers lying in range [1,10]. Now for each query you have to report no. of elements in range [L,R] which are divisible by atleast one element from the set.

My approach:

I am storing a 2D prefix sum array which tells the no. of elements divisible by X(1<=X<=10) in range [L,R]. Now for a given query I am generating all subsets of elements in the set and then using inclusion-exclusion principle to find the numbers divisible by atleast 1 element from set. But getting TLE .

Please Suggest some optimization or some other approach to this problem Thanks in advance.

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +1 Vote: I do not like it

You can delete a number from the set if a divisor of that number is present in the set too.

The maximum number of the remaining numbers in the set will be at most 5 then, so I think that optimization is sufficient to make your code pass in time.

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Osama_Alkhodairy , Still getting TLE. Link to my code: http://codeforces.net/gym/101102/submission/37739183 Please have a look at it. Trying to solve this problem for last 4 days. I have generated all distinct LCMs possible for all subsets possible for 1 to 10. There are around 240 distinct values. So i Computed prefix sum for all 240 values for the given array and then deleted a number from set if it has a divisor present in the set. Then generated subsets and applied inclusion exclusion.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 2   Vote: I like it +1 Vote: I do not like it

      I can't view your code, so can you upload it on ideone or something alike?

      However, I can see only 42 LCM distinct values,

      code
      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Thanks for the help Osama_Alkhodairy. Got Accepted . I was doing a silly mistake while computing the LCM of subsets.

        → Reply