Новый конкурс программистов

[svb]

Nataly-Mak в сообщении #588239 писал(а):

А у вас есть какие-то оптимизации перебора? Ну, скажем, отсечение вариантов по каким-то критериям.
К тому же здесь ещё говорили о некоторой закономерности в первой строке - расстояния между одинаковыми цветами.
Вы всё это используете уже?

Допустим ищем диагонали 0 цвета. Без ограничения общности можно первый символ строки считать 0, следующий 0 выбираем - уже пара позиций строки дополнительно выкидывается из возможных для 0. Выбираем третий 0 - еще выкидываем позиции. И т.д. К сожалению, программу написал на живую нитку - честно говоря, очень плохо - об особой оптимизации говорить не приходится. Но количество вариантов даже для малых C зашкаливает, поэтому для больших C необходимы более разумные решения.

[Zealint]

Pavlovsky в сообщении #588153 писал(а):

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

Давайте называть тех людей, которые вышли за пределы джентльменского набора, "достраивателями" : ) Что-то мне кажется сомнительным, чтобы там какие-то регулярные решения были придуманы.

[Nataly-Mak]

Zealint

(Оффтоп)

любите вы подчёркивать ошибки так и лезет из вас преподаватель.
Я сделала ошибку, Pavlovsky её повторил...
Здесь вообще-то много делают ошибок, замучаетесь подчёркивать
Ладно, иностранцы пишут неграмотно, ещё неграмотнее пишут русские!

Насчёт "достраивателей" не согласна.
Я, например, достраиванием построила решение C=6, N=36x36, и оно получилось вполне регулярное.
Достроить можно многое. Например, ещё я получила достраиванием решение C=3, N=10x10 из решения N=9x9. Правда, сначала содрала его из какой-то статьи

-- Сб июн 23, 2012 23:25:46 --

Nataly-Mak в сообщении #587804 писал(а):

А по теореме для C=5 мы имеем прямоугольник 25х30 С-coloring. Значит, его надо просто достроить до прямоугольника 31х31 с использованием 6-го цвета.

Вот, осталось совсем немного:
1. построить прямоугольник 25х30 5-coloring;
2. достроить этот прямоугольник до 31х31 6-coloring.

Пункт 1 я выполнила. Правда, сделала это не по описанию в теореме 4.12, т. к. абсолютно ничего там не поняла.

Начала с С=3. Число 3 простое, следовательно, по теореме, которую я привела выше, существует прямоугольник 9х12 3-coloring. Вот этот прямоугольник:

A,A,A,B,B,B,C,C,C,B,A,C,B,B,B,C,C,C,A,A,A,B,A,C,C,C,C,A,A,A,B,B,B,B,A,C,A,B,C,B,C,A,C,A,B,A,C
,B,B,C,A,C,A,B,A,B,C,A,C,B,C,A,B,A,B,C,B,C,A,A,C,B,A,C,B,B,A,C,C,B,A,C,B,A,B,A,C,C,B,A,A,C,B,
C,B,A,C,B,A,A,C,B,B,A,C,C,B,A

Строила так: сначала записала квадрат 9х9 3-coloring, который раньше строила по описанию, приведённому Pavlovsky. Дальше не знала, где взять ещё 3 столбца и... пустила в ход достраивание в программе Эда.
Прямоугольник 9х12 получился быстро, причём эти недостающие 3 столбца нарисовались очень гармонично.

Ну, и далее совершенно аналогично построила прямоугольник 25х30 5-coloring только уже, конечно, без достраивания, т. к. уже поняла, какие должны быть недостающие 5 столбцов.

Ещё один рубеж взят.
Однако с достраиванием этого прямоугольника пока ничего не вижу регулярного. Надо думать дальше.

Pavlovsky
не подсказывать!

-- Сб июн 23, 2012 23:44:16 --

Вот он - прямоугольник 9х12 3-coloring:



Это ж надо как последние 3 столбца раскрасились
Трудно было догадаться.

-- Сб июн 23, 2012 23:56:58 --

У Алексея Чернова новый рекорд!

15 192 36864  Alex Chernov @ 16:04:06 on 06-23-2012 1

