## 802 - Lead or Gold

Moderator: Board moderators

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

### Re: 802 - Lead or Gold

Oh, now I see. I knew that trick, I just forgot its name.

But I think its use is totally unnecessary here. In fact, you don't even have to add any artificial variables. Here's LP formulation that I've used in my simplex solution:

Code: Select all

minimize (A+B+C) - \sum_{i=1}^n (a[i] + b[i] + c[i]) x[i]
subject to
\sum_{i=1}^n a[i] x[i] <= A
\sum_{i=1}^n b[i] x[i] <= B
\sum_{i=1}^n c[i] x[i] <= C
x[i] >= 0
That is, I just turn strict equalities into inequalities and try to minimize the sum of residuals, starting from zero basic feasible solution. The original problem is feasible if that sum reaches zero.

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

### Re: 802 - Lead or Gold

Also I noticed that in CLR -- without Stein -- they give no description of simplex algo.
I guess you have an English version of CLRS that you brought from one of your innumerable
trips around the world
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

### Re: 802 - Lead or Gold

Yes, they've added a chapter on linear programming only in 2nd edition of the book.

By the way, the book's third edition is coming this fall!

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

### Re: 802 - Lead or Gold

I got AC with your LP formulation, as well. Of course, your approach is neat:
your just sum the residuals and change the order of summation and get the objective function (just dropping
a constant summand).
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke

tryit1
Experienced poster
Posts: 119
Joined: Sun Aug 24, 2008 9:09 pm

### Re: 802 - Lead or Gold

i got AC on 10089 but this problem is giving me trouble when i've vectors like (0,0,q) or (0,q,r).

If all were positive i could convert it to 10089 by multiplying the lcm of (p,q,r) to make the ratio equations equal. But this zero is messing the whole thing. Any tricks , can we add newEPS=1e-3 in place of 0 and actual EPS=1e-9. but adding newEPS to each quantity of that will change the ratio and possibly solution.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

### Re: 802 - Lead or Gold

i got AC on 10089 but this problem is giving me trouble when i've vectors like (0,0,q) or (0,q,r).
You're talking about weights in the desired (target) mixture? Well, if some component is zero, it's just the same problem with one less dimension. If target mixture is (a, b, 0), then the only mixtures you may take are also of form (x, y, 0). So it doesn't hurt to remove all mixtures which are not of this form, drop this 0 coordinate from all vectors, and you get a 2D problem.

(Note: I haven't actually tried to solve this problem by reducing to 10089, so maybe I'm saying here something wrong. I've got accepted with simplex method, and a method based on projection and convex hull.)