2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу Пред.  1 ... 3, 4, 5, 6, 7, 8, 9 ... 130  След.
 
 Re: Новый конкурс программистов
Сообщение31.05.2012, 10:21 
Цитата:
Zealint
на построение одного квадрата ручками у меня уходит 5-10 минут.
Сомневаюсь, что если вы раскрасите, например, квадрат 75х75 произвольным образом в 21 цвет, программа разберётся со всеми прямоугольниками за приемлемое время. Иногда исправить все прямоугольники вообще не удаётся, и программа ваша просто захлебнётся (зациклится).

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

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

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

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

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

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

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

 
 
 
 Re: Новый конкурс программистов
Сообщение31.05.2012, 13:11 
Аватара пользователя
Вроде разобрался с алгоритмом построения квадрата 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
Квадрат построен.

 
 
 
 Re: Новый конкурс программистов
Сообщение31.05.2012, 13:26 
Аватара пользователя
То есть вы теперь легко можете построить квадрат 256х256 для C=16?

 
 
 
 Re: Новый конкурс программистов
Сообщение31.05.2012, 13:29 
Аватара пользователя
Где то так.

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

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

 
 
 
 Re: Новый конкурс программистов
Сообщение31.05.2012, 13:34 
Аватара пользователя
Кстати, решение для C=8 N=64*64 на конкурсе получено. Наверное, этим же методом.

 
 
 
 Re: Новый конкурс программистов
Сообщение31.05.2012, 13:39 
Аватара пользователя
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

 
 
 
 Re: Новый конкурс программистов
Сообщение31.05.2012, 14:24 
Аватара пользователя
То есть для p=5 можно гарантированно построить не только квадрат 25х25, но и прямоугольник 25х30. Правильно я поняла?

 
 
 
 Re: Новый конкурс программистов
Сообщение31.05.2012, 14:30 
Pavlovsky в сообщении #578892 писал(а):
А. Множество чисел Х={1...C^2} надо С способами разбить на С групп по С чисел. В соответсвии с леммой 4.11 надо чтобы любые два числа входили только в одну группу.

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

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

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

 
 
 
 Re: Новый конкурс программистов
Сообщение31.05.2012, 14:38 
Аватара пользователя
Да. Достроить 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}

 
 
 
 Re: Новый конкурс программистов
Сообщение31.05.2012, 15:09 
А для 5 какие шаги нужно брать? И для 7... и дальше?

 
 
 
 Re: Новый конкурс программистов
Сообщение31.05.2012, 15:20 
Аватара пользователя
Для С=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)

 
 
 
 Re: Новый конкурс программистов
Сообщение31.05.2012, 15:42 
Отлично, спасибо.
Уже закодил, послал все простые числа. Работает, сижу на втором месте : )
Основная сложность состояла в отправке ответов для 17 и 19, браузер несколько раз подвисал минут на 3-5.

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

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

 
 
 
 Re: Новый конкурс программистов
Сообщение31.05.2012, 15:44 
Аватара пользователя
Увы я кодю жутко медленно. Еще даже не начинал, чешу одно место. Поэтому очень рад, что мои посты кому то пригодились.

 
 
 [ Сообщений: 1937 ]  На страницу Пред.  1 ... 3, 4, 5, 6, 7, 8, 9 ... 130  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group