2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 93, 94, 95, 96, 97, 98, 99 ... 130  След.
 
 Re: Новый конкурс программистов
Сообщение24.08.2012, 08:03 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
И наконец последнее весьма оригинальное решение.

Это совсем оригинальный алгоритм, он основан на МБ-лемме.
Кто внимательно читал тему, помнит, что именно по этому алгоритму я построила решения 2-го класса.

Берём стандартную 7-сильную раскраску 49х8. Выполняем одну репликацию, но!.. возникший при репликации цвет 8 не заменяем на 1.
В результате такой операции мы получаем раскраску 49х16 (8,2)-strong по МБ-лемме!

Вот она - эта очень симпатичная раскрасочка:

Изображение

Ну, а теперь, понятно, применяем МБ-лемму, всего 3 репликации и... раскраска 49х64 8-coloring готова. Приписываем к ней 9 строк и получаем решение 58х64 8-coloring:

Изображение

Так я получила своё первое решение во 2-ом классе - C10N92. И для всех следующих С аналогично.

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


22/03/08

7154
Саратов
Опубликую таблицу рекордов, полученных на конкурсе, вряд ли уже что-то изменится до конца конкурса:

Цитата:
2 4 16 Wes Sampson @ 05:33:15 on 05-30-2012 81
3 10 100 Mark Mammel @ 06:40:27 on 05-30-2012 55
4 18 324 Juha Saukkola @ 09:15:48 on 05-30-2012 45
5 25 625 Jarek Wroblewski @ 09:04:36 on 05-30-2012 41
6 36 1296 Alex Chernov @ 23:02:26 on 05-31-2012 23
7 49 2401 Jarek Wroblewski @ 09:05:38 on 05-30-2012 38
8 64 4096 Il brigante Pennastorta @ 14:08:50 on 05-31-2012 28
9 81 6561 Il brigante Pennastorta @ 17:12:43 on 05-31-2012 28
10 94 8836 Artem Karavaev @ 19:50:31 on 07-09-2012 4
11 121 14641 Jarek Wroblewski @ 09:06:25 on 05-30-2012 37
12 136 18496 Artem Karavaev @ 19:18:29 on 06-30-2012 2
13 169 28561 Jarek Wroblewski @ 09:07:27 on 05-30-2012 37
14 186 34596 Artem Karavaev @ 06:56:57 on 07-10-2012 2
15 197 38809 Alex Chernov @ 13:23:07 on 08-08-2012 1
16 256 65536 Dmitry Kamenetsky @ 07:49:18 on 06-01-2012 27
17 289 83521 Jarek Wroblewski @ 09:13:49 on 05-30-2012 37
18 310 96100 Artem Karavaev @ 17:37:19 on 07-11-2012 2
19 361 130321 Jarek Wroblewski @ 09:19:13 on 05-30-2012 37
20 384 147456 Artem Karavaev @ 08:19:18 on 07-10-2012 2
21 400 160000 Alex Chernov @ 22:10:03 on 08-11-2012 1

Забавно, 81 из 88 участников нашли решение C2N4 :D

По-прежнему неповторенными остаются рекорды Алексея Чернова для С=15,21.
svb загадочно намекал, что должно получиться решение C21N401 в рамках какого-то достраивания, но я так и не поняла, где же оно :wink:

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


21/02/10
1594
Екатеринбург
Рановато, я заявил о звершении участия в конкурсе. Появляются еще идеи!

Вспомогательная задача.
Дано: натуральные числа k,N.
Необходимо заполнить единичками прямоугольник MxN. M – количество строк, N – количество колонок. Такой что:
1) В прямоугольнике нет запрещенных прямоугольников.
2) В каждой колонке размещается ровно k единичек.
3) Количество строк M - минимально возможное.

В стиле доказательства Sirgedas можно оценить границу снизу для M

Код:
k\N   6   10   12   14   15   18   20   21
2     4    5    6    6    6    7    7    7
3     7    9    9   10   10   11   12   12
4     9   12   13   14   12   16      
5    12   15   16   18   18


