11012 - Cosmic Cabbages

mido · Post by **mido** » Sat Mar 18, 2006 8:26 pm

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

fernando · Post by **fernando** » Sat Mar 18, 2006 8:32 pm

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 · Post by **wook** » Sun Mar 19, 2006 2:34 am

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.

wook · Post by **wook** » Sun Mar 19, 2006 2:36 am

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.

Dapper · Post by **Dapper** » Sun Mar 19, 2006 8:05 am

i do not understand...

StatujaLeha · Post by **StatujaLeha** » Sun Mar 19, 2006 8:39 am

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 · Post by **Dapper** » Sun Mar 19, 2006 9:01 am

thank wook~

shalinmangar · Post by **shalinmangar** » Sun Mar 19, 2006 12:12 pm

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 · Post by **david** » Sun Mar 19, 2006 1:24 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 · Post by **andresw1** » Sun Mar 19, 2006 3:00 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.

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

david · Post by **david** » Sun Mar 19, 2006 3:05 pm

andrews1:
Your algorithm is incorrect. Consider, for instance, points (1, 1, 0), (3, 3, 0), (2, 1, 0), (0, 4, 0).

Raiyan Kamal · Post by **Raiyan Kamal** » Sun Mar 19, 2006 3:12 pm

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 · Post by **krijger** » Sun Mar 19, 2006 4:44 pm

little joey · Post by **little joey** » Sun Mar 19, 2006 5:02 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

krijger · Post by **krijger** » Sun Mar 19, 2006 5:17 pm

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?