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

[Nataly-Mak]

dimkadimon в сообщении #590315 писал(а):

Хочу добавить что я тоже уже пытался. Я пробовал трясти прямоугольники strong c-coloring и те по вашей лемме. Их так же сложно, и может даже сложнее, трясти как обычные квадраты. У меня достаточно ефективный метод тряски которым я нашел 93х93, поэтому думаю тут нужен другой подход.

Стоп, стоп!
Пояснее, пожалуйста. Что вы "трясли"?
Каким именно методом вы нашли 93х93? Что у вас было исходным материалом для "тряски"?

Насколько я понимаю, решения 91х91 для С=10, которое даёт алгоритм для C=p^k+1, вы тогда ещё не нашли. Результат 93х93 для С=10 у вас введён очень давно, задолго до применения вами этого алгоритма.

Так что же вы тогда "трясли"? Непонятно!

P.S. Я никому не навязываю свой подход.

[Pavlovsky]

(Оффтоп)

[svb]

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

Но вот почему Вы решили, что svb имел ввиду именно ломанные диагонали, я так и не понял... Давайте подождём, что он скажет по этому поводу.

Хм... Я привел следующее определение:

Можно рассматривать "сильную диагональность", когда все маленькие квадраты одинаковы в своей диагонали - далеко не факт, что это невозможно, но перебор сильно сокращается.

которое, вроде, не должно было вызывать разночтений. Вы привели пример, который формально соответствовал этому определения - тут спорить не чем. Но изначально разговор шел о Г-образных маленьких квадратах и я "имел ввиду" именно их. Пустые Г-образные маленькие квадраты вынужденно располагаются по "ломанным диагоналям", поэтому и их внутреннее содержимое будет располагаться по ломанным диагоналям, если требовать, чтобы одноцветные Г-обрамления имели одинаковое содержимое.

Далее. Если мы заполнили маленькими квадратами главную диагональ (от левого-верхнего угла) и все квадраты выше, то оставшиеся квадраты "разумно" получать симметричным отражением относительно главной диагонали. Исходя из этого требования "маленькие" диагонали должны быть перпендикулярными главной диагонали, если они есть

Но все эти споры о терминологии лучше оставить "на потом".

[dimkadimon]

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

dimkadimon в сообщении #590315 писал(а):

Хочу добавить что я тоже уже пытался. Я пробовал трясти прямоугольники strong c-coloring и те по вашей лемме. Их так же сложно, и может даже сложнее, трясти как обычные квадраты. У меня достаточно ефективный метод тряски которым я нашел 93х93, поэтому думаю тут нужен другой подход.

Стоп, стоп!
Пояснее, пожалуйста. Что вы "трясли"?
Каким именно методом вы нашли 93х93? Что у вас было исходным материалом для "тряски"?

Насколько я понимаю, решения 91х91 для С=10, которое даёт алгоритм для C=p^k+1, вы тогда ещё не нашли. Результат 93х93 для С=10 у вас введён очень давно, задолго до применения вами этого алгоритма.

Так что же вы тогда "трясли"? Непонятно!

P.S. Я никому не навязываю свой подход.

Я начал с 81х81 из 9 цветов и тряс пока не дошел до 93х93, постепено увеличивая квадрат.

[svb]

Да, забыл сказать. Для C=10 не существует диагональных квадратов 100x100, если рассматривать ломанные диагонали.

[dimkadimon]

dimkadimon писал(а):

Я начал с 81х81 из 9 цветов и тряс пока не дошел до 93х93, постепено увеличивая квадрат.

Кажется Алексей наконец тоже нашел 93х93.

[Nataly-Mak]

А ну его этот квадрат 100х100
У меня вот "очко", квадрат 21х21 10-цветный, красивый:



Ход конём!
Кстати, в некотором роде диагональный и даже пандиагональный
Такими доминошными плиточками "диагональный". Только в одном месте нарушается такая плиточная диагональность.

[alexBlack]

dimkadimon в сообщении #590351 писал(а):

Кажется Алексей наконец тоже нашел 93х93.

Ага, даже 100x93, дополнением strong 9-colorings.

[Alexu007]

21х21 10-цветный программа случайного перебора находит мгновенно. И 9-8-7-цветные тоже. Всё хочу написать функцию, которая будет пытаться принудительно достраивать квадраты, не дотянувшие немного после случайного перебора. Но никак не заставлю себя начать программить - лень...

[Nataly-Mak]

Весь мир равняется на нашего Алексея!

Цитата:

1 Alex Chernov 20.000000 06-29-2012 @ 20:58:32

И что тут делать ещё два месяца?
Пора закрывать конкурс

Не зря я выступала на их форуме за сокращение продолжительности конкурса. Три месяца - это очень много. Вполне хватило бы и двух. Алексей вот прекрасно справился за месяц.
А для тех, кому лень, и трёх месяцев будет мало.

[svb]

Nataly-Mak

Цитата:

Не зря я выступала на их форуме за сокращение продолжительности конкурса. Три месяца - это очень много. Вполне хватило бы и двух. Алексей вот прекрасно справился за месяц.

С чем он справился? 20 баллов набрал? Так они у него уже были.

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

[dimkadimon]

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

Весь мир равняется на нашего Алексея!

Цитата:

1 Alex Chernov 20.000000 06-29-2012 @ 20:58:32

И что тут делать ещё два месяца?
Пора закрывать конкурс

Не зря я выступала на их форуме за сокращение продолжительности конкурса. Три месяца - это очень много. Вполне хватило бы и двух. Алексей вот прекрасно справился за месяц.
А для тех, кому лень, и трёх месяцев будет мало.

