Hey Everyone,
I have been trying to solve this problem from CodeChef: Practical coding for everyone but I am not able to understand the motto of the problem.
Help would be appreciated.
well if you donβt understand the motto of the problem you can refer the editorial and just read the problem description and don"t read the solution
However, Here is mine explanation
the question is asking you to compute the total beauty of the paintings you select in order to maximize the beauty of the exhibition that is you have to use only those paintings in xor calculation which can maximize the xor value i.e. the total beauty of the exhibition
for instance suppose that there are 5 paintings such as
painting beauty probability
paint_1 b1 p1
paint_2 b2 p2
paint_3 b3 p3
paint_4 b4 p4
paint_5 b5 p5
and suppose you opt paint_1 , paint_3, and paint_4 then
total beauty = b1p1 + b3p3 + b4*p4
now print this total beauty to 6 digits after the decimal and this is your required answer.
Remember that every painting you select is probably selected , not all are selected so calculate the sum with the probability i.e. calculate the total probability .
Example case 1: The first painting must be displayed at the exhibition, the second one must be excluded. If the third painting is displayed (with probability 0.50.5), the beauty is 5β2=75β2=7; if it is excluded (with probability 0.50.5), the beauty is 55. The expected beauty is 0.5β 5+0.5β 7=60.5β 5+0.5β 7=6.
this is the example given in the problem, I donβt understand the part 0.5β
5+0.5β
7=60.5β
5+0.5β
7=6
why 5 and 7 (which are xor ) is getting multiplied with 0.5.
sorry , shivank i just made a little mistake in my above explanation which is actually big:stuck_out_tongue_closed_eyes:
see its just asking the total beauty
now if you know that a painting you are selecting is with beauty βBβ and probability βPβ then you know there still chances that the painting may not be selected which is equal to β1-Pβ by the law of probability hence you need to multiply the beauty with the probability in order to get the total beauty. i.e βP*Bβ. its just a little math you have to consider
read the total probability rule or check this link for the same however i recommend NCERT
TOTAL PROBABILITY RULE.
i have corrected the above explanation