11012 - Cosmic Cabbages

[aminallam]

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]

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]

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!

[StatujaLeha]

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]

I'm completely lost with this problem...
When will the admins upload the other problems? I have questions for them too.

[krijger]

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]

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]

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

[andresw1]

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]

Look at the lecture notes for Week 2.

[trulo17]

guess kalinov post just above is enough for solving this task

[shanto86]

krijger what r the 8 cases?

[andresw1]

Hello,

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

[johnplayers]

Thank You all for your help.

[Psyco]

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!