11012 - Cosmic Cabbages

Moderator: Board moderators

mido
Learning poster
Posts: 78
Joined: Sun Jun 16, 2002 9:48 pm
Location: Cairo,Egypt

11012 - Cosmic Cabbages

Any ideas for problem A in finals warmup 2(Cabbages)....thanks

fernando
New poster
Posts: 21
Joined: Sat Mar 18, 2006 8:21 pm

11012 - Cosmic Cabbages

Hi, any ideas how to solve this problem?, during contest i used the next algo: i determine the points who are "extreme", with extreme i want to mean the points with the minimum and maximum X,Y,Z coordinates, intituitively i thought that the two points with maximum distance are in this set, but i got WA, can anyone give me a counterexample, here are some I/O, please post more cases:

Code: Select all

``````10
2
1 1 1
2 2 2
3
0 0 0
0 0 1
1 1 0
4
0 1 2
3 4 5
6 7 8
9 10 11
6
0 0 0
1 1 1
2 2 2
0 0 1
1 0 0
0 1 0
6
0 0 0
1 1 1
2 2 2
0 0 1
100000000 100000000 100000000
-100000000 -100000000 -100000000
12
0 0 0
1 1 1
2 2 2
0 0 1
5 7 9
190 89 67
1321 312 5466
312 312 121
312 312 45
3125 5454 545454
234 4324 4234
-5 -6 545454
4
5 7 -25
-5 -7 0
0 0 0
5 7 1000
2
-1 -2 -5
-100 -200 -300
3
1000 1999 1234
1000 1999 1234
100 1693 1233
7
0 0 0
100 100 0
30 20 0
20 30 0
1 1 1
99 99 99
100 0 100
``````
My output

Code: Select all

``````Case #1: 3
Case #2: 3
Case #3: 27
Case #4: 6
Case #5: 600000000
Case #6: 554033
Case #7: 1025
Case #8: 592
Case #9: 1207
Case #10: 297
``````

wook
Learning poster
Posts: 76
Joined: Fri Oct 01, 2004 11:34 am
Location: Korea, Republic Of
I think there are some other counterexamples.

This problem is not so difficult.
A simple idea will lead to an O(n) algorithm.
Sorry For My Poor English..

wook
Learning poster
Posts: 76
Joined: Fri Oct 01, 2004 11:34 am
Location: Korea, Republic Of
This problem is not so difficult.
Once you got a simple idea, you can make out a linear algorithm.

Another Hint)
The manhattan distance
between (0, 0) and (2, 3)
between (0, 0) and (3, 2)
between (0, 0) and (5, 0)
...
is same.
Sorry For My Poor English..

Dapper
New poster
Posts: 2
Joined: Sat Mar 18, 2006 1:29 pm

i do not understand...

StatujaLeha
Learning poster
Posts: 91
Joined: Tue May 31, 2005 2:01 pm
Location: Russia
wook wrote:This problem is not so difficult.
Once you got a simple idea, you can make out a linear algorithm.

Another Hint)
The manhattan distance
between (0, 0) and (2, 3)
between (0, 0) and (3, 2)
between (0, 0) and (5, 0)
...
is same.
It is clear how to calculate the distance between two cabbages. Can you give a hint how to get algorithm O(n)? During the contest I thought up only O(N^2)

Dapper
New poster
Posts: 2
Joined: Sat Mar 18, 2006 1:29 pm
thank wook~

shalinmangar
New poster
Posts: 6
Joined: Sun Nov 27, 2005 8:24 am
Location: India
StatujaLeha wrote:
wook wrote:This problem is not so difficult.
Once you got a simple idea, you can make out a linear algorithm.

Another Hint)
The manhattan distance
between (0, 0) and (2, 3)
between (0, 0) and (3, 2)
between (0, 0) and (5, 0)
...
is same.
It is clear how to calculate the distance between two cabbages. Can you give a hint how to get algorithm O(n)? During the contest I thought up only O(N^2)
The hint that wook gave is the key to solving the problem in O(n). Thanks wook.

david
Learning poster
Posts: 83
Joined: Mon Apr 21, 2003 10:14 pm
shalinmangar wrote: The hint that wook gave is the key to solving the problem in O(n). Thanks wook.
What hint? wook hasn't said anything useful.

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

I'm new to the forum so please tell me if my post is not OK because I offer direct solution to the problem.

//  Wrong idea ((

??? I don't know if this is the solution I just try to use the hitn you gave us... I can't find other application of your hint which can be used in liniear time...
Last edited by andresw1 on Sun Mar 19, 2006 3:46 pm, edited 1 time in total.

david
Learning poster
Posts: 83
Joined: Mon Apr 21, 2003 10:14 pm
andrews1:
Your algorithm is incorrect. Consider, for instance, points (1, 1, 0), (3, 3, 0), (2, 1, 0), (0, 4, 0).

Raiyan Kamal
Experienced poster
Posts: 106
Joined: Thu Jan 29, 2004 12:07 pm
Contact:
I had to solve a problem like this some days ago and I came up with a brute-force solution. Later, when discussing it with others, someone gave me a good idea.

Make a 3d convex hull and chek the points on the convex hull only. This will speed up the process, but for special cases where all the points are on the hull, it does not offer any advantage.

krijger
New poster
Posts: 39
Joined: Wed Jul 21, 2004 12:35 am
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)

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
COMPLETELY OFF TOPIC

Hi krijger,
You are Erik-Jan Krijgsman from Holland, isn't it? I noticed you did very well on the warmup contest yesterday, and have been performing good at recent contests as well. Are you going to the world finals? Do you you know if any Dutch teams will?

Just curious
The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.

krijger
New poster
Posts: 39
Joined: Wed Jul 21, 2004 12:35 am
Hi little joey.

I am indeed 'Erik-Jan Krijgsman' from Holland and actually, I am part of the Dutch team that goes to the world finals ('MessedUp').
Yesterday we (me and one of my teammates, the other couldn't come) did a practice session for the world finals and it went pretty well, allthough we hope to do better in Texas of course

But now I'm curious too You are also from the Netherlands right? And you perform pretty well regularly also and you solved a lot of problems, but I never saw your name at other contests. Have you for example ever been to the World Finals?