Пример для k=3, N=6
    1 1 1 0 0 0
    1 0 0 1 1 0
    1 0 0 0 0 1
    0 1 0 1 0 1
    0 1 0 0 1 0
    0 0 1 1 0 1
    0 0 1 0 1 0

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


01/06/12
1016
Adelaide, Australia
Я наконец разгадал метод Herbert с cyclic difference set (CDS). CDS(v,k,lambda) это k цифр от 0 до v-1, где каждая разница (mod v) между любой пары цифр встречается ровно lambda раз. Для нашей задачи нам интересны имено lambda=1. Причём CDS(v,k,1) существуют для всех k=p^n+1 и v=p^2+p+1, где p простое число. CDS(v,k,1) дает нам решение где C=k и N=v. Вот они тут: http://www.ccrwest.org/diffsets/diff_sets/baumert.html
Значит мы можем построить вот эти решения: C3N7, C4N13, C5N21, C6N31, C8N57, C9N73, C10N91, C12N133, C14N183, C17N273, C18N307 и C20N381. Эти решения имеют диагональную форму и поетому очень красивые.

Возьмём CDS(7,3,1) = (0,1,3). Это можно представить как замкнутую цепочку из 7 бусинок где бусинки на позициях 0, 1 и 3 чёрные, а остальные белые. Растояния между любой две чёрные бусинки все разные. Вот как выглядит таблица разниц (mod 7):

Код:
  0 1 3
0 0 1 3
1 6 0 2
3 4 5 0


Заметьте что все разницы от 1 до 6 встречаются ровно 1 раз. Если передвинуть бусинки на одну позицию то опять получится правильная цепочка. Значит CDS(7,3,1) можно записать вот ещё так:

Код:
0,1,3  а
1,2,4
2,3,5
3,4,6
4,5,0  b
5,6,1
6,0,2  c

Это всё очень хорошо описано тут: http://www.inference.phy.cam.ac.uk/cds/part1.htm

Итак чтобы составить наше решение красим первым цветом (а) диагонали 0, 1 и 3, начиная сверху:

Код:
0123456
аа0а000
0аа0а00
00аа0а0
000аа0а
0000аа0
00000аа
000000а


Пустые клетки я обозначил нулём. Если сделаем 7 - (0,1,3) то получим (7,6,4). Теперь можно закрасить нижние диагонали 4 и 6 начиная слева:

Код:
  0123456
0аа0а000
10аа0а00
200аа0а0
3000аа0а
4а000аа0
50а000аа
6а0а000а


Остальные два цвета можно закрасить таким же образом. Для второго цвета b выбираем (4,5,0), а для третьего цвета c берём (6,0,2). Вот наконец получаем полное решение:

Код:
  0123456
0ааcabbc
1cааcаbb
2bcааcаb
3bbcааcа
4аbbcааc
5cаbbcаа
6аcаbbcа


Этот метод можно проделать и для других C. Красота!

К сожалению это совсем не даёт нам никаких улучшений. "Увеличивать" эти решения совсем не получается, например я даже не смог получить C10N92 из C10N91. Зато обнаружил что можно немного уменьшить требования CDS - можно искать цепочки где каждая разница встречается 0 или 1 раз. То есть какие то разницы вообще не встречаются. В этом случае, правда, для других цветов надо находить отдельные цепочки (которые отличны) от первой. Таким образом я теперь очень быстро могу находить диагональные решения C5N25 и C6N36, а вот для C>=10 никакого прогресса.

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

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


20/01/10
766
Нижний Новгород
Nataly-Mak в сообщении #609842 писал(а):
А вот здесь вы разве не о супералгоритме писали?
Читая это, я поняла так, что у вас есть как минимум решение C21N401 и ещё куча рекордов :D
Писал я не об алгоритме, а о "базовой конфигурации". Основной целью было оживление темы, как говорит Павловский "интриганство" :-)

