EXPXOR - EDITORIAL

PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Setter: Pritom Kundu

Tester: Teja Vardhan Reddy

Editorialist: Teja Vardhan Reddy

DIFFICULTY:

Easy Medium

PREREQUISITES:

Linearity of expectation, Probability

PROBLEM:

Given n numbers (b_1,b_2,....b_n) and probabilities of choosing each of the numbers. Find the expected xor value of the chosen set.

EXPLANATION

Let X be the random variable representing xor of chosen set. And x_i be random variable representing i th bit in xor of chosen set.

X = \sum_{i=0}^{30} 2^i * x_i

Now E[X] = E[\sum_{i=0}^{30} 2^i * x_i]

E[X] = \sum_{i=0}^{30} E[ 2^i * x_i] (By linearity of expectation).

E[X] = \sum_{i=0}^{30} 2^i * E[x_i]

We are only considering first 30 bits (infact log_2(max_{i=1}^n b_i) \lt 30 from given constraints) because for all other values of i, each of the n inputs always takes a value zero for that bit, hence that bit of xor of chosen set will be always zero.

Now, let us focus on how to calculate E[x_i].
Let us iterate numbers from 1 to n and consider whether they join the set or not (Assume j th number joins set with probability p_j).

Initially before we start, P_0[x_i = 0] = 1.

Now for j th number,

Case 1: i th bit is zero.
Irrespective of we take it into the set or not, it wont affect x_i.

Case 2: i th is one.
Now, we consider both cases that j th number is in set and not in the set and compute the probability.

P_j[x_i = 0] = P_{j-1}[x_i = 0]*(1-p_j) + P_{j-1}[x_i = 1]*(p_j)

P_j[x_i = 1] = 1 - P_j[x_i = 0] (since x_i must be either zero or one)

And finally E[x_i] = P_n[x_i = 1]

So now, we can compute E[X] from above derived formula after we know E[x_i].

TIME COMPLEXITY

To compute E[x_i] for each i, we need O(n) time.

Hence, total time needed to compute E[x_i] for all i is O(n* log_2(max_{i=1}^n b_i)).

Now to find E[X] given all values of E[x_i] takes O(log_2(max_{i=1}^n b_i)) time.

Hence total time complexity is O(n* log2(max_{i=1}^n b_i)).

SOLUTIONS:

Setter's Solution
#include<bits/stdc++.h>
#define LL long long
#define pb push_back
using namespace std;
 
const int N = 1e5 + 7;
const int K = 30;
int a[N];
double p[N];
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int t;
    cin>>t;
    
    while (t--) {
        int n;
        cin>>n;
    
        for (int i=1; i<=n; i++)    cin>>a[i];
        for (int i=1; i<=n; i++)    cin>>p[i];
    
        double ans = 0;
    
        for (int i=0; i<K; i++)
        {
            double prob = 0;
            for (int j=1; j<=n; j++)
                if (a[j] & (1<<i))
                    prob = prob * (1-p[j]) + (1-prob) * p[j];
    
            ans += prob * (1<<i);
        }
        cout<<setprecision(15)<<fixed<<ans<<"\n";
    }
}
Tester's Solution
//teja349
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
//setbase - cout << setbase (16); cout << 100 << endl; Prints 64
//setfill -   cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x)  cout<<fixed<<val;  // prints x digits after decimal in val
 
using namespace std;
using namespace __gnu_pbds;
 
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define flush fflush(stdout) 
#define primeDEN 727999983
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
// find_by_order()  // order_of_key
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
 
int a[123456];
long double p[123456];
int main(){
    std::ios::sync_with_stdio(false); cin.tie(NULL);
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        int i,j;
        rep(i,n){
            cin>>a[i];
        }
        rep(i,n){
            cin>>p[i];
        }
        long double zer,one,ans=0;
        rep(j,30){
            zer=1.0;
            one=0.0;
            rep(i,n){
                if(a[i]&(1<<j)){
                    zer=zer*(1-p[i])+one*p[i];
                    one=1-zer;
                }
            }
            ans+=one*(1<<j);    
        }
        cout<<setprecision(35)<<ans<<endl;
        
    }
 
    return 0;   
}

Feel free to Share your approach, If it differs. Suggestions are always welcomed. :slight_smile:

5 Likes

Can you clarify more this approach?

Let the probability of having ith bit 1 in XOR be
P(i)
Now, ans is \sum_{i=0}^{29} P(i)*2^i
Now a subproblem is given n probabilities and a binary array… Find expected value of Xor…
When value of array is 0 it doesn’t contribute anything… so consider all probabilities when array value is 1
Now Xor can be either 1 or 0
So use DP for finding P(Xor=1) which will be nothing but P(i)
And just repeat the process for each bit position

Hint for DP :
DP will be 2*n matrix… Where first row denotes probability of having Xor 1 and 2nd row denotes probability of having Xor 0…
dp[0][0]=val[0]
dp[0][1]=1-val[0]

Now dp[i][0]=dp[i-1][1]*(1-val[i]) + dp[i-1][0]*val[i]
Meaning current value will be 1 if previous Xor value was 0 and current value is 1
Or previous value was 1 and current value is 0
Then dp[i][1]=1-dp[i][0]

8 Likes

Thankyou for this explanation.

1 Like

Can anyone give me similar problems of Expectation for practice. It would be of great help for me. Also, if possible, problems including bits. I can’t able to understand x&(1<<j) this operation.Thanks.

a[j]&(1<<i) checks if the ith bit is 1 in a[j] or not. a[j] is the jth number of the array. If this expression returns a non-zero value, then that bit is set.

Credits: @aryanc403

Can you suggest what are the topics which should be read to solve probability based problems in a contest?

please someone tell me how finding the probability of each bit to be 1 in xor giving us the final expected xor value?

2 Likes

To give a non-zero contribution to final answer, the value of xor of all numbers’ i’th bit should be one. Since there are only two possibilities (1 or 0) for i’th bit of every number, to return 1 as xor there must be odd number of 1’s. So the problem reduces to finding the probability of taking an odd number of 1’s from all i’th bits of the number, which can be done by simple O(n) process.

1 Like

so can i say that instead of finding xor value and probability of that xor value for every subset , we are finding the probability of xor values to become 1,2,4,8,16… and using them to finding expected probability?

Yes, considering that you’re multiplying each of the 1,2,4,8,16 individually by respective probabilities.

Thank you l_returns, that was probably the best anyone can explain this problem!

2 Likes

Thanks @buzz_95

1 Like