Codeforces 442B - Andrey and Problem

Problem Statement:
442B - Andrey and Problem

Solution:
An interesting mathematical problem. The official editorial to this problem is excellent, so this post is more for my self reference.

First of all find a neat representation of the function we are going to optimize:
Let \(K = \{ p_1, p_2, \ldots, p_k \} \) be the probabilities of friends chosen, then the probability of having one problem is:
\(F = p_1(1-p_2)(1-p_3)\ldots (1-p_k) + (1-p_1)p_2(1-p_3)\ldots (1-p_k) + \ldots \)
       \(+ (1-p_1)(1-p_2)(1-p_3)\ldots p_k\),
which can be simplified as
\(F = (1-p_1)(1-p_2)\ldots (1-p_k) \{ \sum_{i=1}^{k} \frac{p_i}{1-p_i}  \} \)
Let \(P = (1-p_1)(1-p_2)\ldots (1-p_k)\) and \(S =  \sum_{i=1}^{k} \frac{p_i}{1-p_i} \).



Now suppose that we are going to add one person into the group, what is the condition such that this addition will increase the probability? Suppose the probability of that person be p. So here we have
\(F' = P(1-p)(S+\frac{p}{1-p})\), hence
\(D = F - F' = PS - P(1-p)(S+\frac{p}{1-p})\).
\(D = Pp(S-1)\)
This means that for D < 0 (i.e. F is less than F'), we need S < 1. This forms a rule for us to decide whether to add another person to the set K of currently chosen friends.

Now if S < 1, which friend should we add? Here suppose we have two choice between p and q, where \(q < p\). Then we have
\(P(1-p)(S+\frac{p}{1-p}) - P(1-q)(S+\frac{q}{1-q}) = P(p-q)(1-S) > 0\)
which means that we should always choose the friend with bigger probability to add!

How do we know that the final set K build this way will be optimal? i.e. is there K' such that their elements are not all the same as K, but has higher probability than K? Let's assume that there is. Then since K contains all the biggest elements, there must be at least one \(p \in K\) and one \(q \in K'\) such that \(p > q\) (where p is not in K' and q is not in K). Since \(K'\) is optimal, removing q from K' to form R = K' - {q} will lead to S(R) < 1, since otherwise addition of q to R that set won't be optimal in the first place. Now we are back to the case where S(R) < 1 and we have two choices p or q to add to R. So we know adding p will be more optimal that adding q, hence naturally we will choose p. However this means that we found another more optimal set than K', which contradicts the assumption that K' is optimal. Hence K must be optimal in the first place.

A very good greedy algorithm problem indeed.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
double p[103];
double EPS = 1e-30;
int N;
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;++i){
        scanf("%lf",&p[i]);
    }
    sort(p,p+N);
    double ans = 0;
    double sum = 0;
    double prob = 1;
    if(fabs(p[N-1]-1.0)<EPS) {printf("%.12lf\n",p[N-1]);return 0;}
    for(int i=N-1;i>=0;--i){
        sum += p[i] / (1.0 - p[i]);
        prob *= (1-p[i]);
        ans = max(ans,sum*prob);
        if(sum > 1.0) break;
    }
    printf("%.12lf\n",ans);
    return 0;
}