А вот алгоритм? Может он и существует, а может и нет - не знаю. Вручную я пробовал заполнять дырки для C=5, получилось, но потом оказалось, что это слишком маленький опыт. Но предел у этого подхода C21401 - в сочетании с результатами alexBlack появилась возможность "интриговать" :-) . В свое оправдание могу сказать, что обманом я никогда не занимался - можете проверить.

Вот сейчас появилось сообщение dimkadimon с исключительно богатой и интересной идеей. Сколько я с этими "разностями" возился, но жар-птица все-время улетала. Уложить все "разности" в одну строку - это блеск!

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


22/03/08

7154
Саратов
svb в сообщении #610024 писал(а):
Писал я не об алгоритме, а о "базовой конфигурации".

Вы писали о некотором способе построения решений. Это не алгоритмом разве называют? :shock:
Цитата:
Основной целью было оживление темы, как говорит Павловский "интриганство" :-)

По-моему, мы находимся не на тусовке бомонда, чтобы плести интриги. Мне это непонятно.
"Трёп", "интриги"... Здесь вроде как научный форум. Я все сообщения воспринимаю серьёзно и начинаю обдумывать. Оказывается, тут интриги какие-то :shock:

-- Пт авг 24, 2012 16:14:51 --

svb в сообщении #610024 писал(а):
Вот сейчас появилось сообщение dimkadimon с исключительно богатой и интересной идеей.

Да, dimkadimon, в отличие от вас, не интригует, а пишет совершенно конкретные вещи.
Я эту идею Герберта давным-давно отметила, но не разобралась в ней до конца. Даже свою попытку приводила (картинку).
dimkadimon сумел разобраться, молодец!

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


01/06/12
1016
Adelaide, Australia
Nataly-Mak в сообщении #610065 писал(а):
Я эту идею Герберта давным-давно отметила, но не разобралась в ней до конца. Даже свою попытку приводила (картинку).
dimkadimon сумел разобраться, молодец!


Спасибо. Кстати я догадался только благодаря вашей попытки. Все таки вместе мы гораздо сильнее.

-- 24.08.2012, 21:07 --

Pavlovsky в сообщении #609902 писал(а):
Рановато, я заявил о звершении участия в конкурсе. Появляются еще идеи!

Вспомогательная задача.
Дано: натуральные числа k,N.
Необходимо заполнить единичками прямоугольник MxN. M – количество строк, N – количество колонок. Такой что:
1) В прямоугольнике нет запрещенных прямоугольников.
2) В каждой колонке размещается ровно k единичек.
3) Количество строк M - минимально возможное.



Пока не вижу связь етой задачи с главной задачей, но готов поискать решения к ней. Какие k и N вас интересуют?

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


21/02/10
1594
Екатеринбург
dimkadimon в сообщении #610076 писал(а):
Пока не вижу связь этой задачи с главной задачей

Появилась идея. В случае удачи можно строить решения 4 и даже 5 класса! Первая попытка реализовать идею закончилась неудачей. Так как уже нет сил заниматься конкурсной задачей, готов опубликовать идею. Если никто не возражает.

dimkadimon в сообщении #610076 писал(а):
готов поискать решения к ней. Какие k и N вас интересуют

Например N=10 k=3. В соответсвии с нижней оценкой M=9. То есть надо построить прямоугольник 9х10 (9 - строки 10 - колонки).
1) В прямоугольнике нет запрещенных прямоугольников.
2) В каждой колонке размещается ровно 3 единичек.

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


20/01/10
766
Нижний Новгород
Nataly-Mak в сообщении #610065 писал(а):
Вы писали о некотором способе построения решений. Это не алгоритмом разве называют? :shock:
Я разве писал, что знаю как получить C21N401? Прошу вас не сочинять и не приписывать мне того, что я не говорил :mrgreen:
Цитата:

По-моему, мы находимся не на тусовке бомонда, чтобы плести интриги. Мне это непонятно.
"Трёп", "интриги"... Здесь вроде как научный форум. Я все сообщения воспринимаю серьёзно и начинаю обдумывать. Оказывается, тут интриги какие-то :shock:
Слово "интриги" не я употребил, поэтому и ставлю это слово в кавычки.
Цитата:
Да, dimkadimon, в отличие от вас, не интригует, а пишет совершенно конкретные вещи.
Вот это уже переходит за рамки приличий, поэтому я, пожалуй, покину этот форум. Прощайте!

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