Вот молодец!
Если это и достраивание, то очень хитрое. Скорее всего, применяются какие-то эвристики. На тупом переборе здесь много не получишь.

С другой стороны, можно так рассуждать: с ростом C экспоненциально растёт количество вариантов для перебора, а следовательно, больше шансов "убить" все ошибки.
Но делать это надо всё равно как-то очень хитро.

[Zealint]

Nataly-Mak в сообщении #588334 писал(а):

Насчёт "достраивателей" не согласна.
Я, например, достраиванием построила решение C=6, N=36x36, и оно получилось вполне регулярное.

Я же специально пояснил, что "кто вышел за пределы". Вот там есть хоть одно решение за пределами нашего набора, которое регулярное? Мне кажется, что нет. Например, C=10, N=93. Какое оно? У меня получилось N=92, оно выглядит так, будто его всю ночь трясли. 93 я скоро тоже досчитаю, но его трясут уже две ночи и сегодняшнее утро.

(Оффтоп)

Цитата:

любите вы подчёркивать ошибки так и лезет из вас преподаватель.
Я сделала ошибку, Pavlovsky её повторил...
Здесь вообще-то много делают ошибок, замучаетесь подчёркивать
Ладно, иностранцы пишут неграмотно, ещё неграмотнее пишут русские!

Нет, я не всегда так делаю, просто иногда бывают опечатки, а иногда проявление ошибки носит характер незнания. И вот когда мне кажется, что имеет место незнание, я как бы намекаю. Нужно стараться быть грамотным, на каком бы языке не писал.

[Nataly-Mak]

Вы не поняли мою логику. Поясняю.
Я говорю о том, что к "достраивателям" можно отнести и тех, кто получает достраиванием регулярные решения, то есть они не вышли ни за какие пределы пока.

Кроме того, как я уже отметила, достраивать можно очень хитро с применением оптимизаций, как это, наверное, делает Алексей Чернов. Тогда не надо будет сутками "трясти"
У меня вообще нет программы достраивания, я достраиваю в программе Эда; разумеется, тут сутками трясти невозможно. Если быстро не достраивается, бросаю. Потом через некоторое время ещё пытаюсь. Тут очень интересный момент: всё зависит от случайного заполнения пристраиваемой строки и/или столбца. Один раз не удаётся достроить (плохо заполнились пристраиваемые строки/столбцы), а в другой раз довольно быстро удаётся. Так у меня было с достраиванием прямоугольника 31х36 6-coloring.
Ну, и конечно, для очень больших квадратов вручную достраивать вряд ли получится.

Мне очень понравилось вот это решение:



Чем не диагональное решение? Красота!

Работает метод составных квадратов.
Исходный квадрат - диагональное решение 16х16 4-coloring, конечный результат - 32х32 8-coloring.

Если взять за исходный квадрат диагональное решение 25х25 5-coloring, можно получить аналогичное решение 50х50 10-coloring.
Ну, и далее: 36х36 6-coloring --> 72x72 12-coloring.

[Zealint]

Цитата:

Вы не поняли мою логику. Поясняю.
Я говорю о том, что к "достраивателям" можно отнести и тех, кто получает достраиванием регулярные решения, то есть они не вышли ни за какие пределы пока.

Я понял Вашу логику ещё до того, как Вы написали тот пост, где не согласны. Но я имел ввиду, что не уверен в регулярности тех решений, которые за пределами набора. А как называть тех, кто в пределах набора - это неважно. Кто-то достраивает, кто-то нет. Кроме того, в слово "достраиватели" я ещё вкладывают тот факт, что решения лидеров совсем немного отличаются от решений, полученных известными методами. Например, когда для C=10 будет решение N=100, тогда можно предположить, что человек придумал что-то регулярное.

[Nataly-Mak]

Zealint в сообщении #588402 писал(а):

Например, когда для C=10 будет решение N=100, тогда можно предположить, что человек придумал что-то регулярное.

А ещё можно предположить, что человек два месяца крутил программу перебора только для C=10

Я придумала метод неперескающихся комбинаций. Однако никто не знает, сколько существует непересекающихся комбинаций из чисел 1,2,3,...,10.
На форуме nazva.net нашли набор из 50 непересекающихся комбинаций. Это предел?
Ответ на этот вопрос я так и не получила. Никто не знает?

