Page 1 of 2
11012 - Cosmic Cabbages
Posted: Sat Mar 18, 2006 8:26 pm
by mido
Any ideas for problem A in finals warmup 2(Cabbages)....thanks
11012 - Cosmic Cabbages
Posted: Sat Mar 18, 2006 8:32 pm
by fernando
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
Posted: Sun Mar 19, 2006 2:34 am
by wook
Your output is correct.
I think there are some other counterexamples.
This problem is not so difficult.
A simple idea will lead to an O(n) algorithm.
Posted: Sun Mar 19, 2006 2:36 am
by wook
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.
Posted: Sun Mar 19, 2006 8:05 am
by Dapper
i do not understand...
Posted: Sun Mar 19, 2006 8:39 am
by StatujaLeha
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)
Posted: Sun Mar 19, 2006 9:01 am
by Dapper
thank wook~
Posted: Sun Mar 19, 2006 12:12 pm
by shalinmangar
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.
Posted: Sun Mar 19, 2006 1:24 pm
by david
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.
Posted: Sun Mar 19, 2006 3:00 pm
by andresw1
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...
Posted: Sun Mar 19, 2006 3:05 pm
by david
andrews1:
Your algorithm is incorrect. Consider, for instance, points (1, 1, 0), (3, 3, 0), (2, 1, 0), (0, 4, 0).
Posted: Sun Mar 19, 2006 3:12 pm
by Raiyan Kamal
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.
Posted: Sun Mar 19, 2006 4:44 pm
by 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)
Posted: Sun Mar 19, 2006 5:02 pm
by little joey
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
Posted: Sun Mar 19, 2006 5:17 pm
by krijger
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?