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 :)



We want to prove this: For any induced subgraph G' containing more than 2 vertices, we can always find an edge in G'(V', E') which has density bigger or at least equal to the density of G', denoted as \(D(G')\). We want to prove this because if this is true, we can conclude that any subgraph G' more than 2 vertices is not more optimal than the maximum density edge in G', which is exactly what our very first claim is saying. Proof? By contradiction: Suppose that for all \((u,v) \in E' \), we have \(\frac{u+v}{w(u,v)} < D(G')\) and therefore \(u+v < w(u,v)D(G')\). If we sum up all the inequalities for all (u,v), we have \(\sum_{u \in G'} u + \sum_{v \in G'} v < \sum_{(u,v) \in G'} w(u,v) D(G')\), hence \( \frac{ \sum_{u \in G'} u + \sum_{v \in G'} v } { \sum_{(u,v) \in G'} w(u,v) } < D(G') \). However, we also have that \(D(G') = \frac{\sum_{u \in G'} u}{\sum_{(u,v) \in G'} w(u,v)} \leq  \frac{ \sum_{u \in G'} u + \sum_{v \in G'} v } { \sum_{(u,v) \in G'} w(u,v) } \), hence a contradiction. Therefore we conclude that there are (u,v) in G' that has density at least equal to or more than D(G'). :D