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

[Nataly-Mak]

Никто не вносит ясность по поводу третьего базового (ключевого) алгоритма

Запостила сообщение на форуме конкурса:

Цитата:

The competitive problem is easily solved with the help of Mutually Orthogonal Latin Squares (MOLS).
This algorithm can be applied to C = p ^ k, p - prime number, k> = 1.
The algorithm gives a solution of C ^ 2xC ^ 2.
Quite a large number of decisions: C = 3,4,5,7,8,9,11,13,16,17,19.
MOLS can be found here: http://www.natalimak1.narod.ru/grolk.htm
and then the second part of the article.
I do not know whether there is a well-known algorithm for the C = p ^ k +1, p - prime number, k> = 1.
At the forum saying that there is: post581176.html
The forum report that the algorithm gives a solution to C ^ 2-C +1.
This algorithm is suitable for C = 6,10,12,14,18,20.

For C = 6, N = 31x31 I found the solution in another way, who came up with herself.

Может быть, там кто-нибудь "расколется".

Оно, конечно, и правильно: нечего всем рассказывать про известные алгоритмы

[Nataly-Mak]

Сильно подозреваю, что алгоритм для C=6 есть в первой статье, приведённой на главной странице конкурса:
http://www.cs.umd.edu/~gasarch/papers/grid.pdf

Сейчас опять открыла эту статью, читать, конечно, не умею

(Кстати, один коллега по моей просьбе перевёл эту статью в Гугле. Мама дорогая! Это совершенно невозможно читать! Математические формулы вообще все превратились в какой-то винегрет, всё сикись-накись и вообще ничего абсолютно непонятно.
Да-а-а... Переводить математические тексты Google не умеет никак!)

Так что открываю оригинал и тупо смотрю в него

Первое, что вроде поняла:
если построить G36,12 strongly-(6,2)-colorable, то из него можно получить
G36,36 6-colorable

или

если построить G36,18 strongly-(6,3)-colorable, то из него можно получить
G36,36 6-colorable

[могла напутать; не принимать это, как окончательные справедливые утверждения!]

Это уже кое-что даёт. Можно искать не наборы непересекающихся комбинаций, как я это делаю, а искать несколько другие комбинации. Однако комбинации становятся очень длинными, не размера 6, а размера 12 или 18.

"Читаю" дальше...

Example 4.6

вижу такие разбиения:

|1|2|3|
|6|5|4|

|1|6|2|
|5|4|3|

|1|5|6|
|4|3|2|

|1|4|5|
|3|2|6|

|1|3|4|
|2|6|5|

Здесь участвуют как раз 6 цветов. Не являются ли эти разбиения ключом к алгоритму для C=6 (а также и для C=10,12,14,18,20)?

Это я сама себя спрашиваю.
Участники дискуссии пусть не волнуются, что надо отвечать на мои вопросы.
Попробую сама разобраться. Получится - хорошо, не получится - тоже неплохо

Ну, и сообщение делаю с такой целью: вдруг это кому-то поможет выйти на нужный путь.
Для тех, кто ещё не нашёл алгоритм для C=6,10,12,14,18,20.

-- Вс июн 17, 2012 05:49:53 --

Вот фрагмент перевода данной статьи в Google:



-- Вс июн 17, 2012 06:23:12 --

Кстати, в статье приведён пример к Лемме 4.3.

Это G8,6 strong-(6,2)-coloring:

1 1 2 2 3 6
1 2 1 2 4 5
2 1 2 1 5 4
2 2 1 1 6 3
3 4 5 6 1 2
4 5 6 4 1 1
5 6 3 3 1 2
6 3 4 5 1 2

Далее из этого прямоугольника получается по лемме G8,18 6-coloring.

Вроде всё правильно поняла.

[Nataly-Mak]

Далее пытаюсь сама сочинить пример.

Делаю выборку из приведённого в статье прямоугольника 8х28 strong-(5,3)-coloring.
Если не наврала, у меня получился такой G5,13 strong-(4,2)-coloring:

1 1 1 1 1 1 3 2 3 3 2 2 2
1 2 2 2 2 2 1 1 4 4 3 3 2
2 1 3 3 3 3 2 2 1 1 1 4 1
2 2 1 4 4 4 3 3 2 2 2 1 1
4 3 4 3 2 1 4 4 1 3 3 2 4

Теперь можно применить указанную выше лемму и получить G5,26 4-coloring.
Этот G5,26 я построила, проверить негде. Сейчас попробую скормить его программе Эда, он небольшой, может быть, проверится...

Ах, нет, наврала... Вижу повторение пары чисел (3,2). А эти числа не имеют права повторяться. Так что, выборка осталась strong-(4,3)-coloring. Лемму применить к этому прямоугольнику нельзя.

Но суть ясна теперь.

Если удалить четвёртую строку сверху, может быть, получится strong-(4,2)-coloring?

Нет, увы, всё равно не получится

А! надо удалить ещё предпоследний столбец.
Так получится G4,12 strong-(4,2)-coloring?

Нет, и так не получается, пара (3,1) повторяется.

[Nataly-Mak]

Желающих высказаться нет, тогда я продолжу
Ещё попытка...
Беру опять часть прямоугольника 8х28 strong-(5,3)-coloring из статьи:

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

Это G8,18 strong-(5,3)-coloring.
Комбинации хорошие, длиной 18, как раз, то что нам нужно. А вот цветов пока только 5. Но добавить цвет не проблема.
Добавляю навскидку такую комбинацию:

1 6 3 2 6 6 6 6 2 6 3 6 6 6 6 6 6 6

Теперь у нас 6 цветов и G9,18 strong-(6,3)-coloring.

Не наврала? Могла ошибиться при добавлении 9-ой строки.

Вот, 9 нужных комбинаций длины 18 уже есть. А нам надо 36 таких комбинаций.
Если это сделать возможно, то решение G36,36 6-coloring должно получиться из G36,18 strong-(6,3)-coloring по лемме 4.3.

Пока можно получить только G9,36 6-coloring (при условии, что я правильно составила G9,18 strong-(6,3)-coloring).

Скорее всего, с таким исходным прямоугольником составить 36 нужных комбинаций не удастся. Надо в первые 8 строк тоже вставить число 6.

Да и вообще возможно ли построение G36,18 strong-(6,3)-coloring?
Я пока не знаю ответ на этот вопрос.

[Nataly-Mak]

А, вот нашла в статье



По лемме 4.3 из этого прямоугольника можно получить G6,30
4-coloring.

Сейчас попробую этот прямоугольник нарисовать

-- Вс июн 17, 2012 14:42:30 --

Вот нарисовала G6,30 4-coloring:

1,1,1,1,1,3,3,3,2,3,3,2,2,2,2,3,3,3,3,3,1,1,1,4,1,1,4,4,4,4,
1,2,2,2,2,1,1,1,1,4,4,3,3,3,2,3,4,4,4,4,3,3,3,3,2,2,1,1,1,4,
2,1,3,3,2,1,2,2,2,1,1,1,4,4,3,4,3,1,1,4,3,4,4,4,3,3,3,2,2,1,
2,2,1,4,3,2,1,4,3,1,2,2,1,1,4,4,4,3,2,1,4,3,2,1,3,4,4,3,3,2,
3,3,2,1,4,2,2,1,4,2,1,4,1,2,1,1,1,4,3,2,4,4,3,2,4,3,2,3,4,3,
4,4,4,2,1,4,4,2,1,2,2,1,2,1,1,2,2,2,4,3,2,2,4,3,4,4,3,4,3,3

Вроде всё верно получилось.

[Nataly-Mak]

Да, этот прямоугольник правильный.
Сам Эд проверил

Кстати, мне подсказали на форуме конкурса простой способ проверить в программе Эда прямоугольник: надо добавить к нему несколько строк, чтобы он стал квадратом.
При проверке будут видны ошибки в верхней части квадрата, то есть именно в проверяемом прямоугольнике.

[Nataly-Mak]

Продолжила эксперимент с прямоугольником 9х18 strong-(6,3)-coloring, расширила его по лемме 4.3 до прямоугольника 9х36 6-coloring:

1,1,1,1,1,1,1,5,5,5,5,3,2,4,3,4,3,2,3,3,3,3,3,3,3,1,1,1,1,5,4,6,5,6,5,4,
1,2,2,2,2,2,2,1,1,1,1,1,1,5,4,5,4,3,3,4,4,4,4,4,4,3,3,3,3,3,3,1,6,1,6,5,
2,1,3,3,3,3,2,1,2,2,2,2,2,1,1,1,1,1,4,3,5,5,5,5,4,3,4,4,4,4,4,3,3,3,3,3,
2,2,1,4,4,4,3,2,1,3,3,3,3,1,2,2,2,2,4,4,3,6,6,6,5,4,3,5,5,5,5,3,4,4,4,4,
3,3,2,1,5,3,3,2,2,1,4,4,4,2,1,3,3,3,5,5,4,3,1,5,5,4,4,3,6,6,6,4,3,5,5,5,
3,4,3,2,1,5,4,3,3,2,1,5,3,2,2,1,5,4,5,6,5,4,3,1,6,5,5,4,3,1,5,4,4,3,1,6,
4,3,4,3,2,1,5,3,4,3,2,1,5,3,3,2,1,5,6,5,6,5,4,3,1,5,6,5,4,3,1,5,5,4,3,1,
5,5,5,5,3,2,1,4,3,4,3,2,1,3,5,3,2,1,1,1,1,1,5,4,3,6,5,6,5,4,3,5,1,5,4,3,
1,6,3,2,6,6,6,6,2,6,3,6,6,6,6,6,6,6,3,2,5,4,2,2,2,2,4,2,5,2,2,2,2,2,2,2