И другой метод придумала: базовый алгоритм № 2 плюс лемма 4.3 (в усиленном варианте).
Но никто пока этим методом строить не пытается.

Pavlovsky собирался порыть в этом направлении...

Не уверена, что направление перспективное, но надо ведь пробовать.

А достраивание...
Pavlovsky писал, что у него табу на перебор на первые два месяца конкурса.
У меня табу на перебор на весь конкурс.
Не могу крутить сразу две долгоиграющие программы, тогда мне работать будет трудно. У меня постоянно крутится программа проверки потенциальных магических констант (и это ещё надолго!). Эта программа мне не мешает работать. Не хочу машину мучить, начав крутить вторую долгоиграющую программу перебора.

-- Вс июн 24, 2012 08:23:11 --

38  Jürgen Durst 6.788160 06-12-2012 @ 01:56:41
39  Justus Winter 6.069780 06-22-2012 @ 12:26:41
40  Daniel Lincke 5.810500 06-23-2012 @ 12:24:23
41  Vladimir Chirkov 5.801540 06-23-2012 @ 12:55:13
42  Gregor Heitkamp 5.537470 06-22-2012 @ 18:07:11
43  Vassili Skarine 5.195030 06-06-2012 @ 09:01:10
44  Eduard Baumann 5.052470 06-11-2012 @ 12:18:20
45  Rob Garretson 4.821810 06-07-2012 @ 08:19:11
46  Cyrus 4.792820 06-08-2012 @ 19:37:05
47  Kyle Jones 4.726690 06-16-2012 @ 11:05:45
48  Ray Hartung 4.384740 05-31-2012 @ 05:41:38

Ужас! Германцев, американцев толпа, прямо сплошными группами
Вот здесь среди 11 конкурсантов 4 германцев, 4 американцев и только один россиянин затесался.

[Pavlovsky]

Nataly-Mak в сообщении #588211 писал(а):

Предположу, что максимальное диагональное решение для C цветов имеет размер C^2xC^2.

Для получения оценки диагональных решений сверху, предлагаю решить следующую вспомогательную задачу.

Вспомогательная задача.
Найти N различных целых чисел таких что:
1) Для любых четырех чисел a1<a2<a3<a4, верно a4-a2<>a3-a1.
2) Для любых трех чисел a1<a2<a3, верно a3-a2<>a2-a1.
3) Среди всех наборов удовлетворяющих условиям 1,2 выбрать такое где максимальное число минимально. Обозначим его F(N).

Пример
F(1)=1 {1}
F(2)=2 {1,2}
F(3)=4 {1,2,4}
F(4)=8 {1,2,4,8}
F(5)=13? {1,2,4,8,13}
F(6)=21? {1,2,4,8,13,21}

Определим обратную функцию для F(N). f(M)=i, где i максимальный индекс для которого F(i)<M.

Лемма о существавании диагонального решения.
Обозначим G(С,M) - диагональное решение для квадрата MxM и С цветов.
Тогда G(С,M) не существует, если f(M)<M/C

Эта оценка достаточно грубая, Можно предложить более точную оценку. Но для первого приближения сойдет. Например для оценки возможности построения G(10,100), надо вычислить значение F(10). У меня получилось F(10)<=81. То есть потенциально возможно построить диагональное решение G(10,100), но все очень впритык.

-- Вс июн 24, 2012 12:13:12 --

Так долго писал. А гугл знает все

Mian-Chowla sequence (a B_2 sequence): a(1) = 1; for n>1, a(n) = smallest number > a(n-1) such that the pairwise sums of elements are all distinct.
http://oeis.org/A005282

1, 2, 4, 8, 13, 21, 31, 45, 66, 81, 97, 123, 148, 182, 204, 252, 290, 361, 401, 475, 565, 593, 662, 775, 822, 916, 970, 1016, 1159, 1312, 1395, 1523, 1572, 1821, 1896, 2029, 2254, 2379, 2510, 2780, 2925, 3155, 3354, 3591, 3797, 3998, 4297, 4433, 4779, 4851

-- Вс июн 24, 2012 13:01:30 --

Получается грубая оценка дает слишком общий результат. Могут существовать диагональные решения вплоть до теоретичской верхней оценки C^2+C-1.
Тогда будем оценивать верхнюю оценку более точно.
Диагональное решение NxN однозначно описывается числами в первой строке и в последней колонке. Выпишем эти числа в строку длинной 2N-1, назовем ее характеристической строкой.

Теорема. Для существования диагонального решения NxN необходимо и достаточно:
1) Чтобы для любых четырех номеров (i<j<k<l) одноцветных ячеек в характеристической строке, таких что l-j<N выполняется условие l-j<>k-i (или l+i<>k+j).
2) Чтобы для любых трех номеров (i<j<l) одноцветных ячеек в характеристической строке, таких что l-j<N выполняется условие l-j<>j-i (или l+i<>2j).

Решим вспомогательную задачу.
Расставим в характеристической строке, квадрата NxN максимально возможное количество символов 1, так чтобы выполнялись условия выше приведенной теоремы для пометки 1. Обозначим количство единиц F(N).

Пример.
F(1)=1 {1}
F(2)=2 {1,2}
....
F(9)=6 {1,2,4,10,11,13}
F(10)=6 {1,2,4,11,12,14}

Лемма о существовании диагонального решения.
Диагональное решение G(С,N) не существует, если F(N)<(2N-1)/C

Пример
G(3,9) 6 > 17/3 решение может существовать
G(3,10) 6 < 19/3 решение не существует

[Nataly-Mak]

Pavlovsky в сообщении #588417 писал(а):

Пример
G(3,9) 6 > 17/3 решение может существовать

И оно существует! Его привёл svb.
А я покажу иллюстрацию. Красивое решение!

[Nataly-Mak]

Итак, я продолжаю думать над реализацией метода, вытекающего из приведённой мной теоремы.
Выше показала прямоугольник 9х12 3-coloring. Теорема утверждает, что для С=3 такой прямоугольник существует. Да, действительно, он существует, я его построила и показала.
Далее построила уже прямоугольник 25х30 5-coloring и прямоугольник 81х90 9-coloring.

Теперь надо достроить 3-цветный прямоугольник 9х12 до 4-цветного квадрата 13х13 и соответственно 5-цветный прямоугольник 25х30 до 6-цветного квадрата 31х31, 9-цветный прямоугольник 81х90 до 10-цветного квадрата 91х91.

Как здесь говорилось, все эти достраивания возможны и выполняются очень легко по какой-то закономерности. Я пока не вижу, как же выполнить достраивание.
Предположу, что я не так построила исходные прямоугольники, которые надо достраивать. А может быть, и так построила, но закона достраивания всё равно не вижу

Ну, даже лидер конкурса dimkadimon не сразу увидел этот закон, где уж мне сразу увидеть
Подумаю ещё, может, что и придёт в голову. Осталось сделать последний шаг.

Прямоугольник 9х12 3-coloring достроила в программе Эда до квадрата 13х13 4-coloring. Достроился легко, однако никакой особой регулярности я в этом достраивании не вижу.



Конечно, достраивать прямоугольник 81х90 до квадрата 91х91 вручную - занятие глупое.
Квадрат 31х31 6-coloring мне не нужен, т.к. у меня есть уже решение 36х36 для C=6.
Построить следующие прямоугольники не проблема: 11-цветный 121х132, 13-цветный 169х182, 17-цветный 289х306, 19-цветный 361х380. Надо понять, как их достраивать.

Решения для С=10,12,14,18,20 уже очень близко и всё ещё бесконечно далеко

Кстати, например, 9-цветный прямоугольник 81х90 элементарно достраивается до решения С=10, N=82х82 (пристроить строку цвета 10), но такое решение у меня уже есть.

-- Вс июн 24, 2012 14:44:26 --

Эх, покажу прямоугольник 25х30 5-coloring.
Вдруг ещё кто-нибудь мучается с этим методом, иллюстрация моя вдруг ему и поможет.
Это всего лишь пример, иллюстрирующий известную теорему. Ничего сектретного



А красивый прямоугольник!

[Nataly-Mak]

