ACM16CHN - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practise

Contest

Problem Setter : Satyaki Upadhyay

Tester :

Editorialist : Manas Kumar Verma

DIFFICULTY:

MEDIUM

PREREQUISITE:

Convex Hull

PROBLEM:

Given cost, salt and sugar content of N wine (N=10^5) , we need to find minimum money we need to be able to manufacture all N wines. Either we can buy any of given wines or we can obtain a new wine whose salt and sugar content is convex combination of some wines we have bought.

QUICK EXPLANATION:

As soon as we realize that rule for creating a new wine is nothing but convex combination, it becomes obvious that the problem is asking us to compute convex hull of points that can be marked as (X,Y)=(sugar,salt) and sum of costs associated with them is our answer.

EXPLANATION:

We first start by analyzing mathematical rule given for creating a new wine by combining some wines since it leads us to crux that gives us idea to solve this problem geometrically.

Formally, if t wines are combined in ratio x_1:x_2:x_3:...:x_t with i^{th} wine having s_i micrograms of sugar then mixture contains say sugar equal to M_{sugar}=(s_1*x_1+s_2*x_2+...+s_t*x_t)/(x_1+x_2+...+x_t). Similarly salt content of mixture can be computed.

Let \alpha_i=\dfrac{x_i}{x_1+x_2+...+x_t)}. So we can re-write M_{sugar}=\sum\limits_{i=1}^t \alpha_i * s_i and since clearly \sum\limits_{i=1}^t \alpha_i = 1 , our mixture rule is simply convex combination of Sugar (/Salt) content and the ratios in which wines are combined. This observation invites us to re-look problem from geometric point of view. We mark each given wine as a point in 2D plane as (X,Y)=(sugar,salt). It is very intuitive that any point inside simple convex-polygon can be represented as convex combination of vertices of polygons. Infact, this is one of the most introductory application of geometry in Linear Programming and a standard trick used in competitive programming. We will prove this fact formally.

There are several proofs : proof by induction, proof by construction, proof by triangulation. Each of them will require the following base case.

Claim : If A=\alpha_1*B_1+\alpha_2*B_2 then A lies on line segment \overline{B_1B_2} , \forall A,B_1,B_2 \in \mathbb{R}^2 and \alpha_1+\alpha_2=1.

Proof : Substituting \alpha_2=1-\alpha_1 in equation of A we get A=\alpha_1*B_1+(1-\alpha_1)*B_2. This is simply parametric form of line-segment between \overline{B_1B_2} by comparing it to A=t*B_1+(1-t)*B_2, t \in [0,1]. Limits for our case can be verified as \alpha_1+\alpha_2=1 and \alpha_1,\alpha_2 being ratios \alpha_1,\alpha_2>=0 so 0<=\alpha_1,\alpha_2<=1. Hence proved.

After proving the base case, we will complete proof by construction. Let polygon P\equiv\{P_1,P_2,...,P_t\} be simple convex polygon whose vertices belong to convex hull formed on given N points constructed as (X,Y)=(Sugar,Salt). We can create any point say Q lying on boundary of polygon P since any point on boundary will lie on some line segment \overline{P_iP_{(i+1)\%t}} and thus we can create point Q by convex combination of P_i,P_{(i+1)\%t}. After this, it is easy to show that any point say W lying inside the polygon P can also be created. Take any arbitrary vertex of polygon say P_i and draw ray \overrightarrow{P_iW}. It will cut polygon P at exactly one point say W', as polygon is simple and convex. W' can be created by convex combination of some P_i,P_{(i+1)\%t} as we have shown. Now W lies on line segment \overline{P_iW'} and thus can be formed by their convex combination.

Thus we have proved that any point inside polygon can be created using vertices of the polygon. Next we prove that convex combination of some two points inside polygon can never create vertex of polygon. It seems pretty obvious ,if not one can think of convex combination in terms of weighted means (infact whole of problem or solution can be remodelled as Weighted Mean and all proofs used for it can be applied here). However obvious it might look, our formal proof is incomplete till we prove it.

Claim : Any vertex of polygon cannot be created by convex combination of two points inside polygon.

Proof : We will prove it by proof of contradiction. On contrary , lets assume a vertex P_i can be formed by convex combination of two points A,B lying inside Polygon. By defination , P_i=\alpha_1*A+\alpha_2*B , \alpha_1+\alpha_2=1. Without loss of generality, let A be closer to P_i than B. So A=\alpha_3*P_i+\alpha_4*B, \alpha_3+\alpha_4=1. By substituion we get , P_i=\alpha_1*\alpha_3*P_i+\alpha_1*(1-\alpha_3)*B+(1-\alpha_1)*B. By rearranging and cancelling we get P_i=B but our initinal assumption was P_i was a vertex of polygon and B was point inside polygon and thus they cannot be same. Hence our claim is proved by contradiction.

Implementations: