802 - Lead or Gold

[Miguel Angel]

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

[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...

[Miguel Angel]

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

[Observer]

Oh... Linear algebra =/= linear programming !!

I actually used something like solving system of linear equations...

[Miguel Angel]

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

[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]

Your idea looks fine, but have you considered this:

Also, note that you can't add a negative number of stones!!

Have fun~~

[sclo]

The simplex algorithm can be used on this problem, it checks the feasibility of the solution at the same time.

[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

[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?

[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]

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.

[mf]

Look at these two loops:

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.

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]

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]

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".