802 - Lead or Gold

All about problems in Volume 8. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

802 - Lead or Gold

Post by Miguel Angel »

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

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer »

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

Post by Miguel Angel »

I don't think it will be linear programming, someone there to help me??:(
:D Miguel & Marina :D

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer »

Oh... Linear algebra =/= linear programming !! :-P

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

Post by Miguel Angel »

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

JaviGS
New poster
Posts: 6
Joined: Thu Aug 05, 2004 5:24 pm
Location: Spain

Post by JaviGS »

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??
Thanks in advance
Javi

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer »

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~~ 8)
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
Location: Vancouver, BC, Canada
Contact:

Post by sclo »

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

Post by suly »

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 :lol: :wink:

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

Re: 802 - Lead or Gold

Post by 898989 »

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.
Mostafa Saad

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

Re: 802 - Lead or Gold

Post by roticv »

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

Post by serur »

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

Post by mf »

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

Post by mf »

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

Post by serur »

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

Post Reply

Return to “Volume 8 (800-899)”