Please suggest an approach for solving this question : https://www.codechef.com/DODE2018/problems/GOD .
1 Like
Solution outline:
So this problem can be reduced to, for given x,y,z where x,y belong to [0,1] and z belongs to [a1,a2] finding the probability such that sum of squares of any two amongst x,y,z is lesser than the square of the third side. So the possibilities are x^2+y^2<z^2, y^2+z^2<x^2 and z^2+x^2<y^2.This is a geometric probability question. As x,y,z are independent of each other we can treat x,y,z as the sides of a unit cube with a vertex at origin of co-ordinate system. Now the three above conditions would be internal volume of 3 quarter cones whose axes are perpendicular to each other and whose vertices are at the origin. But as z is constrained between a1 and a2 the cones and even the cube would be sliced so that the probability would become the ratio of sum of volumes of sliced cones to that of the volume of cuboid formed after slicing the cube along z from a1 to a2. The volume of cuboid formed after slicing would be (a2-a1)11 which is (a2-a1). The volumes of sliced cones can be found by integration. Let the volumes of sliced cones be V1,V2 and V3 after finding through integration. Refer to these links for methods of integration http://www.mathwords.com/f/frustum.htm and
https://math.stackexchange.com/questions/1660071/how-to-calculate-volume-of-a-right-circular-cones-hyperbola-segment?rq=1.
So the required probability would be (V1+V2+V3)/(a2-a1) which would be
(
1 Like
Thanks . Can you please tell me the final expression as well ?