Binary Calculation (BINCAL) - Editorial

editorial
, ,
1

Binary Calculation (BINCAL)

Problem link -LINK
Author- Aagam Jain
Tester - Aagam Jain

Difficulty : Easy - Medium
Problem Tag : Bit Manipulatioin

Problem :
To maximize the value of ∑Ai^2, you can perform only :

  • Choose two distinct indices 0 ≤ i,j ≤ n−1,
    and put Ai = Ai AND Aj and also put Aj=Ai OR Aj
    where AND & OR are bitwise AND & OR respectively.

Explanation :

This is the problem of BitMasking and in this question we have to find maximum value of ∑Ai^2.

In the given operation if we observe that max(Ai , Aj) ≤ Ai OR Aj and Ai AND Aj ≤ min(Ai , Aj) . By observation we can find that Ai + Aj = ( Ai OR Aj ) + ( Ai AND Aj ).

Let Assume Ai =10 (1010) , Aj = 12 (1100).
Ai OR Aj = 1110 =14
Ai AND Aj = 1000 = 8
and 10 + 12 =14 + 8 = 22

By our observations we find that instead of working brute force and find max value of Ai , lets work on the bits of individual elements of the given array.

Let assume an array {8 , 16 , 10 , 6 , 3 , 13 , 18 , 9}
Initialize a bit array of size 5 {0 , 0 , 0 , 0 , 0}
One by One store bits of a number in this array, on the repective positions
which are -1 , 2 , 4 ,8 ,16
08 = 01000 → {0 , 0 , 0 ,1 , 0}
16 = 10000 → {0 , 0 , 0 ,1 , 1}
10 = 01010 → {0 , 1 , 0 , 2 , 1}
06 = 00110 → {0 , 2 , 1 , 2 , 1}
03 = 00011 → {1 , 3 , 1 , 2 , 1 }
13 = 01101 → {2 , 3 , 2 , 3 , 1}
18 = 10010 → {2 , 4 , 2 , 3 , 2}
09 = 01001 → {3 , 4 , 2 , 4 , 2}

By using this we simply calculate on 2^0 , 2^1 , 2^2 , 2^3 , 2^4 how many ones are there, here we have 3 , 4 , 2 , 4 , 2 ones respectively.

Now find max combinations occur by these ones and get an array.
{3 , 4 , 2 , 4 , 2} → 31 → {2 , 3 , 1, 3 , 1}
{2 , 3 , 1, 3 , 1} → 31 → {1 , 2 , 0 , 2 , 0}
{1 , 2 , 0 , 2 , 0} → 11 → {0 , 1 , 0 , 1 , 0}
{0 , 1 , 0 , 1 , 0} → 10 → {0 , 0 , 0 , 0 , 0}
{0 , 0 , 0 , 0 , 0} → 00 → {0 , 0 , 0 , 0 , 0}

The maximize value in array we get = {31 , 31 , 11 ,10 , 0 , 0 , 0 , 0}

∑Ai^2 = 961 + 961 +121 + 100 + 0 + 0 + 0 + 0 = 2143

My Solution :
LINK

1 Like