10885 - Martin the Gardener

All about problems in Volume 108. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Antonio Ocampo
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per

10885 - Martin the Gardener

Post by Antonio Ocampo » Sun Jul 31, 2005 9:56 pm

Hi guys

I don


Antonio Ocampo
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per

Post by Antonio Ocampo » Sun Jul 31, 2005 11:25 pm

That paper is very hard for me :oops:. What I feel is, if this is the expected way to solve the problem, then this is a maths problem instead of programming problem. Thx anyway :lol:

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post by misof » Sun Jul 31, 2005 11:28 pm

Well, it was "Abednego's Mathy Contest", so one could expect math problems...

(And don't worry, the paper was too hard for me too, I found it during the contest but couldn't make a working solution... I plan to get back to this task once I have more time ;) )

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Mon Aug 01, 2005 8:54 am

No hard papers are required. The idea is very simple. I was very happy when 1 person solved this problem during the contest! He ended up in the 155'th place. :-)

The key observation is the following. Suppose that you know how to plant 13 trees at rational coordinates, so that the distance between each pair of trees is a rational number. Then you can simply multiply every coordinate by the common denominator of everything (coordinates and distances), and you will get integer coordinates and integer distances.

Now how do we solve the problem in rational numbers? That's not very hard at all. Here is a hint. We are not allowed to place 3 trees on the same line. If you add the restriction that no 4 trees are allowed on the same circle, then this is a famous unsolved problem. The largest number of trees that anyone knows how to place with the additional no-4-on-a-circle constraint is 6.
If only I had as much free time as I did in college...

User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho » Mon Aug 01, 2005 10:45 am

Hmmm.. It turns out that, for me, understanding misof's reference is easier than getting insight from Abednego's hint. :)

Cosmin.ro
Learning poster
Posts: 95
Joined: Thu Aug 21, 2003 12:02 am

Post by Cosmin.ro » Mon Aug 01, 2005 11:38 am

I think he means all points are on a circle.

Antonio Ocampo
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per

Post by Antonio Ocampo » Tue Aug 02, 2005 5:23 am

I'm so frustrated :cry:

gush
New poster
Posts: 13
Joined: Tue Oct 14, 2003 12:47 pm

Post by gush » Wed Aug 10, 2005 10:42 am

This is my answer:
....
I've tested that the distances between them are integers. But I still got WA. Why?
Last edited by gush on Thu Aug 11, 2005 10:56 am, edited 1 time in total.

Cosmin.ro
Learning poster
Posts: 95
Joined: Thu Aug 21, 2003 12:02 am

Post by Cosmin.ro » Wed Aug 10, 2005 11:27 am

Maybe 3 colinear points, have you tested that?

gush
New poster
Posts: 13
Joined: Tue Oct 14, 2003 12:47 pm

Post by gush » Wed Aug 10, 2005 11:55 am

All the points are on the same circle. So there should be no 3 points in the same line.

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

Post by little joey » Wed Aug 10, 2005 1:13 pm

gush, your values are OK and I just got AC with them.

Please make sure you send in a program that prints them, not just a text file that contains them.

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Wed Aug 10, 2005 6:05 pm

gush, and when you get AC, please don't forget to remove the numbers from your post. Thanks.
If only I had as much free time as I did in college...

gush
New poster
Posts: 13
Joined: Tue Oct 14, 2003 12:47 pm

Post by gush » Thu Aug 11, 2005 10:57 am

ok

kp
Learning poster
Posts: 71
Joined: Tue Apr 26, 2005 1:29 am
Location: Russia

Post by kp » Sat Aug 20, 2005 5:36 pm

So points should be on a cirle, but what's next?

Should I look for points like

x = R*cos(k*phi)
y = R*sin(k*phi)

k = 0..12

for some R and phi?

If yes then how can I find such R and phi?

Post Reply

Return to “Volume 108 (10800-10899)”