_maverick's blog

Optimisation for a subset problem
By _maverick, history, 7 years ago, In English

I faced this question among the challenges in another platform. I was unable to optimise my solution for this problem with it's constraints to pass within the time limit during the contest. The contest has ended and I feel it's time to learn.

Question :

You're given an array of size N. You need to generate all subsets for the given array. For each subset you need to OR it's minimum and the maximum element and add it to the result. You need to finally output the result after performing the mentioned operation for all it's subsets. Since the result can be large, output the result MOD by (10^9)+7.

Constraints :

1<=N<=(2*(10^5))

Let Ai be the values of the array where 1<=i<=N

1<=Ai<=1000

My Approach :

Since the problem demands to OR the minimum and maximum of each subset, I started by sorting the given array. Since the minimum element would have to appear with all the higher elements it pairs with, and the second minimum element would have to pair with all elements higher than itself and so on, sorting the array seems to be a correct approach towards the goal.

Over the sorted array I run my logic which is displayed in the below code snippet.

long MOD = 1000000007l;
long result = 0l;
for (int i=0;i<N;i++) {
    for (int j=i;j<N;j++) {
        if (i==j) {
            result = (result+array[i])%MOD;
            continue;
        }
        int OR = array[i]|array[j];
        result = (result+((OR%MOD)*(fastExponentiate(2,j-i-1)%MOD)))%MOD;
    }
}
print(result)

This looks good as an optimised brute solution running at O((N^2)*log(N)). Still not good enough to pass the time limit of 1 sec. I think the key idea lies somewhere in using the value's maximum limit of 1000 which is 10 bits for each number of the array. I tried several ideas but they were a catastrophe. I still couldn't optimise the logic. Can anyone help me if you've come across this type of problem ?

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

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

If all elements are not greater than 1000, then there are no more than 1000 different values in your array. So just compress equal values into single element and then run your quadratic solution over them.

→ Reply
»
7 years ago, # |
  Vote: I like it +4 Vote: I do not like it

By the way, you don't need to use fast exponentiation algorithm here. You can simply precalc in array all powers of two from range 0 ... n, and then get in O(1) ones that will be needed.

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

    Yeah, now the algorithm will have a nice upper bound of O(n^2) where n is the number of distinct elements present in the array and n will not exceed 1000 in the worst case owing to the constraints. Thanks a lot for that precious hint in your first comment.

    → Reply