А всё-таки, наверное, неправильно я построила прямоугольники
Они С-coloring, но структура в них не такая, как надо там по теореме 4.12, чёрт бы её побрал!

Вот второй вариант прямоугольника 9х12 3-coloring. Последние 3 столбца тоже получила достраиванием в программе Эда.
Ну и чем этот вариант лучше (хуже) предыдущего? Всё равно непонятно, как его достраивать до квадрата 13х13 4-coloring.



Могу сделать ещё и третий вариант этого прямоугольника.

[svb]

Любителям красоты

(Оффтоп)

A,A,A,A,A,B,B,B,B,B,C,C,C,C,C,D,D,D,D,D,E,E,E,E,E,A,B,C,D,E,
A,B,C,D,E,B,C,D,E,A,C,D,E,A,B,D,E,A,B,C,E,A,B,C,D,E,A,B,C,D,
A,C,E,B,D,B,D,A,C,E,C,E,B,D,A,D,A,C,E,B,E,B,D,A,C,D,E,A,B,C,
A,D,B,E,C,B,E,C,A,D,C,A,D,B,E,D,B,E,C,A,E,C,A,D,B,C,D,E,A,B,
A,E,D,C,B,B,A,E,D,C,C,B,A,E,D,D,C,B,A,E,E,D,C,B,A,B,C,D,E,A,
B,B,B,B,B,C,C,C,C,C,D,D,D,D,D,E,E,E,E,E,A,A,A,A,A,A,B,C,D,E,
B,C,D,E,A,C,D,E,A,B,D,E,A,B,C,E,A,B,C,D,A,B,C,D,E,E,A,B,C,D,
B,D,A,C,E,C,E,B,D,A,D,A,C,E,B,E,B,D,A,C,A,C,E,B,D,D,E,A,B,C,
B,E,C,A,D,C,A,D,B,E,D,B,E,C,A,E,C,A,D,B,A,D,B,E,C,C,D,E,A,B,
B,A,E,D,C,C,B,A,E,D,D,C,B,A,E,E,D,C,B,A,A,E,D,C,B,B,C,D,E,A,
C,C,C,C,C,D,D,D,D,D,E,E,E,E,E,A,A,A,A,A,B,B,B,B,B,A,B,C,D,E,
C,D,E,A,B,D,E,A,B,C,E,A,B,C,D,A,B,C,D,E,B,C,D,E,A,E,A,B,C,D,
C,E,B,D,A,D,A,C,E,B,E,B,D,A,C,A,C,E,B,D,B,D,A,C,E,D,E,A,B,C,
C,A,D,B,E,D,B,E,C,A,E,C,A,D,B,A,D,B,E,C,B,E,C,A,D,C,D,E,A,B,
C,B,A,E,D,D,C,B,A,E,E,D,C,B,A,A,E,D,C,B,B,A,E,D,C,B,C,D,E,A,
D,D,D,D,D,E,E,E,E,E,A,A,A,A,A,B,B,B,B,B,C,C,C,C,C,A,B,C,D,E,
D,E,A,B,C,E,A,B,C,D,A,B,C,D,E,B,C,D,E,A,C,D,E,A,B,E,A,B,C,D,
D,A,C,E,B,E,B,D,A,C,A,C,E,B,D,B,D,A,C,E,C,E,B,D,A,D,E,A,B,C,
D,B,E,C,A,E,C,A,D,B,A,D,B,E,C,B,E,C,A,D,C,A,D,B,E,C,D,E,A,B,
D,C,B,A,E,E,D,C,B,A,A,E,D,C,B,B,A,E,D,C,C,B,A,E,D,B,C,D,E,A,
E,E,E,E,E,A,A,A,A,A,B,B,B,B,B,C,C,C,C,C,D,D,D,D,D,A,B,C,D,E,
E,A,B,C,D,A,B,C,D,E,B,C,D,E,A,C,D,E,A,B,D,E,A,B,C,E,A,B,C,D,
E,B,D,A,C,A,C,E,B,D,B,D,A,C,E,C,E,B,D,A,D,A,C,E,B,D,E,A,B,C,
E,C,A,D,B,A,D,B,E,C,B,E,C,A,D,C,A,D,B,E,D,B,E,C,A,C,D,E,A,B,
E,D,C,B,A,A,E,D,C,B,B,A,E,D,C,C,B,A,E,D,D,C,B,A,E,B,C,D,E,A,
A,B,C,D,E,A,B,C,D,E,A,B,C,D,E,A,B,C,D,E,A,B,C,D,E,@,@,@,@,@,
E,A,B,C,D,E,A,B,C,D,E,A,B,C,D,E,A,B,C,D,E,A,B,C,D,@,@,@,@,@,
D,E,A,B,C,D,E,A,B,C,D,E,A,B,C,D,E,A,B,C,D,E,A,B,C,@,@,@,@,@,
C,D,E,A,B,C,D,E,A,B,C,D,E,A,B,C,D,E,A,B,C,D,E,A,B,@,@,@,@,@,
B,C,D,E,A,B,C,D,E,A,B,C,D,E,A,B,C,D,E,A,B,C,D,E,A,@,@,@,@,@

