PROBLEM LINK:
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. 