Теперь мне надо проверить этот прямоугольник в программе Эда. Приписываю к нему 27 строк, состоящих из числа 7, получаю квадрат 36х36, раскрашенный в 7 цветов. Ввожу этот квадрат в программу Эда, она его проверяет; вижу, что в прямоугольнике 9х36 ошибок нет, то есть он действительно 6-coloring.

Отлично! Лемма работает.
Теперь осталось исследовать вопрос: возможно ли составить прямоугольник 36х18 strong-(6,3)-coloring или прямоугольник 36х12 strong-(6,2)-coloring.

Вот картинка проверки квадрата 36х36 в программе Эда:



-- Пн июн 18, 2012 08:19:02 --

Проделала ещё один эксперимент с прямоугольником 9х36 6-coloring.
Любопытный эксперимент.
Ввела прямоугольник в программу Эда, не дополняя его до квадрата.
Прямоугольник преобразовался в программе в квадрат 18х18 (т.к. 9*36=324).
Но в этом квадрате оказалось, разумеется, много ошибок. С этими ошибками программа расправилась быстро, и вот такое решение получилось C=6, N=18x18:

C,B,A,B,A,A,D,A,E,E,B,C,B,D,C,D,C,B,A,A,C,B,C,D,C,A,B,D,D,E,C,F,E,B,E,D,B,B,B,A,B,B,B,C,A,D,A,
A,A,E,D,C,D,C,A,C,D,D,B,A,D,B,B,D,B,C,A,C,F,A,F,E,B,D,C,A,D,C,D,A,D,B,B,B,D,A,C,C,A,A,D,A,E,E,
E,E,B,B,D,C,D,D,B,C,A,C,B,A,B,A,A,D,D,D,A,D,A,C,C,C,C,A,B,B,B,B,C,D,C,F,F,B,E,B,A,E,E,E,E,C,D,
D,A,D,C,B,D,C,E,C,A,A,B,C,D,A,D,B,D,A,B,C,E,E,D,C,A,E,E,D,D,B,F,F,F,D,C,E,E,E,D,A,B,B,A,E,D,C,C
,B,A,E,C,B,B,A,A,D,E,F,E,B,B,A,F,E,E,D,C,A,E,D,A,C,A,F,D,D,D,C,A,D,B,C,A,A,B,C,E,B,A,B,D,E,F,E,F
,E,D,C,C,E,F,E,D,C,A,E,B,D,D,A,A,E,E,B,C,C,A,D,C,D,C,B,D,C,E,D,C,A,A,B,A,A,E,D,D,F,E,F,E,D,C,E,
A,E,C,C,A,D,C,D,F,F,F,F,B,A,D,B,F,F,F,F,A,C,A,C,E,D,A,B,C,C,D,C,E,B,B,A,C,B,D,D

[Zealint]

Могу дать такой совет. Вместо цвета "G" используйте цвет "@", тогда Total Errors будет равен нулю и пустые квадраты будут белыми. Те квадраты, которые у Вас на рисунке белые, на самом деле могут быть очень светло-серыми, поэтому число ошибок тут не видно.

[Nataly-Mak]

Я вообще-то не использовала символы, а использовала в решении только числа.
Числа в символы преобразовала программа.

К тому же, ошибки я вижу, включив функцию "линии ошибок" ("Error Lines"); эти линии красные и их никак нельзя не заметить!

Вот картинка с линиями ошибок:



Очевидно, что в проверяемом прямоугольнике 9х36 ошибок нет.

Бесполезный ваш совет, как всегда
Что-нибудь дельное можете посоветовать?

[dimkadimon]

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

Бесполезный ваш совет, как всегда
Что-нибудь дельное можете посоветовать?

Вы опять за свое? Как вы думаете, после такого ответа, люди захотят вам советовать?!?

[Nataly-Mak]

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

Продолжила эксперимент с прямоугольником 9х18 strong-(6,3)-coloring, расширила его по лемме 4.3 до прямоугольника 9х36 6-coloring:

1,1,1,1,1,1,1,5,5,5,5,3,2,4,3,4,3,2,3,3,3,3,3,3,3,1,1,1,1,5,4,6,5,6,5,4,
1,2,2,2,2,2,2,1,1,1,1,1,1,5,4,5,4,3,3,4,4,4,4,4,4,3,3,3,3,3,3,1,6,1,6,5,
2,1,3,3,3,3,2,1,2,2,2,2,2,1,1,1,1,1,4,3,5,5,5,5,4,3,4,4,4,4,4,3,3,3,3,3,
2,2,1,4,4,4,3,2,1,3,3,3,3,1,2,2,2,2,4,4,3,6,6,6,5,4,3,5,5,5,5,3,4,4,4,4,
3,3,2,1,5,3,3,2,2,1,4,4,4,2,1,3,3,3,5,5,4,3,1,5,5,4,4,3,6,6,6,4,3,5,5,5,
3,4,3,2,1,5,4,3,3,2,1,5,3,2,2,1,5,4,5,6,5,4,3,1,6,5,5,4,3,1,5,4,4,3,1,6,
4,3,4,3,2,1,5,3,4,3,2,1,5,3,3,2,1,5,6,5,6,5,4,3,1,5,6,5,4,3,1,5,5,4,3,1,
5,5,5,5,3,2,1,4,3,4,3,2,1,3,5,3,2,1,1,1,1,1,5,4,3,6,5,6,5,4,3,5,1,5,4,3,
1,6,3,2,6,6,6,6,2,6,3,6,6,6,6,6,6,6,3,2,5,4,2,2,2,2,4,2,5,2,2,2,2,2,2,2

Теперь мне надо проверить этот прямоугольник в программе Эда. Приписываю к нему 27 строк, состоящих из числа 7, получаю квадрат 36х36, раскрашенный в 7 цветов. Ввожу этот квадрат в программу Эда, она его проверяет; вижу, что в прямоугольнике 9х36 ошибок нет, то есть он действительно 6-coloring.

А неправильно я применила лемму
Вот никто и не проверяет. Хор-р-р-ошо! Сама зато проверяю. Сейчас подвигала по этому прямоугольнику мышкой в программе Эда, линии ошибок и нарисовались

А как правильно, не буду показывать. Всё равно ведь это не нужно никому, судя по полному отсутствию комментариев.

[svb]

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

К тому же, ошибки я вижу, включив функцию "линии ошибок" ("Error Lines"); эти линии красные и их никак нельзя не заметить!

Вот картинка с линиями ошибок:

Наталия, не обманывайте себя. Картинка, которую вы показали, совсем не обозначает, что в верхней части нет ошибок.

Кстати, последняя версия программы (от 13.06) стала работать шустрее - я пробовал вводить квадрат $13 \times 13$ в версию от 8.06 и в версию от 13.06. К сожалению, поле ограничено размером $200 \times 200$

[Nataly-Mak]

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

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

Бесполезный ваш совет, как всегда
Что-нибудь дельное можете посоветовать?

Вы опять за свое? Как вы думаете, после такого ответа, люди захотят вам советовать?!?

Да не нужны мне бесполезные советы!

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

-- Пн июн 18, 2012 13:05:59 --

svb в сообщении #586319 писал(а):

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

К тому же, ошибки я вижу, включив функцию "линии ошибок" ("Error Lines"); эти линии красные и их никак нельзя не заметить!

Вот картинка с линиями ошибок:

Наталия, не обманывайте себя. Картинка, которую вы показали, совсем не обозначает, что в верхней части нет ошибок.

Вы тоже опоздали с советом!
Я нашла ошибку сама. Посмотрите мой предыдущий пост.
Да, я сначала подумала, что все линии ошибок нарисовались автоматически. Оказалось, что это не так. Почему-то часть линий ошибок нарисовалась автоматом, а другая часть не нарисовалась; и эти линии рисуются только когда наведёшь мышку на ошибочный прямоугольник. Так что я не обманывала ни себя, ни кого бы то ни было (а какой смысл вообще обманывать?). Непонятки в работе программы Эда - только и всего

Цитата:

Кстати, последняя версия программы (от 13.06) стала работать шустрее - я пробовал вводить квадрат $13 \times 13$ в версию от 8.06 и в версию от 13.06. К сожалению, поле ограничено размером $200 \times 200$

Я не понимаю, о каких программах вы говорите.
Не видела никаких версий вообще

А! так вы о программе Эда что ли?
А что, есть уже новая версия? Вот - хоть один полезный совет появился

[svb]

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

Я не понимаю, о каких программах вы говорите.
Не видела никаких версий вообще

А вы посмотрите на картинку, которую вы прислали - там в верхней строчке и увидите

[Nataly-Mak]

Опять опоздали
Сама догадалась, что вы о программе Эда говорите.