May cook off 2019(Expected Xor)

1

I am not able to get it where to use probability as it was given in question you need to find the expected Xor in the final answer of the subset.
suppose input is
n=3
b value- 4 5 8
probabilty- 0.2 0.3 0.4

Now we need to choose subset so there will be 2^n-1.
here 4 ,5 ,8 , 4 5 , 5 8 , 4 8 , 4 5 8.Now we need to xor of all the b value present in subset.But where to use probability i didn’t get this . Great help if you explain me with an example .
problem link - CodeChef: Practical coding for everyone
Thankyou.

2

For the subset 4 8,

XOR value (x) will be = 4 ⊕ 8 = 12.

The probability that this subset will be chosen is = f(x) = (probability of choosing 4) * (probability of not choosing 5) * (probability of choosing 8) = 0.2 * (1 - 0.3) * 0.4 = 0.056.

Find the XOR value and probability of occurring for each subset and use the given formula to calculate expected value.

Expected xor = ∑ x.f(x) for all the possible subsets.

This is a Brute Force Approach with exponential time complexity and should not be used. Please use Dynamic Programming approach as given in the Editorial.