Зиммерманн-2

[omega]

Да, решение 30:44 элементарно получается из рекордного решения 28:39 методом наращивания.
А от решения 30:44 и вся цепочка рекордов дальше.
Наверняка эти результаты уже другие конкурсанты тоже получили.

Сейчас ввела решение 28:39 и из него сразу же получила решение 30:44

Код: Выбрать все

(49729680,563603040),(0,986305320),(82882800,704503800),(41441400,0),(49729680,140900760),(35521200,503217000),(43243200,398197800),(41441400,563603040),(33153120,422702280),(33153120,704503800),(49729680,704503800),(47361600,503217000),(46414368,422702280),(41441400,422702280),(37297260,352251900),(0,7749541800),(45208800,448320600),(43513470,563603040),(41441400,704503800),(37297260,563603040),(49729680,422702280),(44204160,610569960),(42625440,503217000),(0,503217000),(45585540,493152660),(0,140900760),(62162100,352251900),(46621575,616440825),(43743700,508808300),(44629200,541926000)

Координаты здесь небольшие, хорошо работать с такими координатами.

Но вот переход от N=28 к N=29 никак не даёт больше +2, хоть убейся

[Hellko]

Source of the post
Наталия, чего то не сооброжу, где вы берете координаты рекордов? В таблице рекордов выдается картинка, а сами координаты где?

когда нажимаешь на решение. в адресной строке браузера координаты.

[omega]

Source of the post
Наталия, чего то не сооброжу, где вы берете координаты рекордов? В таблице рекордов выдается картинка, а сами координаты где?

Они там хитро замаскировали координаты.

Копируйте их из адресной строки браузера.

Уже ответил Hellko

Кстати, был тоже перескок +3

N=33, p=49
N=34, p=52

Рекорд, который нашёл Pavlovsky, 33:50, этот перескок ликвидировал.

Зато образовался перескок в другом месте:
N=29, p=41
N=30, p=44

[omega]

Мой вариант решения 33:50

Код: Выбрать все

(845404560,563603040),(0,986305320),(1409007600,704503800),(704503800,0),(845404560,140900760),(603860400,503217000),(704503800,563603040),(563603040,422702280),(563603040,704503800),(845404560,704503800),(805147200,503217000),(789044256,422702280),(704503800,422702280),(634053420,352251900),(768549600,448320600),(704503800,704503800),(845404560,422702280),(751470720,610569960),(724632480,503217000),(0,503217000),(774954180,493152660),(1056755700,352251900),(792566775,616440825),(735134400,398197800),(0,7749541800),(758696400,541926000),(671350680,663062400),(725224500,642341700),(634053420,563603040),(0,140900760),(739728990,563603040),(743642900,508808300),(3804320520,1409007600)

Продолжаю мучить решение 28:39

[omega]

Посмотрите, какое красивое рекордное решение 27:36 (автор Dmitry Kamenetsky)

Код: Выбрать все

(234780,234780),(352170,469560),(704340,469560),(0,0),(352170,234780),(704340,939120),(704340,1173900),(704340,234780),(469560,547820),(352170,586950),(0,704340),(234780,391300),(0,-469560),(469560,469560),(281736,375648),(422604,422604),(0,234780),(234780,469560),(281736,328692),(234780,156520),(301860,335400),(352170,410865),(328692,359996),(379260,397320),(387387,399126),(278460,316680),(436020,503100)

Рекорд повторили 5 человек.
Конструкция обалденная! Мне такая даже в голову не пришла.

[omega]

Pavlovsky
вы уже ввели ваши новые рекорды!

Здорово! Молодцом!

Перевела

After a fight with his fists do not wave

Иностранцы поймут поговорку? Однако Гугль как точно перевёл

А я запостила "цветок Дьюдени" и свою неправильную звезду (решение 16:12). Картинки прикрепила. Вот!

И ещё запостила им ссылку на свою статью.

Offered his work "Orchard Planting Problem".
This article was written in Russian.
Format pdf.
[url=http://narod.ru/disk/35625399001/contest3.pdf.html]http://narod.ru/disk/35625399001/contest3.pdf.html[/url]

Перевела статью в формат pdf и выложила на файлообменник Народа.
Желающие могут скачать (это та же самая статья, которуя я выше выложила, но там она в формате doc).
А большая статья-то получилась 130 с лишним страниц Картинок много.

[omega]

Ну, я до них добралась
Сейчас ещё запостила:

isomorphic solutions

This is my solution N (11) = 6:

1) (0,0),(1200,0),(1200,900),(600,450),(1800,-450),(2400,-1800),(1000,150),(960,0),(400,300),(1600,0),(800,200)
2) (40040,0),(80080,0),(60060,80080),(48048,32032),(72072,32032),(75075,20020),(60060,20020),(0,-160160),(65520,14560),(68640,22880),(64680,24640)
3) (-454020,-454020),(264845,113505),(128639,-204309),(340515,-113505),(605360,0),(378350,378350),(227010,227010),(151340,151340),(232415,37835),(195615,89355),(205625,133245)

