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

[Pavlovsky]

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

вы не пробовали искать прямоугольные базовые матрицы?К найденной вами базовой матрице 8х8 для С=10 наверняка можно добавить ещё одну строку.

Пробовал и 8х9 и 9х8. Не нашел.

[Nataly-Mak]

Тогда, возможно, последняя строка в базовой матрице добавлена с игнорированием небольшого количества возникших ошибок. Ведь дальше всё равно применяется "вытряхивание" ошибок.

alexBlack тоже пишет в своей статье о максимальной матрице 8х8 (C=10) для блоков с циклическим сдвигом. Он сделал полный перебор. Значит, ваш результат правильный и больше матрицы 8х8 найти ничего не удастся (без ошибок) для блоков данного вида.

[Pavlovsky]

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

Тогда, возможно, последняя строка в базовой матрице добавлена с игнорированием небольшого количества возникших ошибок. Ведь дальше всё равно применяется "вытряхивание" ошибок.

Эксперименты многих участников конкурса, показали регулярные решения трясутся плохо.

К тому же зачем, перед тряской, пытаться что то добавить к матрице 8х8?! Когда можно сразу начать трясти исходную матрицу 8х8.

-- Чт окт 11, 2012 09:10:14 --

Может порешать вспомогательную задачу?! Известно для С=p^s можно построить прямоугольники (C^2)x(C^2+C) и (C^2+C)x(C^2). И даже квадрат (C^2+C)x(C^2+C) с вырезанным углом CxC.

А можно ли нечтно подобное построить для С=6? Для С=6 пока лучшим результатом является решение 37х36. Можно ли его улучшить? Например построить прямоугольник 36х42??

-- Чт окт 11, 2012 09:32:15 --

Может порешать вспомогательную задачу?! Известно для С=p^s можно построить прямоугольники (C^2)x(C^2+C) и (C^2+C)x(C^2). И даже квадрат (C^2+C)x(C^2+C) с вырезанным углом CxC.

А можно ли нечтно подобное построить для С=6? Для С=6 пока лучшим результатом является решение 37х36. Можно ли его улучшить? Например построить прямоугольник 36х42??

[Nataly-Mak]

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

Эксперименты многих участников конкурса, показали регулярные решения трясутся плохо.

Как я поняла, и dimkadimon, и Zealint "трясли" именно регулярные решения.
Zealint, например, в самом начале сообщал, как он "тряской" получил из регулярного решения C10N90 решение C10N91, а затем и C10N92.
А dimkadimon, кажется, вообще начинал "трясти" регулярное решение C9N81.

Цитата:

К тому же зачем, перед тряской, пытаться что то добавить к матрице 8х8?! Когда можно сразу начать трясти исходную матрицу 8х8.

Zealint писал не так давно (уже после окончания конкурса), что "трясти" большой прямоугольник (скажем, 94х100), содержащий лишние строки (столбцы) эффективнее, чем квадратное решение, например, 90х90, в котором надо добавлять 4 строки и 4 столбца. Это и понятно.

Ну, я посмотрела на решение C10N94 Zealint и мне показалось, что структура решения именно такая. Внизу хорошо видно обрезанное обрамление.

Цитата:

А можно ли нечтно подобное построить для С=6? Для С=6 пока лучшим результатом является решение 37х36. Можно ли его улучшить? Например построить прямоугольник 36х42??

У меня есть решение 36х48 для С=6, но только с "дырками".

(Оффтоп)

[dimkadimon]

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

Как я поняла, и dimkadimon, и Zealint "трясли" именно регулярные решения.
Zealint, например, в самом начале сообщал, как он "тряской" получил из регулярного решения C10N90 решение C10N91, а затем и C10N92.
А dimkadimon, кажется, вообще начинал "трясти" регулярное решение C9N81.

