July 18- Problem Discussion

See it is a multi-step process. When you start solving a problem, generally you can’t think of the best way in just one look. First you think of a simple way which can solve the problem mostly that is Brute Force and then as per the constraints you modify your approach. Some times it is possible and some times it isn’t and you have to think of another approach.

In this ques- For the first try I used 2D arrays of n * n and also my complexity was of order n^2 and thus it didn’t give complete AC soln.

This is the beauty of Competitive Programming, many a times the answer is simple but to reach the answer within the constraints is what requires thinking.

@ritam777 : Actually that isn’t an assumption

The observation in step 2 is that only one of the vector can have side
greater than k/2

Let’s call p(i) as probability of loosing if we give ith vector a magnitude
greater than k/2

All I am saying is due to symmetry, p(1) = p(2) = … = p(n)

Thus we can compute p(1) (which I have done above) and the probability of winning will thus be [ 1 - n * p(1) ]

1 Like

Can you please explain your function-

bool bad(int a,int b,int c) {
  // use deterministic comuputation with long long if sufficient
  return (long double)(B[c]-B[a])*(M[a]-M[b])<(long double)(B[b]-B[a])*(M[a]-M[c]);
}