Поздравляю Алексея - ето гигантское достижение! Закрывать конкурс думаю еще рано. Теперь мы увидим настоящий прогрес и новые рекорды. Очень хорошо что много информации уже выложено на етом форуме - ето должно помочь прогресу.

[Nataly-Mak]

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

С чем он справился? 20 баллов набрал? Так они у него уже были.

Он справился с задачей! Он её решил, нашёл новые алгоритмы и методы, в отличие от многих, кто нашёл только то, что написано в статьях
20 баллов у него уже были, я это помню, здесь об этом писала. Но потом он терял несколько соток из-за рекородов других. Теперь он эти рекорды нашёл и у него снова 20 баллов.
Вот и справился!! Блестяще решил задачу!

Цитата:

Если дальше будет так продолжаться, то конкурс не даст ни одного значимого результата.

Как "так"?
Что вам не нравится в развитии конкурса? Что вы не нашли ни одного значимого результата? Так что вам мешает?
По-моему, всё замечательно развивается.
Кроме того, значимые результаты разрешено искать и после официальной части конкурса!

Цитата:

А если вам надо быстро, то тогда лучше стометровку бегать.

Угу. Сейчас побегу

-- Сб июн 30, 2012 04:58:59 --

dimkadimon в сообщении #590518 писал(а):

Очень хорошо что много информации уже выложено на етом форуме - ето должно помочь прогресу.

dimkadimon
Спасибо за вашу оценку этой темы. Кажется, вы единственный, кто её оценил

-- Сб июн 30, 2012 05:17:19 --

Таблица рекордов, найденных на конкурсе:

(Оффтоп)

2 4 16 Wes Sampson @ 05:33:15 on 05-30-2012 72
3 10 100 Mark Mammel @ 06:40:27 on 05-30-2012 47
4 18 324 Juha Saukkola @ 09:15:48 on 05-30-2012 38
5 25 625 Jarek Wroblewski @ 09:04:36 on 05-30-2012 36
6 36 1296 Alex Chernov @ 23:02:26 on 05-31-2012 18
7 49 2401 Jarek Wroblewski @ 09:05:38 on 05-30-2012 34
8 64 4096 Il brigante Pennastorta @ 14:08:50 on 05-31-2012 23
9 81 6561 Il brigante Pennastorta @ 17:12:43 on 05-31-2012 23
10 93 8649 Dmitry Kamenetsky @ 09:24:27 on 06-05-2012 2
11 121 14641 Jarek Wroblewski @ 09:06:25 on 05-30-2012 33
12 135 18225 Dmitry Kamenetsky @ 12:46:11 on 06-11-2012 3
13 169 28561 Jarek Wroblewski @ 09:07:27 on 05-30-2012 33
14 185 34225 Herbert Kociemba @ 02:59:00 on 06-21-2012 2
15 192 36864 Alex Chernov @ 16:04:06 on 06-23-2012 1
16 256 65536 Dmitry Kamenetsky @ 07:49:18 on 06-01-2012 22
17 289 83521 Jarek Wroblewski @ 09:13:49 on 05-30-2012 33
18 309 95481 Herbert Kociemba @ 19:05:08 on 06-26-2012 2
19 361 130321 Jarek Wroblewski @ 09:19:13 on 05-30-2012 33
20 383 146689 Herbert Kociemba @ 19:30:28 on 06-26-2012 2
21 389 151321 Alex Chernov @ 17:12:15 on 06-24-2012 1

Конкурс уже дал целый ряд значимых результатов.
Непревзойдённые пока решения Алексея для С=15, 21. Класс!

Далее, хорошие решения для С=10,12,14,18,20.
Конечно, их ещё можно улучшить, наверное. Но то, что найдено, уже впечатляет.

Алексей сообщил, что он нашёл для С=10 прямоугольник 100х93. Здорово! Дальше можно пытаться достраивать. Если не до 100х100, то хотя бы до 94х94 вполне возможно достроить.

Не исключено, что и для других С возможны улучшения.
Ну, впереди ещё два месяца. Время покажет.
Кто бегать стометровку не будет, тот ещё что-то значимое найдёт
Хотя пробежки стометровок в этом не помешают, наоборот, помогут.

alexBlack
вы бегаете по утрам?

Кстати, у меня тоже есть один прямоугольничек - 37х36 6-цветный
У многих, наверное, такой имеется.
Это я из своего решения 36х36 получила в программе Эда, легко! Почему бы ему не достроиться до 37х37...

[svb]

Я нисколько не собираюсь умалять результаты alexBlack, как это вы пытаетесь представить, но ваше мнение о сокращении продолжительности конкурса более чем странно. Разве не осталось никаких проблем?

Цитата:

Что вам не нравится в развитии конкурса? Что вы не нашли ни одного значимого результата? Так что вам мешает?

А причем здесь я? Конечно, значимость результата слишком субъективно, чтобы спорить на эту тему, но получить для C цветов сторону квадрата $C^2$ хотелось бы. Для C=6 этот квадрат имеется, но чем хуже число 21 или 10? Если вы получите для C=6 квадрат 37x37, то для меня это тоже будет значимым результатом.

Я бы присоединился к поздравлениям Алексея, но лучше дождусь окончания конкурса - сейчас это выглядит несуразно. Если вы следите за результатами, то Herbert Kociemba имеет неплохие шансы повторить результат Алексея. Именно Herbert Kociemba подтолкнул Алексея к последним результатам. Т.ч. даже со спортивной точки зрения основная борьба впереди.

[alexBlack]

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

Именно Herbert Kociemba подтолкнул Алексея к последним результатам. Т.ч. даже со спортивной точки зрения основная борьба впереди.

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