Я получил своё первое C10N93 тряся C9N81. Pavlovsky прав, трясти решение в которых есть регулярность (например диагональные решения или решения которые построены из strong решений) гораздо сложнее. Это потому что в таких решениях всё уже "на своих местах" и они в глубоком локальном минимуме. Чтобы выбраться из этого минимума надо делать большие шаги, а это сложнее потому что таких шагов больше и шанс наткнуться на правильный шаг тогда меньше.

Насчёт 36х42. Я даже не могу найти 36х38 где меньше 36 ошибок.

[Nataly-Mak]

dimkadimon в сообщении #629428 писал(а):

Pavlovsky прав, трясти решение в которых есть регулярность (например диагональные решения или решения которые построены из strong решений) гораздо сложнее. Это потому что в таких решениях всё уже "на своих местах" и они в глубоком локальном минимуме. Чтобы выбраться из этого минимума надо делать большие шаги, а это сложнее потому что таких шагов больше и шанс наткнуться на правильный шаг тогда меньше.

И тем не менее, и вы, и Zealint "трясли" же регулярные решения и "вытрясли" из них то, что нужно

Цитата:

Насчёт 36х42. Я даже не могу найти 36х38 где меньше 36 ошибок.

У меня аналогично.

[dimkadimon]

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

И тем не менее, и вы, и Zealint "трясли" же регулярные решения и "вытрясли" из них то, что нужно

Не совсем так. Опять я не знаю что вы имеете ввиду под регулярное...

Из диагональных решений я ничего не получил.
Из матричных решений я ничего не получил.
C10N94 я не смог получить от C10N93, которое основано на C9N81. Но вроде zealint смог. Я его получил на основе диагональной 85-строчки Pavlovsky. Так же я не смог получить C12N136 и C14N186.

[Nataly-Mak]

dimkadimon
а вот вам контрпример
Вы получили решение C10N93 "тряской" регулярного решения С9N81. Это раз.
Далее, решение С10N93 у вас получилось нерегулярное, потому что вы его получили "тряской". Однако из этого нерегулярного решения вы почему-то не "вытрясли" решение С10N94. Это два.
Для получения решения С10N94 вы взяли 85-символьную строку Pavlovsky, которая очень даже регулярный strong 10-cоloring прямоугольник 85х10, только немножко с "дырками":



Реплицировали эту полосу (или часть её), получили большой, довольно регулярный прямоугольник 94х100 (или 95х100) с ошибками и из этого прямоугольника "вытрясли" решение С10N94.
Это три

-- Чт окт 11, 2012 11:00:17 --

dimkadimon в сообщении #629439 писал(а):

Опять я не знаю что вы имеете ввиду под регулярное...

А вы что имеете в виду под "регулярное"?

Цитата:

C10N94 я не смог получить от C10N93, которое основано на C9N81.
Но вроде zealint смог. Я его получил на основе диагональной 85-строчки Pavlovsky. Так же я не смог получить C12N136 и C14N186.

Вот именно об этом я уже и написала выше.

Конечно, у меня небольшой опыт "тряски" и очень большие прямоугольники я не "трясла".
Но вот, например, от регулярного решения 32х36 6-coloring элементарно получила "тряской" решение третьего класса С6N33 (всего за несколько минут). Этот пример я привела в книге.

Так что, я не совсем понимаю, о каких экспериментах участников конкурса говорит Pavlovsky, если сам он ничего не "тряс", а известные нам конкурсанты с большим успехом "трясли" именно регулярные решения.

[Pavlovsky]

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

Для получения решения С10N94 вы взяли 85-символьную строку Pavlovsky, которая очень даже регулярный strong 10-cоloring прямоугольник 85х10, только немножко с "дырками":

Строка немного длиннее и дырок в ней больше

(Оффтоп)

Получился прямоугольник со срезанными углами. Поэтому она хорошо трясется, что в ней есть много полузаполненных строк (от почти заполненных, до почти пустых).

[Nataly-Mak]

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

Строка немного длиннее и дырок в ней больше

Ну, это, кто что получил. Я получила такую полосу. В этой полосе вся ваша строка, то есть все 85 символов.

