11012  Cosmic Cabbages
Moderator: Board moderators
11012  Cosmic Cabbages
Any ideas for problem A in finals warmup 2(Cabbages)....thanks
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:
My output
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
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

 Learning poster
 Posts: 91
 Joined: Tue May 31, 2005 2:01 pm
 Location: Russia
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)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.

 New poster
 Posts: 6
 Joined: Sun Nov 27, 2005 8:24 am
 Location: India
The hint that wook gave is the key to solving the problem in O(n). Thanks wook.StatujaLeha wrote: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)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.
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.
// [edit] 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...
I'm new to the forum so please tell me if my post is not OK because I offer direct solution to the problem.
// [edit] 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.

 Experienced poster
 Posts: 106
 Joined: Thu Jan 29, 2004 12:07 pm
 Location: Bangladesh
 Contact:
I had to solve a problem like this some days ago and I came up with a bruteforce 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.
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.

 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
COMPLETELY OFF TOPIC
Hi krijger,
You are ErikJan 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
Hi krijger,
You are ErikJan 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.
Hi little joey.
I am indeed 'ErikJan 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?
I am indeed 'ErikJan 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?