## 11012 - Cosmic Cabbages

Moderator: Board moderators

aminallam
New poster
Posts: 39
Joined: Thu Dec 08, 2005 12:51 pm
Location: Suez, Egypt.
I do not know why all explanations are "encrypted" !
Is it forbidden to post a complete explanation here?
Here is a complete explanation:
1) Get the 8 corners of the bounding box of the points.
2) For each corner, get the nearest point to it (in tie, choose any).
3) For each of these 8 points, compute its distance from all other points.

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain
No, It is not forbidden to post a complete explanation, but in such case the people use write something like <SPOILER> to warn that the next text will give you a complete method to solve the problem. This is because somepeople only want a hint and then thinking about the problem, they (and sometimes me) wish find the solution themself.

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
Hi Erik-Jan,

No, I never went to the world finals. I'm a bit too old for that. In fact I only started serious programming when I lost my job a few years ago, so I'm only in it for the fun. And my coding speed is a bit to slow to do well in an actual contest.

I'll wear an orange wig 9-13 april . Laat ze 'n poepie ruiken!
The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.

StatujaLeha
Learning poster
Posts: 91
Joined: Tue May 31, 2005 2:01 pm
Location: Russia
krijger wrote:You're trying to find the i and j for which this function is maximal:

|xi-xj|+|yi-yj|+|zi-zj|

Suppose you know i, what do you know about j? (hint: there are 8 cases)
Have I understood right that you propose to find vertexes that form сonvex polyhedron and then find maximum distance between this points?

andresw1
New poster
Posts: 27
Joined: Sat Mar 18, 2006 5:04 pm
I'm completely lost with this problem...
When will the admins upload the other problems? I have questions for them too.

krijger
New poster
Posts: 39
Joined: Wed Jul 21, 2004 12:35 am
StatujaLeha wrote:
krijger wrote:You're trying to find the i and j for which this function is maximal:

|xi-xj|+|yi-yj|+|zi-zj|

Suppose you know i, what do you know about j? (hint: there are 8 cases)
Have I understood right that you propose to find vertexes that form сonvex polyhedron and then find maximum distance between this points?
I'm not sure what you mean. What I mean is that if you are given i, there are only 8 possible points you could consider, and those 8 point are the same for each i. Reverse the roles of i and j and it follows that i and j must both be one of those 8 points.

kalinov
New poster
Posts: 27
Joined: Tue Mar 29, 2005 3:10 pm
Location: Croatia
To maximize |xi-xj| + |yi-yj| + |zi-zj| you can choose if

1. (xi-xj) will be positive or negative
2. (yi-yj) will be positive or negative
3. (zi-zj) will be positive or negative

You can do it in 8 ways. For example if you choose (xi-xj) to be positive, (yi-yj) to be negative, and (zi-zj) to be positive then you get:

xi-xj + yj-yi + zi-zj = (xi-yi+zi) - (xj-yj+zj)

To maximize this function we have to find point i that maximizes x-y+z and point j that minimizes it.

So you have to find maximum for each of the eight functions and see which one is the best. (Actually there are only 4 functions because you get the same functions with i and j swapped)

Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:
I'm glad this problem is causing so many troubles for everybody. ;-)

I got it from a course I'm taking. It is taught by Avner Magen at the University of Toronto. If you want to see a good explanation of how to solve it, look at the lecture notes from week 2 here:
http://www.cs.toronto.edu/~avner/teachi ... index.html

Good luck...
If only I had as much free time as I did in college...

andresw1
New poster
Posts: 27
Joined: Sat Mar 18, 2006 5:04 pm
Hello,
Abednego, I skipped trough the site, and all the pdf and ps files but from a first sight I could see anything related. These papers are too hard for me to understand but if you tell me which file should I look I can focus my understanding skills on it and try again:)

Btw can you give a short explanation about the theory presented at these lecture notes. What are the applications? I saw some graph drawings as well as gemotry pictures, also some maxflows...

Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:
Look at the lecture notes for Week 2.
If only I had as much free time as I did in college...

trulo17
Learning poster
Posts: 62
Joined: Mon Jan 24, 2005 6:12 am
Location: Lima,Peru
guess kalinov post just above is enough for solving this task

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm
krijger what r the 8 cases?
Self judging is the best judging!

andresw1
New poster
Posts: 27
Joined: Sat Mar 18, 2006 5:04 pm
Hello,

Kalinov,
Thank you very much! Now I get it:)))

johnplayers
New poster
Posts: 5
Joined: Mon Apr 03, 2006 12:52 pm
Thank You all for your help.

Psyco
New poster
Posts: 14
Joined: Sat Jan 21, 2006 12:39 pm
Contact:

### Hint

There are 8 cases.

max = 1, min = 0

0 0 0
0 0 1
0 1 0
1 0 0
1 1 0
0 1 1
1 0 1
1 1 1

Have a good time!