OJ Board

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

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

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

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

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

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

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

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~~

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

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

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?

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.

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... Bu it gets TLE.

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.

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 :)

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