11012 - Cosmic Cabbages

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

Moderator: Board moderators

aminallam
New poster
Posts: 39
Joined: Thu Dec 08, 2005 12:51 pm
Location: Suez, Egypt.

Post by aminallam » Sun Mar 19, 2006 5:21 pm

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

Post by Emilio » Sun Mar 19, 2006 6:40 pm

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.

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

Post by little joey » Sun Mar 19, 2006 6:42 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

Post by StatujaLeha » Sun Mar 19, 2006 10:52 pm

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

Post by andresw1 » Sun Mar 19, 2006 11:22 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

Post by krijger » Mon Mar 20, 2006 1:29 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

Post by kalinov » Mon Mar 20, 2006 2:09 am

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)

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Mon Mar 20, 2006 3:24 am

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

Post by andresw1 » Mon Mar 20, 2006 10:10 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...

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Tue Mar 21, 2006 1:39 am

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

Post by trulo17 » Tue Mar 21, 2006 6:16 pm

guess kalinov post just above is enough for solving this task

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

Post by shanto86 » Thu Mar 23, 2006 8:36 am

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

Post by andresw1 » Thu Mar 23, 2006 10:12 pm

Hello,

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

johnplayers
New poster
Posts: 5
Joined: Mon Apr 03, 2006 12:52 pm

Post by johnplayers » Tue Apr 04, 2006 12:18 pm

Thank You all for your help.

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

Hint

Post by Psyco » Thu Apr 06, 2006 12:24 pm

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!

Post Reply

Return to “Volume 110 (11000-11099)”