22/03/08

7154
Саратов
dimkadimon
ещё раз спасибо вам за подробное описание идеи Герберта.
Вроде разобралась. Построила сначала 7х7 3-coloring точно по вашему описанию, чтобы лучше понять.
Затем повторила свою неудавшуюся давно попытку, это решение C6N31.
Теперь получилось:

Изображение

Действительно, красивые решения получаются.
Вы писали, что можно по этому алгоритму получить решения C8N57, C10N91. Здорово.
Для С=10 решение 1-го класса диагональное!
Кстати, решение для С6N31, показанное мной, тоже 1-го класса. И C8N57 тоже 1-го класса.
То есть по этому алгоритму все решения 1-го класса получаются. Так?

Кстати, тут давно пытались искать диагональные решения для С=10. Какое максимальное удалось найти? Может быть, 91х91 и есть максимальное?
Построить бы его... но вручную долго, трудновато. Программку бы составить.

Не поняла один момент: что означает n в таблице CDS?
Например, я использовала CDS (31,6,1)

Код:
1, 5, 11, 24, 25, 27

здесь n=5. Что это такое? Где используется?

Вообще идея супер, конечно. Спасибо Герберту!

-- Сб авг 25, 2012 11:14:49 --

Pavlovsky в сообщении #610105 писал(а):
Появилась идея. В случае удачи можно строить решения 4 и даже 5 класса! Первая попытка реализовать идею закончилась неудачей. Так как уже нет сил заниматься конкурсной задачей, готов опубликовать идею. Если никто не возражает.

Вы тоже интригуете? :D

Что же это так сильно устали. Я тоже притомилась, но всё ещё занимаюсь задачей.
Правда, ничего не получается, но... я не виновата, стараюсь :?
Насчёт опубликования идеи не возражаю.

Цитата:
Например N=10 k=3. В соответсвии с нижней оценкой M=9. То есть надо построить прямоугольник 9х10 (9 - строки 10 - колонки).
1) В прямоугольнике нет запрещенных прямоугольников.
2) В каждой колонке размещается ровно 3 единичек.

Ну, вот, например, с ходу такой прямоугольник, он не совсем удовлетворяет вашим условиям, но близко; в одной колонке 4 единички, а в трёх колонках по 2 единички, в остальных - по 3 единички:

Код:
1 x x x x x x 1 x x
x x x x x 1 x x 1 1
x x x 1 1 x 1 x 1 x
x x 1 x x 1 1 1 x x
x 1 1 x x x x x 1 x
x 1 x 1 x x x 1 x x
x x 1 1 x x x x x 1
1 x 1 x 1 x x x x x
1 1 x x x x 1 x x x

Если будет построен такой прямоугольник в точном соответствии с вашими условиями, дальше что с ним надо делать?

-- Сб авг 25, 2012 11:50:52 --

Цитата:
My clues never really reveal anything. But, as has already been mentioned, it WILL involve prime numbers. :)

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

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

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


01/06/12
1016
Adelaide, Australia
Pavlovsky в сообщении #610105 писал(а):
Например N=10 k=3. В соответсвии с нижней оценкой M=9. То есть надо построить прямоугольник 9х10 (9 - строки 10 - колонки).
1) В прямоугольнике нет запрещенных прямоугольников.
2) В каждой колонке размещается ровно 3 единичек.


Вот решение для N=10, k=3 и М=9:
Код:
0,1,0,0,0,0,1,0,1,0,
1,0,0,0,0,1,1,0,0,0,
0,0,1,0,0,0,1,1,0,1,
1,0,0,1,0,0,0,0,1,1,
0,1,1,1,0,1,0,0,0,0,
0,1,0,0,1,0,0,0,0,1,
0,0,0,0,1,1,0,1,1,0,
0,0,0,1,0,0,0,1,0,0,
1,0,1,0,1,0,0,0,0,0

