802  Lead or Gold
Moderator: Board moderators

 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
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
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org

 Learning poster
 Posts: 60
 Joined: Tue Aug 13, 2002 2:39 am
 Location: Mexico
Oh... Linear algebra =/= linear programming !!
I actually used something like solving system of linear equations...
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
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org

 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
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
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:
Have fun~~marceh wrote:Also, note that you can't add a negative number of stones!!
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org

 Learning poster
 Posts: 83
 Joined: Wed Feb 01, 2006 12:59 pm
 Location: (Fcicu) 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?
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
Mostafa Saad
Re: 802  Lead or Gold
This is a linear programming question. Normal Gaussian elimination or GaussJordan 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.
Hope this help.
Re: 802  Lead or Gold
I tried to implement the socalled MAlgorithm 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.
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
Malgorithm
Last edited by serur on Wed Apr 08, 2009 8:13 am, edited 1 time in total.
Re: 802  Lead or Gold
Look at these two loops:
What's this Malgorithm, btw?
I've used simplex algorithm straight out of CLRS. It's reasonably easy to code and worked just fine.
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.
Notice anything wrong with them? ;)serur wrote:Code: Select all
for ( i = 0; i < ptrq; ++i ) { theta[j = q[i]] = +oo; for ( i = 0; i < m; ++i )
What's this Malgorithm, btw?
I've used simplex algorithm straight out of CLRS. It's reasonably easy to code and worked just fine.
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 nonnegative.roticv wrote:This is a linear programming question. Normal Gaussian elimination or GaussJordan elimination will not solve this problem as far as I know.
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.
Re: 802  Lead or Gold
And here's another algorithm for this problem for geometryinclined 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 :)
Re: 802  Lead or Gold
After fixing that twice engaged i the code above got AC (I'll cut it).
Malgoirithm is a wellknown 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".
Malgoirithm is a wellknown 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