11012  Cosmic Cabbages
Moderator: Board moderators
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.
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.
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.

 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
Hi ErikJan,
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 913 april . Laat ze 'n poepie ruiken!
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 913 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.

 Learning poster
 Posts: 91
 Joined: Tue May 31, 2005 2:01 pm
 Location: Russia
Have I understood right that you propose to find vertexes that form сonvex polyhedron and then find maximum distance between this points?krijger wrote:You're trying to find the i and j for which this function is maximal:
xixj+yiyj+zizj
Suppose you know i, what do you know about j? (hint: there are 8 cases)
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.StatujaLeha wrote:Have I understood right that you propose to find vertexes that form сonvex polyhedron and then find maximum distance between this points?krijger wrote:You're trying to find the i and j for which this function is maximal:
xixj+yiyj+zizj
Suppose you know i, what do you know about j? (hint: there are 8 cases)
To maximize xixj + yiyj + zizj you can choose if
1. (xixj) will be positive or negative
2. (yiyj) will be positive or negative
3. (zizj) will be positive or negative
You can do it in 8 ways. For example if you choose (xixj) to be positive, (yiyj) to be negative, and (zizj) to be positive then you get:
xixj + yjyi + zizj = (xiyi+zi)  (xjyj+zj)
To maximize this function we have to find point i that maximizes xy+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)
1. (xixj) will be positive or negative
2. (yiyj) will be positive or negative
3. (zizj) will be positive or negative
You can do it in 8 ways. For example if you choose (xixj) to be positive, (yiyj) to be negative, and (zizj) to be positive then you get:
xixj + yjyi + zizj = (xiyi+zi)  (xjyj+zj)
To maximize this function we have to find point i that maximizes xy+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)

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