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

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

11012 - Cosmic Cabbages

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

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

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
Learning poster
Posts: 76
Joined: Fri Oct 01, 2004 11:34 am
Location: Korea, Republic Of

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.
Sorry For My Poor English.. :)

wook
Learning poster
Posts: 76
Joined: Fri Oct 01, 2004 11:34 am
Location: Korea, Republic Of

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.
Sorry For My Poor English.. :)

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

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

:o
i do not understand...
:(

StatujaLeha
Learning poster
Posts: 91
Joined: Tue May 31, 2005 2:01 pm
Location: Russia

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
New poster
Posts: 2
Joined: Sat Mar 18, 2006 1:29 pm

Post by Dapper » Sun Mar 19, 2006 9:01 am

thank wook~

shalinmangar
New poster
Posts: 6
Joined: Sun Nov 27, 2005 8:24 am
Location: India

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
Learning poster
Posts: 83
Joined: Mon Apr 21, 2003 10:14 pm

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
New poster
Posts: 27
Joined: Sat Mar 18, 2006 5:04 pm

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

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
Experienced poster
Posts: 106
Joined: Thu Jan 29, 2004 12:07 pm
Location: Bangladesh
Contact:

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

Post by krijger » Sun Mar 19, 2006 4:44 pm

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)

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

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 :)
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

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?

Post Reply

Return to “Volume 110 (11000-11099)”