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} \).

Codeforces 444A - DZY Loves Physics

Problem Statement:
444A - DZY Loves Physics

Solution:
This problem is pretty cool mathematically, learnt new stuff :)

We claim that there is always an optimal induced subgraph containing only 2 vertices (or in other words, we can find an optimal induced subgraph amongst all the edges in G(V,E) ). If this is true, then to solve this problem, we just need to find the edge in G with the maximum density, which can be done in \(O(m)\) time. So why is this claim true? Here's a proof which I learnt from the official editorial, which I will write here for my future references. But feel free to read them through :)