[Nataly-Mak]

А почему угол пустой?

[svb]

Если бы мне удалось вставить туда хотя бы одну клетку, то я бы получил новый рекорд

[Nataly-Mak]

Так, стоп!
Кажется, у меня точно крыша поехала
Я строю прямоугольник 25х30 5-coloring и пытаюсь достроить его до квадрата 31х31, но ведь уже с использованием ещё одного цвета. Так куда же мне этот цвет совать???
Да, у меня тоже получались варианты с пустым подквадратом 5х5, аналогичные вашему.

Но ведь квадрата 30х30 5-coloring не существует!
Ох! значит, 6-ой цвет надо куда-то в квадрат 30х30 совать. Ну да, было бы куда проще заполнить 6-ым цветом 31-ую строку и 31-ый столбец. Увы, это невозможно.

Впрочем, при достраивании прямоугольника 9х12 3-coloring до квадрата 13х13 4-coloring в программе Эда четвёртый цвет и рассовался внутрь квадрата 12х12 (ибо квадрата 12х12 3-coloring тоже не существует). Но не вижу никакой закономерности в этом достраивании!

Пробовала по-разному 6-ой цвет добавлять внутрь квадрата 31х31 (но не внутрь прямоугольника 25х30!), ничего не получается
Заколдованный круг.

-- Вс июн 24, 2012 22:14:44 --

Вот пример достраивания второго варианта прямоугольника 9х12 3-coloring до квадрата 13х13 4-coloring в программе Эда:

13,13,A,A,A,B,B,B,C,C,C,C,A,B,D,A,C,B,B,A,C,C,B,A,B,C,A,C,A,B,C,B,C,A,C,A,B,A,B,C,A,B,B,B,C,
C,C,A,A,A,C,A,B,B,B,A,C,C,B,A,A,C,B,B,C,A,D,B,C,A,C,A,B,A,B,C,A,B,C,D,C,C,C,A,A,A,B,B,B,C,A,
B,D,C,B,A,A,C,B,B,A,C,B,C,A,D,C,A,B,A,B,C,B,C,A,A,B,C,D,C,A,D,C,A,D,C,A,D,B,B,B,D,D,C,B,A,C,
B,A,C,D,D,D,D,A,A,D,D,A,D,B,D,D,B,C,D,C,C,D,B,C,D,B,D,D,B,C,A,A,A,C

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

-- Вс июн 24, 2012 22:41:24 --

Аналогично, с пустым подквадратом (достраивание прямоугольника 9х12 3-coloring до квадрата 12х12):

A,A,A,B,B,B,C,C,C,C,A,B,A,C,B,B,A,C,C,B,A,B,C,A,A,B,C,B,C,A,C,A,B,A,B,C,B,B,B,C,C,C,A,A,A,C,A
,B,B,A,C,C,B,A,A,C,B,B,C,A,B,C,A,C,A,B,A,B,C,A,B,C,C,C,C,A,A,A,B,B,B,C,A,B,C,B,A,A,C,B,B,A,C,
B,C,A,C,A,B,A,B,C,B,C,A,A,B,C,B,A,C,B,A,C,B,A,C,@,@,@,A,C,B,A,C,B,A,C,B,@,@,@,C,B,A,C,B,A,
C,B,A,@,@,@