10089 - Repackaging

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

Moderator: Board moderators

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

10089 - Repackaging

Post by Anderson » Fri Apr 19, 2002 11:27 am

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[1001],b[1001],c[1001];
int A[1001],B[1001];
int t1[1001],t2[1001];
int n;
bool get()
{
int i;
for (i=1;i<=n;i++) {
A = a-b;
B = a-c;
}
int d;
d = A[1]*B[2]-A[2]*B[1];
if ( d==0 ) {
if ( A[1]==0 || B[1]==0 ) {
for (i=1;i<=n;i++)
A = A-B;
}
for (i=2;i<=n;i++) {
if ( A[1]>0 ) {
if ( A<0 ) return true;
}
else {
if ( A[i]>0 ) return true;
}
}
return false;
}
for (i=3;i<=n;i++) {
t1[i] = B[2]*A[i]-A[2]*B[i];
t2[i] = A[1]*B[i]-B[1]*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[0] = a[1]; b[0] = b[1]; c[0] = c[1];
a[1] = a[i]; b[1] = b[i]; c[1] = c[i];
a[i] = a[0]; b[i] = b[0]; c[i] = c[0];
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

Post by Seokchan » Sun Feb 09, 2003 2:31 pm

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

Post by cyfra » Thu Mar 27, 2003 10:11 am

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

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

Post by yiuyuho » Sat Jan 10, 2004 2:18 am

I must say that this is a brilliant model !!!

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Fri Jun 04, 2004 7:24 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?

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Fri Jun 04, 2004 8:06 pm

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.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Fri Jun 04, 2004 9:28 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...

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Fri Jun 04, 2004 9:57 pm

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:

Post by skylander » Tue Jun 08, 2004 7:33 pm

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

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Tue Jun 08, 2004 8:32 pm

I don't know if there exist a website about this, it was my idea.
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:

Post by yiuyuho » Thu Jun 10, 2004 3:58 pm

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

Post by Per » Sat Aug 21, 2004 1:39 pm

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

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Sat Aug 21, 2004 6:53 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

Post by Per » Sat Aug 21, 2004 7:01 pm

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

Post by CC » Tue Nov 09, 2004 3:01 pm

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 ?

Post Reply

Return to “Volume 100 (10000-10099)”