CHNGOR - Editorial

editorial
, , ,
1

PROBLEM LINK

Practice
Contest

CONTEST PANEL

Author: Prateek Gupta
Tester: Praveen Dhinwa
Editorialist: Prateek Gupta

DIFFICULTY

Easy

PROBLEM

Given an array of length N, you need to select a subsequence from an array and remove the integers contained it. The cost incurred to remove a subsequence is the Bitwise OR of all the elements in that particular subsequence. This operation can be performed any number of times. The final goal is to minimize the total cost after the array becomes empty. Total cost is the sum of costs of all operations.

EXPLANATION

The problem can indeed be solved by simple observation.

It is first important to understand how the Bitwise OR operation actually works. A bitwise OR for two integers takes their corresponding bit patterns of equal length and performs the logical inclusive OR operation on each pair of corresponding bits. The result in each position is 0 if both bits are 0, while otherwise the result is 1.

In order to incur the minimum cost, it is necessary to select a complete array as a subsequence so that the total cost will be the Bitwise OR of all the integers in the array. But, why this will give you the minimum cost?

Consider a number that has some set bits in it’s binary representation. There may be another number in the array who might have set bits in the same position. In case, you do not take these numbers in a single operation, you will end up adding the value contributed by that common set bits twice. However, if you take them as a part of the same subsequence, you do a Bitwise OR and the value contribution for common set bit just get added up only once to the final cost.

Let us look at the pseudo code below.

ans = 0
for each integer in array
   ans = (ans OR integer)

print(ans)

Overall complexity of the solution remains O(N).

SOLUTIONS

Author’s solution can be found here.
Tester’s solution can be found here.

2 Likes
2

Another nice question. Made it look very complicated just to find the bitwise OR of elements.

Below is my implementation which became the best submission.

#include <stdio.h>
#define gc getchar_unlocked
 
int rin() { char c = gc(); while(c<'0' || c>'9') c = gc(); int ret = 0; while(c>='0' && c<='9') { ret = 10 * ret + c - 48; c = gc(); } return ret; }
int main() {
        int T, n, i, res, temp;
        T = rin();
        while(T--){
            res = 0, n = rin();
            for(i = 0;i<n;i++) temp = rin(), res |= temp;
            printf("%d\n", res);
        }
    return 0;
}

Unfortunately, I’m too slow for rapid programming. Need to work on my speed. Despite having best submissions, my rank will be bad only because of my speed.

3

" Consider a number that has some set bits in it’s binary representation. There may be another number in the array who might have set bits in the same position. In case, you do not take these numbers in a single operation, you will end up adding the value contributed by that common set bits twice. However, if you take them as a part of the same subsequence, you do a Bitwise OR and the value contribution for common set bit just get added up only once to the final cost."

Can someone explain the meaning of this with an example??

1 Like
4

@chari407 Every decimal has a binary representation. Say, we have 5 whose binary representaion is 0101. If we have another number whose some of the bits of binary representation is same as that of 5 here. Say, 21 whose binary representation is 10101. If we do not take both of these in same operation we would end up in having the cost of 21+5=26. Instead if we had both of these in same operation we would end up in having bitwise OR of these which would be the cost = 21 | 5 = 21. Hence the cost would be minimum if we OR every number in the array.

2 Likes
5

Actually, everything is up to showing that the following statement is true:

"Let X be a set of integers, then |(x_{1},x_{2},\ldots,x_{n}) \leq \sum\limits_{i=1}^{n}x_{i}".

With | as the OR operator.

It’s proof is considering the associative property of both operators, so one can just show it for two elements and it can expand to n elements:

If we can’t remember how is the simple arithmetic expression for OR, just use this (where a and b can take 0 or 1):

a\&b = ab\,(easy\,one)

Now, by D’Morgan:

a\vee b = \sim (\sim a \wedge \sim b)

Complement can be expressed as \sim a = 1 - a:

a\vee b = \sim (\sim a \wedge \sim b) = [1 - (1-a)(1-b)] = a + b - ab

.

Let’s asume A = \sum\limits_{i=1}^{n}a_{i}2^{i} and B = \sum\limits_{i=1}^{m}b_{i}2^{i} (with a_{i},b_{i}\in\{0,1\}), then the OR of both would be:

C = |(A,B) = \sum\limits_{i=1}^{max(n,m)}(a_{i}+b_{i}-a_{i}b_{i})2^{i}

Also, their sum would be

S = A + B = \sum\limits_{i=1}^{max(n,m)}(a_{i}+b_{i})2^{i}

Now, considering that a_{i},b_{i}\geq 0 , we can say that:

a_{i}b_{i} \geq 0 \rightarrow a_{i}+b_{i}-a_{i}b_{i} \leq a_{i}+b_{i}

So, with all the above, we now can agree that

|(A,B) \leq A+B

For any other quantity of numbers, we just can do something like

|(A,B,C) = |(|(A,B),C) \leq |(A,B)+C \leq (A+B)+C = A+B+C

If I made any mistake please let me know (Y).

6

@sun_d can you explain how your code works?

7

can someone please give me two more examples!
2
1 2 this would result in 3.
just two more examples like this one!

8

Here is the python implementation for this in O(n) time

@sun_d
for _ in range(int(input())):
s = int(input())
l = list(map(int,input().split()))
total = 0
for i in range(len(l)):
total |= l[i]
print(total)

9

@bhushan_ Thanks for the reply. Can you please present a manual run of this over a set of, say, 6 numbers? Thank you.

10

like if you have 1010 and 10 … if you take them in one operation … you will incur cost only 1010 … so basically statement means if you choose 1010 … you would want to choose 1000 , 10 , 1010 in one operation as 1010 consumes cost of all others … ie all other which have set bits only at positions where 1010 already have it

11

Thanks :grinning: :v: :heart: