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

[Pavlovsky]

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

Pavlovsky
вы можете подтянуться! Для вас будет вполне достойная позиция №3
Ещё один красивый алгоритм для С=15,21 и всё получится.

Все идет своим чередом, согласно воле всевышнего. Пытаюсь открыть четвертый класс, есть подвижки. Пробую другие подходы. Смотреть задачу из предыдущего моего поста. Может надо посмотреть решения для С=15,21. Есть кое какие наработки.

-- Чт июл 26, 2012 16:01:00 --

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

Важное уточнение: $(A + D - B - C)\bmod (N + 1) \ne 0$

Принимается. Долго думал, решил что mod лишнее. Оказывается не лишнее.

[svb]

Pavlovsky

Цитата:

Принимается. Долго думал, решил что mod лишнее. Оказывается не лишнее.

Т.е. как бы добавляется один дополнительный цвет. Для $N=5$ в вашей формулировке получается целый класс окрасок для C6N36. Для $N=p-1$, где $p$-простое имеются очевидные "полевые" решения, обрезанная таблица умножения. Но вот почему для $N=9$ перебор дает отрицательный результат? Кстати и для $N=7$ тоже отрицательный результат.

[Pavlovsky]

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

Т.е. как бы добавляется один дополнительный цвет.

Вроде этот факт учтен.

Цитата:

Квадрат надо заполнить числами от 0 до N.

[Nataly-Mak]

Есть!!!

Цитата:

21 392 153664 Alex Chernov @ 15:29:29 on 07-26-2012 1

[Nataly-Mak]

И ещё шаг:

Цитата:

21 393 154449 Alex Chernov @ 16:57:24 on 07-26-2012 1

[Pavlovsky]

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

Т.е. как бы добавляется один дополнительный цвет. Для в вашей формулировке получается целый класс окрасок для C6N36. Для , где -простое имеются очевидные "полевые" решения, обрезанная таблица умножения. Но вот почему для перебор дает отрицательный результат? Кстати и для тоже отрицательный результат.

Сергей раскрываем карты? Или так полунамеками и будем общаться? Может к теме кто то еще подключится?!

-- Пт июл 27, 2012 09:14:17 --

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

И ещё шаг:

Цитата:

21 393 154449 Alex Chernov @ 16:57:24 on 07-26-2012 1

И все таки Алексей одну строчку заныкал. Я ожидал результат C21N394.

-- Пт июл 27, 2012 09:25:57 --

Цитата:

21 394 155236 Alex Chernov @ 09:23:58 on 07-27-2012 1

Ловко я Алексея на чистую воду вывел! Не удалось спрятать!

[Nataly-Mak]

Не-а, не вывели, у него ещё пара строк припрятана

А я разобралась со своим регулярным решением C14N184 (второй класс).
Да, от него мне удалось получить решение C15N186.
Но такое решение у меня уже было получено от решения С14N185 в третьем классе.

Итак, с оценкой "отлично" перехожу в третий класс.
А вот в третьем классе я пока двоечница
Решение C14N185 у меня есть, но оно нерегулярное.
Однако мне удалось получить от него решение C15N187.
Чуть не хватило до C15N188, как раз одну строку не могу добавить

Ну, ничего, может быть, научусь ещё

Да, а во втором-то классе надо ещё попробовать решение C21N384 получить. Это должно получиться, т.к. решение C20N382 у меня регулярное в этом классе.

[Nataly-Mak]

Уф! Одолела решение C21N384 во втором классе.
Теперь этот класс полностью закрыт.

Цитата:

6 Jarek Wroblewski 19.821700 07-09-2012 @ 09:37:20
7 Valery Pavlovsky 19.821700 07-23-2012 @ 21:46:25
8 Natalya Makarova 19.790400 07-27-2012 @ 13:04:36

Такие хорошие джентльмены не берут двоечницу из третьего класса в свою компанию
Всего каких-то 0,0313 балла не хватает

[svb]

Pavlovsky

Цитата:

Сергей раскрываем карты? Или так полунамеками и будем общаться? Может к теме кто то еще подключится?!

Можно и раскрыть:

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