My solutions are isomorphic (so to speak?):

Solution Kevin Burfitt is isomorphic my decisions?
(0,0),(0,6),(0,9),(0,10),(2,8),(6,4),(6,6),(10,0),(12,2),(15,0),(18,0)

And how many different solutions have been found by competitors? This is an interesting question!
I propose to identify the different forms of configurations for each N.

Товарищи, родные русские! Как поняли мой английский?
Иностранцы чего-нибудь поймут?



Pavlovsky
вы ушли новые рекорды искать?

Мне надоело, бросила. Первые 4 быстро получились, а больше ничего не получается. Конечно, ваша программа, может, и найдёт, но не сразу, не так быстро, как первые 4.

И потом, сами же сказали: "After a fight with his fists do not wave"

[Pavlovsky]

After a fight with his fists do not wave

"После драки кулаками не машут". Все таки на русском языке эта пословица звучит калоритнее. Ведь драка <> fight(сражение).

Блин торкнула супер-пупер идея.

Известно, что проективная геометрия обладает свойством двойственности. Двойственная задача, задаче конкурса будет звучать так:

Для заданных n точек, найти минимальное количество прямых так чтоблы через каждую точку проходило ровно четыре прямых.

Но ведь эта задача легко решается! Берем квадрат mxm. Проводим через точки квадрата все вертикальные и горизонтальные линии. А также диоганальные линии (прямые и обратные). Тем самым через каждую точку будет проходить ровно четыре прямых. Если убрать точки из углов (они плохие), то получаются следующие решения задачи конкурса:
N=46 L=84!
N=52 L=105!
N=59 L=128!

Осталось только по двойственному решению найти решение для конкурса!

Покритикуйте идею. Конкурс закончился и нужна дополнительная мотивация опробовать идею.

[Pavlovsky]

Il brigante Pennastorta, победитель конкурса опубликовал описание своего алгоритма.

Как я понял. Он строит конструкцию в 3D пространтсве. Затем ее проектирует на плоскость таким образом, что бы образовалось максимальное количество линий с четырмя точками. Так же он во всю пользуется механизмом удаленных точек.

Забавно все свои решения Il brigante Pennastorta получил из двух 3D конструкций.

P1: (-1,-1,-1),(0,-2,-2),(1,-1,-1),(-2,0,-2),(0,0,-2),(2,0,-2),(-1,1,-1),(0,2,-2),(1,1,-1),
(-2,-2,0),(0,-2,0),(2,-2,0),(-2,0,0),(0,0,0),(2,0,0),(-2,2,0),(0,2,0),(2,2,0),(-1,-1,1),
(0,-2,2),(1,-1,1),(-2,0,2),(0,0,2),(2,0,2),(-1,1,1),(0,2,2),(1,1,1)
S1: (1,0,0),(0,1,0),(0,0,1),(1,1,1),(1,1,-1),(1,-1,1),(1,-1,-1)

P2: (0,0,0),(0,0,2),(0,0,4),(0,2,0),(0,2,2),(0,2,4),(0,4,0),(0,4,2),(0,4,4),(1,0,0),
(1,0,2),(1,0,4),(1,2,0),(1,2,2),(1,2,4),(1,4,0),(1,4,2),(1,4,4),(2,0,0),(2,0,2),(2,0,4),
(2,2,0),(2,2,2),(2,2,4),(2,4,0),(2,4,2),(2,4,4),(3,0,0),(3,0,2),(3,0,4),(3,2,0),(3,2,2),
(3,2,4),(3,4,0),(3,4,2),(3,4,4)
S2: (0,1,0),(0,0,1),(0,1,1),(0,1,-1),(1,0,2),(1,0,-2),(1,2,0),(1,-2,0)

P1S1 gave good results for N trees with 34<=N<=50, and P2S2 gave good results for N>=45

[alexBlack]

Source of the post
N=46 L=84

Наоборот, наверное - 84:46 - точки ведь станут прямыми при обратном преобразовании. У меня была такая реализация, там искать не проще, чем в прямом случае.