А что дальше? Неужели из етого можно получить C3N10? Кстати для М=9 решений не было.

-- 25.08.2012, 17:10 --

Nataly-Mak в сообщении #610346 писал(а):
То есть по этому алгоритму все решения 1-го класса получаются. Так?

Кстати, тут давно пытались искать диагональные решения для С=10. Какое максимальное удалось найти? Может быть, 91х91 и есть максимальное?
Построить бы его... но вручную долго, трудновато. Программку бы составить.

Не поняла один момент: что означает n в таблице CDS?
Например, я использовала CDS (31,6,1)

Код:
1, 5, 11, 24, 25, 27

здесь n=5. Что это такое? Где используется?


По етому алгоритму можно получить C=p^k+1 размером N=p^2+p+1, точно не знаю какой ето класс. Немного изменив метод можно получить и лучше, например C5N25 и C6N36. Возможно 91х91 максимальное, но я еше не пробовал 92х92. 91х91 (и другие) я выложу в конце соревнования. Я не знаю что такое n.

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


22/03/08

7154
Саратов
dimkadimon в сообщении #610359 писал(а):
По етому алгоритму можно получить C=p^k+1 размером N=p^2+p+1...

По-моему, это не совсем правильная формула. У вас во второй формуле не участвует k.
Что за N у вас получится, например, при p=3, k=2 (С=10)?

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


21/02/10
1594
Екатеринбург
Идея была такая. Берем сильноокрашенный прямоугольник 81х10 заполненный 9-ю цветами. Удаляем из него 6 строк. Добавляем 9 строк
Код:
0,1,0,0,0,0,1,0,1,0,
1,0,0,0,0,1,1,0,0,0,
0,0,1,0,0,0,1,1,0,1,
1,0,0,1,0,0,0,0,1,1,
0,1,1,1,0,1,0,0,0,0,
0,1,0,0,1,0,0,0,0,1,
0,0,0,0,1,1,0,1,1,0,
0,0,0,1,0,0,0,1,0,0,
1,0,1,0,1,0,0,0,0,0

Вместо 1 вставляем 10. Пытаемся заполнить ячейки с нулями. Если это удастся, то получим сильноокрашенный прямоугольник 84х10 для С=10. Из которого получаем решение C10N94.

Увы первые эксперименты дали отрицательный результат. Конечно над идеей можно еще работать, но это уже в следующем конкурсе.

-- Сб авг 25, 2012 15:24:37 --

Идея оказалась слишком заумной. Простой вариант идеи такой.
Берем сильноокрашенный прямоугольник 81х10 заполненный 9-ю цветами. Удаляем из него некоторое количество строк. К полученному прямоугольнику пытаемся добавлять строки с использованием 10-ти цветов.

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


22/03/08

7154
Саратов
Pavlovsky в сообщении #610376 писал(а):
Если это удастся, то получим сильноокрашенный прямоугольник 84х10 для С=10. Из которого получаем решение C10N94.

Увы первые эксперименты дали отрицательный результат.

А вы к опыту коллег прислушиваетесь? :D
Я высказала гипотезу, что 10-сильная раскраска 84х10 не существует.

Гипотезу пока никто не опроверг, хотя... и не доказал :!:

Ваш отрицательный результат только подтверждает гипотезу.

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


01/06/12
1016
Adelaide, Australia
Nataly-Mak в сообщении #610361 писал(а):
dimkadimon в сообщении #610359 писал(а):
По етому алгоритму можно получить C=p^k+1 размером N=p^2+p+1...

По-моему, это не совсем правильная формула. У вас во второй формуле не участвует k.
Что за N у вас получится, например, при p=3, k=2 (С=10)?


С это простое число в степени плюс один. p простое число, а k любая степень. Простите я формулу совсем напутал, должно быть N=C^2-С+1.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 1937 ]  На страницу Пред.  1 ... 93, 94, 95, 96, 97, 98, 99 ... 130  След.

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



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

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


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

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