Barclyas HackerEarth Challenge

help
1

You are given an integer N You need to calculate the Bitwise-OR sum of all ordered pairs (i,j):(1≤i,j≤N) . Print the value of sum modulo 10^9+7 (the remainder when sum is divided by 10^9+7

Example Case:
Input: 2
Output :(1|1 + 1|2 + 2|1 + 2|2 ) modulo (10^9+7) = 9.

Could Someone Suggest an efficient approach

Please Find Below My code.

using namespace std;
const unsigned long long int MOD = 1000000007;

unsigned long long int pairAndSum(vector &vect, unsigned long long int n)
{
unsigned long long int ans = 0;
for (unsigned long long int i = 0; i < 32; i++)
{
unsigned long long int k = 0;
for (unsigned long long int j = 0; j < n; j++)
if ( !(vect[j] & (1 << i)) )
k++;
ans +=(((1<<i)%MOD) ((n(n-1)/2)%MOD - (k*(k-1)/2)%MOD))%MOD;
}
return ans;
}
int main()
{
unsigned long long int n,i; cin>>n;
unsigned long long int arr[n];
vector vec(n);
for(i=0;i<n;i++)
vec[i]=i+1;

cout << (((2%MOD)*(pairAndSum(vec, n)%MOD))+(n*(n+1)/2)%MOD)%MOD << endl; 
return 0;

}

This could fetch a partial of 60/100 points , Other test cases gave WA

The Challenge is now over

1 Like
2

When did the challenge ended?
I think someone asked in the midst of the contest. Anyways you can have a look at the soln here

1 Like
3

I will tell you what I did . I basically calculated for each bit , in how many numbers the bit is set and in how many numbers bit is unset

for ex ,for each bit
x = number of numbers in which bit is set
y = number of number in which bit is not set

then that bit will be set in following pairs ( OR of this numbers )

  1. Each of x numbers when taken in OR with (1…n) = xn bits
    2.Each of y numbers taken in OR with x numbers = x    y bits

In this way perform bit addition from LSB to MSB

For reference my code

3 Likes
4

hey @ashforever007 can you please explain your approach more clearly by some sort of an example thanks and please do share the solution for problem 2 “count all” if possible.

5

ll ans = n*(n+1)/2%M;

ll dp[32];
memset(dp, 0, sizeof(dp));
for (ll i = 1; i <= n; i++)
{
ll ci=i;
for (ll j = 0; j < 32; j++) {

  if (ci&1)
  { 
    ans += 2 * (1 << j) * (i - 1);
    dp[j] += 1;
  }
  else

  {
    ans += 2 * (1 << j) * dp[j];
  }
  ci>>=1;
  ans%=M;
}

}

3 Likes
6

Yes i realized someone asked it when the challenge was live. Such practices are unfair to other participants , anyways thank you for the link.

1 Like
7

Use the concept of divisor sieve.

Divisor Sieve

1 Like
8

thanks for sharing @avi141 i haven’t heard about this concept of divisor sieve thanks a lot.

1 Like
9

and also if possible do share some resource for tackling the problems like hard sum of barclays if possible.

1 Like
10

Pure Brilliancy,Sir.

11

Check this editorial and problem on codechef.
They have very similar solutions :).
Seems like author just replaced AND with OR and removed i<j.

A brief summary is as follows.
Break the problem into a subproblem where given a binary array find sum of bitwise OR of it.
Once you solve that subproblem it won’t be hard for you to realize that answer is \sum_{i=0}^{31} ans(i)*2^i \mod m where m=10^9+7. (If constraints have 32 bits in number)
Hint for solving that subproblem :
Count number of “1” and number of “0”.
ans(i)= Count of OR_1 = total - count of OR_0 = (n*n) - (cnt_0*cnt_0) \mod m

1 Like
12

@gagangaur @avi this Divisor Sieve is very efficient and useful as this is also used in one another solution which is asked by rk_221b in this → Count all special element question (Help).

But how this divisor sieve is used here. I think instead of using divisor sieve e can use the concept of set bits as we know here a number is represented by 32 bits and the property of OR is to set the i’th bit , and count all the possible pairs , i will code and if works then definitely i will share :slight_smile:

13

Is this a sarcastic reply ?

14

Nope,I am new to bits-manipulation and this helped me a lot :slight_smile: Thanks :slight_smile:

15

understand the logic behind it then think how it can be modified for OR

1 Like
16

Any more similar problems you have ? :slight_smile:

17

@ssrivastava990 try your best bro and do let us know that your approach worked or not.

18

@gagangaur @anon55659401 @ganesh92 @avi141
Here u go–
// An efficient C++ program to compute sum of bitwise OR

// of all pairs

#include <bits/stdc++.h>

using namespace std;

// Returns value of "arr[0] | arr[1] + arr[0] | arr[2] +

// ... arr[i] | arr[j] + ..... arr[n-2] | arr[n-1]"

int pairORSum( int arr[], int n)

{

int ans = 0; // Initialize result

// Traverse over all bits

for ( int i = 0; i < 32; i++)

{

// Count number of elements with i'th bit set

int k1 = 0; // Initialize the count

// Count number of elements with i’th bit not-set(ie., 0) `

int k0 = 0; // Initialize the count

for ( int j = 0; j < n; j++){

if ( (arr[j] & (1 << i)) )

`k1++;

else

k0++;


}
// There are k1 set bits, means k1(k1-1)/2 pairs. k1C2
// There are k0 not-set bits, so total pairs will be k1*k0.

// Every pair adds 2^i to the answer. Therefore,

ans = ans + (1<<i) * (k1*(k1-1)/2) +(1<<i)*(k1*k0) ;
ans %=MOD;

}

return ans;

}

// Driver program to test above function

int main()

{

int arr[] = {1,2,3,4,5};

int n = sizeof (arr) / sizeof (arr[0]);

cout << pairORSum(arr, n) << endl;

return 0;

}

If any error in this programme or further explaination required then i will explain in best way :slight_smile:

19

brilliant work bro @ssrivastava990 you have simplified the solution a lot to understand easily appreciated.
but i am still struggling with these three lines :sweat_smile: hope if you can simplify that too :sweat_smile: so that one can easily grasp this concept via some sort of an example if possible thanks. :slightly_smiling_face:

20

Seems incorrect… you did the same mistake I did in solution just above you…
There will be k1*k1 + 2*k1*k0 pairs
Or n*n - k0*k0