2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 3, 4, 5, 6, 7, 8, 9 ... 130  След.
 
 Re: Новый конкурс программистов
Сообщение31.05.2012, 10:21 


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

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

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение31.05.2012, 10:36 
Заблокирован
Аватара пользователя


22/03/08

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

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

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

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

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

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение31.05.2012, 12:22 
Заблокирован
Аватара пользователя


22/03/08

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

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


21/02/10
1594
Екатеринбург
Вроде разобрался с алгоритмом построения квадрата 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 
Заблокирован
Аватара пользователя


22/03/08

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

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


21/02/10
1594
Екатеринбург
Где то так.

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

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

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение31.05.2012, 13:34 
Заблокирован
Аватара пользователя


22/03/08

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

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


21/02/10
1594
Екатеринбург
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 
Заблокирован
Аватара пользователя


22/03/08

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

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение31.05.2012, 14:30 


26/01/10
959
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 
Аватара пользователя


21/02/10
1594
Екатеринбург
Да. Достроить 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 


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

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение31.05.2012, 15:20 
Аватара пользователя


21/02/10
1594
Екатеринбург
Для С=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 


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

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

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

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение31.05.2012, 15:44 
Аватара пользователя


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 1937 ]  На страницу Пред.  1 ... 3, 4, 5, 6, 7, 8, 9 ... 130  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group