Хорошо трясётся не сама эта полоса, а полученный из неё репликацией большой и довольно регулярный прямоугольник. Именно такой прямоугольник "тряс" dimkadimon.

Кстати, посмотрите на решение C10N94 dimkadimon; по-моему, у него полоса как раз такая, как у меня.

[Nataly-Mak]

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

Получился прямоугольник со срезанными углами. Поэтому она хорошо трясется, что в ней есть много полузаполненных строк (от почти заполненных, до почти пустых).

А что мешает в любом регулярном решении искусственно сделать такие же полузаполненные строки??

[dimkadimon]

А где форум для нового соревнования?

[Nataly-Mak]

dimkadimon
да форум будет этот же. Может быть, тему открою новую, или кто-то другой откроет.

А у меня такой вопрос: когда по московскому времени начнётся новый конкурс?
Это будет сегодня (12 октября) в 20.00? Или это будет в другое время? Ни черта не понимаю

-- Пт окт 12, 2012 05:49:45 --

Сейчас на главной странице конкурса вижу:



Столько осталось до начала нового конкурса. Это "моё" время?
Если "моё", то конкурс для меня начнётся сегодня (12 октября) в 20.00.

-- Пт окт 12, 2012 05:55:24 --

Вопреки всем прогнозам, моим и whitefox, программа поиска не строго диагонального решения C5N25 работает уже 249 часов. Базовый вектор на данный момент:

1 2 3 4 5 3 1 5 5 2 1 ...

[Nataly-Mak]

Счётчик времени на главной странице конкурса уже обнулился, а конкурса нет
Неправильно счётчик работает!
Значит, всё-таки конкурс начнётся завтра в 4.00 по московскому времени.

-- Пт окт 12, 2012 20:55:11 --

Да, администратор Neil Brewer разослал всем участникам прошлого конкурса письмо. Я получила письмо в 19.13 по московскому времени. В письме сообщается, что очередной конурс начнётся менее чем за 9 часов.
Всё правильно. Ложусь спать, завтра встану пораньше, чтобы посмотреть начало нового конкурса

-- Пт окт 12, 2012 21:20:31 --

Возвращаясь к теме о 10-сильных прямоугольниках...

Я нашла два strong 10-coloring прямоугольника 85х10 с 15 ошибками (оба они приведены в книге).
Собралась превратить один из них в прямоугольник с "дырками", обнаружила, что удалила эту программу (балда!).
Помог whitefox, у него тоже есть такая программа.
Получился strong 10-coloring прямоугольник с 10 "дырками":



Этому прямоугольнику соответствует комплект из 10 попарно ортогональных обобщённых латинских прямоугольников 9х10 с неполной последней строкой (5 элементов содержится в строке) и с 10 незаполненными ячейками, соответствующими "дыркам" (в этих ячейках стоит символ 'x'):

(Оффтоп)

№1
6 5 1 8 9 4 7 3 10 4
3 8 9 5 6 7 1 10 1 5
4 8 7 6 10 9 3 6 10 1
5 7 4 9 3 8 3 4 8 7
10 2 5 9 1 8 3 10 1 4
5 6 9 7 4 9 6 10 1 8
3 7 5 10 1 3 4 9 5 7
6 8 5 1 10 7 3 4 8 2
9 2 10 2 6     

№2
1 1 1 1 1 1 1 1 1 2
2 2 2 2 2 2 2 2 3 10
10 10 10 3 3 10 3 4 4 4
4 4 4 4 4 4 5 5 5 5
5 5 5 5 5 6 6 6 6 6
6 6 6 6 7 7 7 7 7 7
7 7 7 8 8 8 8 8 8 8
8 8 9 9 9 9 9 9 9 9
9 3 10 2 10     

№3
5 8 1 9 6 2 7 3 4 8
7 5 3 10 1 6 9 2 6 1
5 3 2 7 9 8 10 2 3 8
6 5 7 1 9 10 8 9 6 10
1 3 5 2 7 7 2 5 3 1
9 6 10 8 10 7 9 8 5 1
6 3 2 6 2 1 3 5 7 9
10 8 3 4 7 1 5 6 2 8
9 4 10 х х     

