## 10089 - Repackaging

Moderator: Board moderators

Anderson
New poster
Posts: 6
Joined: Thu Apr 18, 2002 12:47 pm

### 10089 - Repackaging

Could you point out the bugs or give me some test cases?
thank you!
the program is as follows:

[cpp]#include <iostream.h>
#include <fstream.h>
ifstream fin("10089.in");
int a,b,c;
int A,B;
int t1,t2;
int n;
bool get()
{
int i;
for (i=1;i<=n;i++) {
A = a-b;
B = a-c;
}
int d;
d = A*B-A*B;
if ( d==0 ) {
if ( A==0 || B==0 ) {
for (i=1;i<=n;i++)
A = A-B;
}
for (i=2;i<=n;i++) {
if ( A>0 ) {
if ( A<0 ) return true;
}
else {
if ( A[i]>0 ) return true;
}
}
return false;
}
for (i=3;i<=n;i++) {
t1[i] = B*A[i]-A*B[i];
t2[i] = A*B[i]-B*A[i];
}
for (i=3;i<=n;i++) {
if ( d>0 ) {
if ( (t1[i]<0 && t2[i]<0) || (t1[i]<0 && t2[i]==0) || (t1[i]==0 && t2[i]<0) ) return true;
}
else
if ( (t1[i]>0 && t2[i]>0) || (t1[i]>0 && t2[i]==0) || (t1[i]==0 && t2[i]>0) ) return true;
}
return false;
}
void main()
{
cin>>n;
while ( n!=0 ) {
int i;
bool ok;
ok = false;
for (i=1;i<=n;i++) {
cin>>a[i]>>b[i]>>c[i];
if ( a[i]==b[i] && a[i]==c[i] ) ok = true;
}
if ( !ok ) ok = get();
if ( ok ) {
cout<<"Yes"<<endl;
cin>>n;
continue;
}
for (i=3;i<=n;i++) {
a = a; b = b; c = c;
a = a[i]; b = b[i]; c = c[i];
a[i] = a; b[i] = b; c[i] = c;
ok = get();
if ( ok ) {
cout<<"Yes"<<endl;
break;
}
}
if ( i>n ) cout<<"No"<<endl;
cin>>n;
}
}[/cpp]

[Edited by fpnc to improve visibility via BBCode 'cpp']

Seokchan
New poster
Posts: 3
Joined: Thu Feb 06, 2003 3:28 pm

### 10089

My algorithm tests all pair of packages, but it is too slow (I got TL)
I can`t think better algorithm.

help plz.

cyfra
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland
Hi!

I have an other algorithm that is correct, and got AC.

My algorithm goes like this :

We treat is as the vectors on the plane. if the package is (s1,s2,s3) it is count as an vector [s2-s1,s3-s1]. And our problem is to find whether starting from point (0,0) you can return there.

And that's all..

Good Luck yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:
I must say that this is a brilliant model !!!

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
Hmm. I'm completely stuck on this problem. I see the simplification using 2D-vectors, but have no clue how to combine them efficiently to reach (0,0). Just trying millions and millions of possibilities gives TLE, obviously.
Can anyone give me a hint?

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
I solved this problem by reducing it to 2D convex hull and checking if one point (representing the package k,k,k) lies inside the convex hull.
But with the other method: you could use simplex to check if there is a solution.

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
Thanks.
I can not see the connection with a convex hull, but I'll think about it. I'll have to study the simplex method; I've heard about it, but don't know it. Can come in handy for other problems too, so it's worth investing time learning it, I guess.
BTW, how is the ellipsis going? There is a realy fast iterative method for it; much like regula falsi...

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
Think of the given packages as vectors in 3D. You want to find a linear combination that build the vector (k,k,k).
The given vectors build a infinite pyramid with (0,0,0) at the top. I assumed, that if the line with direction (1,1,1) is inside the pyramid, then it is possible to find a linear combination.
To make it easier to check if it is in the pyramid, I use 2D convex hull.
BTW, how is the ellipsis going? There is a realy fast iterative method for it; much like regula falsi...
My original method (something like dividing the search interval, select local optimums and search on smaller intervals) for 10631 does not work. Either I get TLE, or I risk to get precision errors.
I will take a look at the regula falsi method. I didn't know it before, thanks for the hint.

skylander
New poster
Posts: 13
Joined: Mon Jun 10, 2002 3:24 pm
Contact:
To make it easier to check if it is in the pyramid, I use 2D convex hull.
i am interested to know how a convex hull could be use to solve a linear system of equations...i am not very clear about the part on the pyramid and how the convex hull could be used in this case....it would be best if u can explain this in a little more detail or direct me to any website where i can learn such techniques....thx in advance... Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
Anyway, I can't solve the system of equations with my method, I just try to check if there can be a solution.
It is clear, that with linear combination (allowing any real coefficient) of the given vectors you can build all vectors that are between them. This builds a thing with a top at (0,0) that extends to positive infinity. I called it pyramid, although there may be more than 3 sides here.
Now I did following assumption: if vector (1,1,1) is in this pyramid, then I can find a linear combination with rational coefficients. This is a assumption where I really don't know if it is correct. Perhaps I was just lucky to get Accepted.
Anyway, if coefficients are rational, it would be possible to multiply by the least common multiple and the result are integer coefficients, so I can output "YES".
I think you can imagine yourself how to check if vector (1,1,1) is in the pyramid.

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:
Adrian, did u use the method like the one cyfra suggested to make it 2D? thx.

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
little joey wrote:Hmm. I'm completely stuck on this problem. I see the simplification using 2D-vectors, but have no clue how to combine them efficiently to reach (0,0). Just trying millions and millions of possibilities gives TLE, obviously.
Can anyone give me a hint?
There is a much simpler method to solve the 2D-simplification than the elaborate methods suggested here (which I'm very impressed by, btw). A key hint: you'll never need more than 4 different vectors to form the solution. (Of course, O(n^4) is too much, but thinking about it a while yields a very simple O(n^2) algorithm).

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
Thanks Per for the hint. It's brilliant. Continueing in that line of thought, I even found an O(N) algorithm, so I finaly solved this problem (in a quite reasonable time).

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
little joey wrote:Continueing in that line of thought, I even found an O(N) algorithm.
Doh! I should've seen that! CC
New poster
Posts: 8
Joined: Tue Oct 14, 2003 5:02 am
little joey wrote:Thanks Per for the hint. It's brilliant. Continueing in that line of thought, I even found an O(N) algorithm, so I finaly solved this problem (in a quite reasonable time).
can u explain it in more detail, I can't see it ?