[Nataly-Mak]

Удивительно! Большинство конкурсантов работает в группе решений C=10,12,14,15,18,20,21.



Правда, у Алексея Чернова решения C=15,21 совсем другой категории, нежели у большинства конкурсантов.

[Pavlovsky]

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

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

Тогда начну с квадрата опубликованного Сергеем. Кстати мое решение C6N36 один в один такой квадрат. Решение C6N36 нашло 20 человек, надеюсь остальные не посещают этот форум. Правда у Alexu007 всего C6N27, но вроде он принципиально не пользуется чужими решениями. В конце концов исключить Сергея из конкурса, в котором он не принимает участие, будет трудно.

Заполним последние 6 строк и колонок как показано на рисунке. Это будет Г-крюк (по терминологии Картеси) Тогда пространство над Г-крюком будет состоять из матрицы 5х5 где в каждой ячейке будет латинский квадрат 6х6.
Вариантов различных ЛК 6х6 окрашенных в 6 цветов миллион и еще пара. Простейшее решение, для сокращения перебора, ограничить круг используемых ЛК. Например возьмем первый попавшийся ЛК и циклическим сдвигом получим другие ЛК с другой раскраской. Итого получится 6 ЛК. Из них и будем достраивать наш квадрат. Пронумеруем ЛК от 0 до 5. В порядке циклического сдвига. 0 - исходный ЛК.
Получилалась задача:
Дано. Пусть дан квадрат 5x5. Квадрат надо заполнить числами от 0 до 5.
Определение. Прямоугольник вида
AB
CD
, где A,B,C,D числа в вершинах прямоугольника, будем называть запрещенным, если выполняется соотношение: $(A + D - B - C)\bmod (6) = 0$.
Необходимо заполнить квадрат так, чтобы в нем не было запрещенных прямоугольников.

Решений у этой задачи много. Вот еще одно

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

Увы этот подход не дает уже решений для C=8,10 и более.
Выход из ситуации видится в увеличении множества базовых ЛК из которых будем строить квадрат. Но как? Ничего умного пока не придумал.

[svb]

Pavlovsky

Цитата:

В конце концов исключить Сергея из конкурса, в котором он не принимает участие, будет трудно.

А может я захочу . Но, увы, шансы мои тают , хотя я честно продолжаю поиски.
Я сейчас завершаю отчаянную попытку для $C=15$, решил пожертвовать одним $C$ - в конце концов $C(C-1)$ для 15 дает 210, все лучше, чем ничего . Лихо начал, но уже для $C=12$ перебор дал нулевой результат

[Pavlovsky]

Возможен другой вариант заполнения квадрата, предложенный svb.

Пример для С=4.

Здесь под Г-крюком образовалась матрица 4х4 из ЛК 3х3. Причем в каждом ЛК должен отсутствовать один из 4-х цветов.

Для сокращения перебора можно выбрать 4 базовых ЛК в каждом остутствует один цвет. Из каждого базового ЛК циклическим сдвигом получить серию ЛК. Получается 4х3=12 ЛК.

Вот тут у меня сразу образовался затык.

Возможно ли вообще из этого множества ЛК строить значимые решения.

К тому же красивое условие $(A + D - B - C)\bmod (N + 1) \ne 0$ действует если ЛК принадлежат одной серии. А придумать просто проверяемое условие для всего множества ЛК пока не получилось.

[svb]

Была, уже забытая, идея покрутить матрицы вида

  *  0  0  0  0  0
  0  *  1  0  3  2
  0  0  *  2  1  3
  0  1  3  *  4  0
  0  2  0  1  *  4
  0  3  2  4  0  *

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

[Pavlovsky]

Ну и последнее.

Для построения решения С6N36 достаточно построить сильноокрашенный прямоугольник 30х5. Как показано на рисунке. То есть заполнить матрицу 6х5 перестановками. В каждой перестановке все числа различны. В этом направлении присутсвуют все трудности предыдущих идей.
Отмечу только что перестановки полученные из базовой циклическим сдвигом подходят под основное условие $(A + D - B - C)\bmod (N + 1) \ne 0$.

Все свои карты я выложил.