№4
9 7 2 10 1 8 4 3 6 4
10 6 2 1 8 9 7 3 10 6
7 9 1 2 8 3 4 10 7 9
8 3 6 4 1 2 8 2 4 7
9 1 5 6 3 8 9 4 6 1
3 7 5 2 9 7 4 5 1 3
6 8 2 2 4 7 10 8 9 6
3 1 4 8 1 10 2 3 7 6
9 5 10 х 5

№5
2 4 9 6 8 1 7 5 3 6
4 8 1 2 5 3 7 9 1 7
5 4 6 3 8 2 9 8 2 5
6 4 9 3 1 7 3 2 5 1
6 7 9 4 8 2 7 1 10 4
3 9 5 8 8 10 4 7 3 1
2 9 5 4 2 8 3 7 1 5
6 9 8 4 5 2 6 7 3 1
9 6 10 10 1     

№6
2 8 10 1 5 9 6 3 4 4
5 7 6 9 1 3 2 8 8 5
6 4 2 9 3 7 1 6 1 5
10 9 2 8 4 3 2 5 9 7
6 8 3 1 4 8 7 5 9 3
6 4 2 1 8 3 10 9 1 2
6 5 4 2 3 9 7 4 1 8
5 6 2 6 7 4 8 1 5 3
9 7 10 х х     

№7
6 2 8 1 7 3 5 4 9 6
9 4 2 8 5 3 7 1 6 3
9 8 4 1 2 5 7 8 3 1
9 10 2 4 5 6 8 4 2 1
7 9 5 6 3 10 2 8 5 1
6 4 3 9 5 8 3 4 2 9
1 6 7 5 9 6 7 1 4 8
2 3 1 4 6 2 3 8 5 10
9 8 10 х 7     

№8
1 4 7 8 9 5 3 2 6 2
7 10 1 3 6 8 5 9 6 2
9 5 7 4 3 8 1 2 7 3
1 6 8 5 4 9 9 6 7 2
4 8 5 3 1 2 6 8 9 1
7 3 4 5 7 6 9 1 2 3
5 4 8 2 10 8 3 7 9 1
5 6 6 8 5 9 3 10 1 7
2 х 10 4 х     

№9
4 5 3 1 6 8 9 2 7 3
8 9 7 1 10 5 2 4 9 4
1 6 7 2 3 8 5 5 9 7
2 3 10 1 4 8 9 5 4 6
8 3 7 2 1 7 1 2 5 9
10 8 3 4 2 4 7 6 8 5
3 1 9 1 6 7 4 5 3 8
9 2 8 4 5 2 6 7 3 1
9 10 10 6 х     

№10
7 9 4 3 2 1 6 10 8 2
7 1 5 10 9 4 8 6 10 5
4 6 9 2 7 8 1 8 2 1
6 5 10 7 4 9 3 6 8 7
10 1 2 4 9 4 2 9 7 8
1 5 6 10 5 1 10 4 6 2
9 8 7 1 5 6 9 10 8 2
4 7 4 2 3 1 8 7 10 6
9 5 х 3 3

Вот так! Всего 10 ячеек не удаётся заполнить, чтобы получить комплект из 10 попарно ортогональных прямоугольников 9х10.

[Nataly-Mak]

Всё!!!
Программа поиска не строго диагонального решения C5N25 закончила работать, работала 263 часа 18 минут с какими-то ещё секундами. Решение не найдено.
Базовый вектор за несколько секунд до финиша имел вид:

1 2 3 4 5 5 4 5 4 3 2 ...

Как говорил maxal, для того чтобы утверждать с уверенностью на 100%, что решения не существует, нужна вторая независимая проверка.
Кто отважится?

А я завтра собираюсь запустить программу поиска не строго диагонального решения C5N26.