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

[Zealint]

Цитата:

Zealint
на построение одного квадрата ручками у меня уходит 5-10 минут.
Сомневаюсь, что если вы раскрасите, например, квадрат 75х75 произвольным образом в 21 цвет, программа разберётся со всеми прямоугольниками за приемлемое время. Иногда исправить все прямоугольники вообще не удаётся, и программа ваша просто захлебнётся (зациклится).

Ну, примерно столько же ушло на метод полного перебора (я имею в виду написание кода). Пока чай пил, досчитал до 169x169 (но перебор не совсем такой тупой, как я написал). Так что в любом случае это пока лучше. Если Ваш метод реализовать, может и будет лучше, не спорю, но ведь надо сначала реализовать! А я пока ещё стартую... До августа время есть подумать.

[Nataly-Mak]

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

Цитата:

Zealint
на построение одного квадрата ручками у меня уходит 5-10 минут.
Сомневаюсь, что если вы раскрасите, например, квадрат 75х75 произвольным образом в 21 цвет, программа разберётся со всеми прямоугольниками за приемлемое время. Иногда исправить все прямоугольники вообще не удаётся, и программа ваша просто захлебнётся (зациклится).

Ну, примерно столько же ушло на метод полного перебора (я имею в виду написание кода). Пока чай пил, досчитал до 169x169 (но перебор не совсем такой тупой, как я написал). Так что в любом случае это пока лучше. Если Ваш метод реализовать, может и будет лучше, не спорю, но ведь надо сначала реализовать! А я пока ещё стартую... До августа время есть подумать.

А вот ручками вашим методом можно построить квадрат, например, 80х80 для 21 цветов? Так что, по-любому мой метод гораздо лучше переборного.

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

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

[Nataly-Mak]

Фантастика! Я дошла до квадрата 83х83, метод работает. Есть предположение, что он будет работать и дальше.
Конечно, мой результат N=6889 выглядит очень плохо по сравнению с максимальным результатом, найденным на конкурсе, но это всё же лучше, чем N=441, что даёт латинский квадрат.

[Pavlovsky]

Вроде разобрался с алгоритмом построения квадрата C^2xC^2.

А. Множество чисел Х={1...C^2} надо С способами разбить на С групп по С чисел. В соответсвии с леммой 4.11 надо чтобы любые два числа входили только в одну группу.

Б. Строим прямоугольник C^2xC по алгоритму изложенному в лемме 4.11 (часть 1). Прямоугольник будет "strong C-coloring".

В. Строим квадрат C^2xC^2 по алгоритму изложенному в лемме 4.3. В итоге получется искомый квадрат.

Пример. С=2

А. P1={1,2|3,4} P2={1,3|2,4}

Б.
1 1
1 2
2 1
2 2
В.
1 1 2 2
1 2 2 1
2 1 1 2
2 2 1 1
Квадрат построен.

[Nataly-Mak]

То есть вы теперь легко можете построить квадрат 256х256 для C=16?

[Pavlovsky]

Где то так.

Надо еще разобраться как получать разбиения на этапе А. Алгоритм описывается в статье после теоремы 4.12.

Для начала хотя бы получить решение для С=5 25х25.

[Nataly-Mak]

Кстати, решение для C=8 N=64*64 на конкурсе получено. Наверное, этим же методом.

[Pavlovsky]

If p is a prime , then $G_{p^{2},p^{2}+p}$ is $p$-colorable

Получается заготовка для для построения квадрата $(p^{2}+p)X(p^{2}+p)}$

-- Чт май 31, 2012 16:21:32 --

Блин, заготовка не получается.

Theorem 5.1 For all c > 0, $G_{c^{2}+c,c^{2}+c}$ is not c-colorable

[Nataly-Mak]

То есть для p=5 можно гарантированно построить не только квадрат 25х25, но и прямоугольник 25х30. Правильно я поняла?

[Zealint]

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

А. Множество чисел Х={1...C^2} надо С способами разбить на С групп по С чисел. В соответсвии с леммой 4.11 надо чтобы любые два числа входили только в одну группу.

Все верно, только надо, чтобы любые два числа из любой группы не попадали в любую другую группу. Таких разбиений нужно m, в идеале хорошо, когда m=C;

Цитата:

Для начала хотя бы получить решение для С=5 25х25.

Это делается перебором. Разбиваем на 5x5 квадраты, которые заполнены циклически. Потом случайно числа в 5x5 квадратах, образующих коллизию с другими квадратами, увеличиваем на 1 (по модулю). Через 2-3 секунды перебора получается правильный квадрат. Для 7x7, правда, уже не работает.

[Pavlovsky]

Да. Достроить 5 строк до квадрата 30х30 не получится. Но получить квадрат 29х29 теоретически возможно.

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

Надо еще разобраться как получать разбиения на этапе А.

Разобрался, теперь можно и кодить. Очень похоже на пути у Россера.

Пример Получить разбиение для C=3
А. Рисуем таблицу
1 2 3
4 5 6
7 8 9
Б. Первое разбиение шаг (1,0) {1,2,3|4,5,6|7,8,9}
В. Второе разбиение шаг (1,1 ) {1,5,9|4,8,3|7,2,6}
Г Третье разбиение шаг (1,2) {1,8,6|4,2,9|7,5,3}

[Zealint]

А для 5 какие шаги нужно брать? И для 7... и дальше?

[Pavlovsky]

Для С=p, где p просте число.
А.Строим таблицу СхС и заполняем ее числами от 1 до C^2
Б. Строим разбиения.
Б1. Для каждого способа разбиения задаем шаг (1,t). 0<=t<p.
Б2. Каждая группа разбиения начинается с ячеек из первого столбца.
Б3. Текущая группа заполняется числами из ячеек таблицы. Берем индексы текущей ячейки. К номеру колонки прибавляем 1, к номеру строки t. Если индекс получился больше C вычитаем из него C (индексы берем по модулю C).

Если C=p^s тогда немного сложнее. Для некоторых разбиений придется задавать шаг (u,t), где u>1.

-- Чт май 31, 2012 17:33:30 --

Например для C=9 можно взять шаги для разбиений (1,0)(1,1)(1,2)(2,5)(1,4)(1,5)(2,7)(1,7)(1,8)

[Zealint]

Отлично, спасибо.
Уже закодил, послал все простые числа. Работает, сижу на втором месте : )
Основная сложность состояла в отправке ответов для 17 и 19, браузер несколько раз подвисал минут на 3-5.

-- Чт май 31, 2012 15:43:35 --

Составные числа, наверное, сегодня уже не успею...

[Pavlovsky]

Увы я кодю жутко медленно. Еще даже не начинал, чешу одно место. Поэтому очень рад, что мои посты кому то пригодились.