## 802 - Lead or Gold

Moderator: Board moderators

Miguel Angel
Learning poster
Posts: 60
Joined: Tue Aug 13, 2002 2:39 am
Location: Mexico

### 802 - Lead or Gold

Can someone gimme a hint of how to solve it?, I simply have no clear idea about it:P
Miguel & Marina

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
This task is quite interesting. The main challenge is to figure out the number of mixture required if "Possible" is to be printed. Some linear algebra stuff here...
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Miguel Angel
Learning poster
Posts: 60
Joined: Tue Aug 13, 2002 2:39 am
Location: Mexico
I don't think it will be linear programming, someone there to help me??:(
Miguel & Marina

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
Oh... Linear algebra =/= linear programming !!

I actually used something like solving system of linear equations...
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Miguel Angel
Learning poster
Posts: 60
Joined: Tue Aug 13, 2002 2:39 am
Location: Mexico

### In fact

Yeap in fact wanted to say linear algebra but my mouth said another. I have already solved with Gauss Jordan, thanks
Miguel & Marina

JaviGS
New poster
Posts: 6
Joined: Thu Aug 05, 2004 5:24 pm
Location: Spain
Hi, I got WA in this problem, but I don't know if my approach is wrong. Here is it:

I consider the vector space R^3 and treat the mixtures as vectors in that space. I make a set S of linearly independant vectors, where S is formed by some of the n mixtures. Then:
If size(S) >=3 then it is always possible
If size(S) =1,2: if our desired solution is linearly dependant with the vectors in S then it is possible. Otherwise it's impossible.

Am I missing something??
Javi

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
Your idea looks fine, but have you considered this:
marceh wrote:Also, note that you can't add a negative number of stones!!
Have fun~~
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
The simplex algorithm can be used on this problem, it checks the feasibility of the solution at the same time.

suly
New poster
Posts: 1
Joined: Thu Mar 08, 2007 1:16 pm
can someone plzzz elaborate this problems... i have tried ma level best but i am not getting the answer to it ....

otherwise u cn simple post the code

898989
Learning poster
Posts: 83
Joined: Wed Feb 01, 2006 12:59 pm
Location: (Fci-cu) Egypt
Contact:

### Re: 802 - Lead or Gold

The Hints here is not enough for me, Can some one go more in details.

All what I realized alone that given input like:
a0 b0 c0
a1 b1 c1
a2 c2 b2

and target ration
at bt ct
We can have matrix as following in relation AX = Y = factor * Y'
A =
a0 a1 a2
b0 b1 b2
c0 c1 c2

X = // This is the factor matrix we multiply in current matrix ratios
R1
R2
R3

Y' = // taregt
at bt ct

factor is the gcd between 3 elements in Y.

If this factor does not exist, then problem is direct gauess jordn, How to attack the problem now?
Sleep enough after death, it is the time to work.

roticv
Learning poster
Posts: 63
Joined: Sat Dec 11, 2004 9:28 am

### Re: 802 - Lead or Gold

This is a linear programming question. Normal Gaussian elimination or Gauss-Jordan elimination will not solve this problem as far as I know. You will need to do Simplex Phase I (which test for the feasibility of the solution). Coding the simplex algorithm will be very much like coding Gaussian elimination.

Hope this help.

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

### Re: 802 - Lead or Gold

I tried to implement the so-called M-Algorithm of simplex method: introduced 3 aritificial variables in order to obtain
an identity matrix in the constraints' matrix, introduced an objective function Z = (x[n+1] + x[n+2] + x[n+3])*M --> min,
and so on...

Code: Select all

``````M-algorithm
``````
Bu it gets TLE.
Last edited by serur on Wed Apr 08, 2009 8:13 am, edited 1 time in total.

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

### Re: 802 - Lead or Gold

Look at these two loops:
serur wrote:

Code: Select all

``````         for ( i = 0; i < ptr-q; ++i ) {
theta[j = q[i]] = +oo;
for ( i = 0; i < m; ++i )
``````
Notice anything wrong with them? ;)

What's this M-algorithm, btw?
I've used simplex algorithm straight out of CLRS. It's reasonably easy to code and worked just fine.
roticv wrote:This is a linear programming question. Normal Gaussian elimination or Gauss-Jordan elimination will not solve this problem as far as I know.
Well, actually, I think it can. If solution is possible, then you can get it by mixing at most 3 mixtures. So, you could brute force all pairs and triples of mixtures, do gaussian elimination for each of them, and check whether the result is non-negative.
Time complexity is O(n^3) - I'm sure that would be definitely enough at the actual 1998 world finals contest. They have very relaxed time limits.

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

### Re: 802 - Lead or Gold

And here's another algorithm for this problem for geometry-inclined people: first, project all points (a[i],b[i],c[i]) onto plane x+y+z=1 by (x,y,z) -> (x,y)/(x+y+z), find their convex hull and check that (a,b)/(a+b+c) is in this convex hull. This is faster and much more fun than learning simplex algorithm :)

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

### Re: 802 - Lead or Gold

After fixing that twice engaged i the code above got AC (I'll cut it).
M-algoirithm is a well-known technique:
http://www.math.cuhk.edu.hk/~wei/lpch3.pdf
keywords: "artificial basis","augmented problem".
It is possible to check whether the system of constraints is inconsistent
by solving this "augmented problem".
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke