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

[Nataly-Mak]

Ну что же, решения C=8, N=4096 и C=9, N=6561 я нашла.
Осталось построить 16-цветный квадрат 256х256, но это уже дело техники.

Буду ли что дальше искать, пока не решила. Подумаю, отдохну после бурного старта

[Nataly-Mak]

Наши пока держатся

1  Alex Chernov 19.936500 06-06-2012 @ 22:15:33
2  Tom Sirgedas 19.904000 06-07-2012 @ 07:11:18
3  Artem Karavaev 19.645500 06-05-2012 @ 09:50:07
4  Valery Pavlovsky 19.645500 06-05-2012 @ 23:19:08
5  Herbert Kociemba 19.645500 06-07-2012 @ 11:40:19
6  Il brigante Pennastorta 19.645500 06-07-2012 @ 13:14:12
7  Jarek Wroblewski 19.245700 06-04-2012 @ 08:14:00
8  Anton Voropaev 19.245700 06-04-2012 @ 15:38:59
9  Nick Gardner 18.865600 06-07-2012 @ 15:39:46
10  Natalya Makarova 18.396200 06-07-2012 @ 21:21:11

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

Ситуация с баллами очень напоминает конкурс с магическими квадратами. Тогда тоже человек 20 в начале таблицы имели результат 24 балла с хвостиком (максимум был 25 баллов). И распределение мест зависело от этого хвостика.

Кстати, очень интересный вопрос: как участники, занявшие места 3 - 6, умудрились набрать абсолютно одинаковое количество баллов?
И участники, занявшие места 7 - 8, тоже.
Я опять предположу, что применив ещё какой-то известный алгоритм, эти двое участников тоже наберут 19,6455 баллов

Ну, и что-то тормозят с применением известных алгоритмов участники, занявшие места 9 - 10

Да, действительно, я пока применила только алгоритмы для C простых и являющихся степенью простых чисел.

Тут писали ещё о других алгоритмах. Как я поняла, есть алгоритм для C=6. И ещё для некоторых C.

[Nataly-Mak]

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

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

Почему на картинке в программе в первом столбце только один символ? Почему квадрат не изображается в нормальном виде со всеми заполненными ячейками?

Вы неправильно ввели квадрат в программу. Надо вводить все цифры одной строчкой через запитую.

Однако ввод в программу Эда решения одной строкой весьма неудобен!

Мы ведь строим квадраты, в виде квадрата решение удобно просматривать.
И в описании задачи ведь приведён пример в виде квадрата.
И программа на конкурсе решения в виде квадрата принимает.

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



dimkadimon
Как вы думаете, сколько в этом решении цветов? В программе написано, что их 6. По количеству разных символов их тоже 6: A,B,C,D,E,F.
Никакого другого символа тут нет. Верно?
Однако при вводе этого решения на конкурс конкурсная программа говорит, что здесь 7 цветов!

Вот такая путаница.
Мне, например, так работать очень неудобно.

Программа Эда должна пpинимать решения как в виде одной строки, так и в виде квадрата (с перводом строк), и отображать оба вида решений одинаково в форме правильного квадрата.

Если Эда по-прежнему интересуют замечания по его программе, передайте ему, пожалуйста, моё замечание.
Я там, на форуме конкурса, дала ссылку на этот топик, но, похоже, Эд сюда не заглядывает.
Понимаю, ему трудно читать по-русски. А мне, к сожалению, трудно читать и писать по-английски.
Я бы написала своё замечание на форуме конкурса, но по-русски писать неудобно, а первод Гугл сделает такой, что никто ничего не поймёт.

Сейчас запостила на форуме конкурса просьбу Эду посмотреть этот пост.

-- Пт июн 08, 2012 05:30:53 --

Ну, наконец-то получился 6-цветный квадрат 26х26, осталось совсем чуть-чуть - до квадрата 36х36

Предыдущее решение у меня было для C=6, N=625.
Вот тут уже процедура наращивания квадрата, то бишь достраивания.
И это легко делается в программе Эда.
Не знаю, как пойдёт следующий квадрат - 27х27, попробую.

Готовый алгоритм для C=6 пока не искала.

[Nataly-Mak]

6-цветный квадрат 27х27 тоже удалось получить, правда, уже не так легко.

Но этот метод у меня здорово осложняется форматом ввода решения в программу Эда, о чём я написала выше.
Если бы программа Эда нормально работала с решениями, вводимыми в виде квадрата (с переводом строк), было бы гораздо проще.

Вот сейчас, например, я имею 6-цветный квадрат 27х27, мне надо его достроить до квадрата 28х28; достраивание я выполняю вручную (не в программе). Затем мне надо ввести в программу полученный новый квадрат 28х28, а для этого (чтобы получить нормальное отображение квадрата в программе) я должна преобразовать решение в одну строку, то есть удалить все переводы строк. Ужас!

-- Пт июн 08, 2012 07:13:15 --

Что означает в таблице результатов кнопка "Hide"?
Нажимаю на эту кнопку и... ничего не происходит.

[dimkadimon]

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

6-цветный квадрат 27х27 тоже удалось получить, правда, уже не так легко.

Но этот метод у меня здорово осложняется форматом ввода решения в программу Эда, о чём я написала выше.
Если бы программа Эда нормально работала с решениями, вводимыми в виде квадрата (с переводом строк), было бы гораздо проще.

Вот сейчас, например, я имею 6-цветный квадрат 27х27, мне надо его достроить до квадрата 28х28; достраивание я выполняю вручную (не в программе). Затем мне надо ввести в программу полученный новый квадрат 28х28, а для этого (чтобы получить нормальное отображение квадрата в программе) я должна преобразовать решение в одну строку, то есть удалить все переводы строк. Ужас!

-- Пт июн 08, 2012 07:13:15 --

Что означает в таблице результатов кнопка "Hide"?
Нажимаю на эту кнопку и... ничего не происходит.

Ну вот опять вы чем то недовольны! Вам столько людей помогают, но всё равно этого недостаточно.

Почему бы вам не написать программу которая преобразают квадратный формат в формат программы Эда (и наоборот)? Почему бы вам не написать программу, как программа Эда, которая считает количество "плохих" прямоугольников и проверяет правильность решения? Эд не обязан делать никаких программ для вас. Вообще огромное спасибо за то что он сделал визуальную программу. Во многих других соревнованиях этого нет.

Вполне можно было догадаться:

Hide = спрятать решение
Show = показать решение

[Nataly-Mak]

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

Ну вот опять вы чем то недовольны! Вам столько людей помогают, но всё равно этого недостаточно.

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

Я не скрываю, что мне помогают технически. Вчера, например, один друг помог составить квадрат 256х256 на базе прямоугольника 16х256, который я сама составила из уникальных перестановок. Это была чисто техническая процедура; он выполнил её за одну минуту в Экселе. Я этого делать пока не умею, но при желании могу научиться, ничего там сложного нет, друг мне уже всё объяснил. Если мне придётся ещё выполнять такие процедуры, обязательно воспользуюсь Экселем. А я писала для составления квадратов 64х64 и 81х81 программы.

[а возможно, у меня и команда будет опять; и члены команды будут помогать уже не только технически; и это тоже вроде не запрещено правилами конкурса; собственно, я ещё ни в одном конкурсе не участвовала одна, начинаю одна, а потом ко мне кто-нибудь присоединяется; в прошлом конкурсе команда состояла всего из двух человек, считая меня]

На конкурсе представлена программа. Я даю справедливую критику этой программе.
Не обязаны делать никаких программ - не делайте.
Но если сделали, будьте добры внимательно отнестись к критике.
А на фига мне программа, которая нормально не работает?!

Цитата:

Почему бы вам не написать программу которая преобразают квадратный формат в формат программы Эда (и наоборот)? Почему бы вам не написать программу, как программа Эда, которая считает количество "плохих" прямоугольников и проверяет правильность решения? Эд не обязан делать никаких программ для вас. Вообще огромное спасибо за то что он сделал визуальную программу. Во многих других соревнованиях этого нет.

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

[а при таком отношении организатора конкурса к критике, пожалуй, так и сделаю]

Это Эд для меня программу делал? Вот какая неожиданность! А я и не знала

Цитата:

Вполне можно было догадаться:

Hide = спрятать решение
Show = показать решение

Виновата, не догадалась

Кстати, в программе показа решений где-то сидит ошибка. Нажимаю кнопку "показать решение" для C=10, у меня показываются сразу два решения - для C=9 и C=10.
И определить, где кончается одно и начинается другое, просто невозможно. А мне надо скопировать именно решение для C=10.

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

-- Пт июн 08, 2012 08:08:42 --

Вот картинка, на стыке двух решений: C=9 и C=10



Это в таблице моих решений (вкладка Mine).

Может быть, решение для C=10 начинается в той самой строке, где написано "10 81 6561", но кто его знает
Зачем мне показывают сразу два решения, если я прошу показать решение только для C=10?

Вот, опять чем-то недовольна

Может быть, я что-то делаю не так...
Но тогда поясните, пожалуйста, что именно я делаю не так. Как уже сказала, нажимаю кнопку "показать решение" напротив решения C=10, а мне выдают сразу два решения: для C=9 и C=10.

[Nataly-Mak]

Неповторенные рекорды:

14 184 33856  Alex Chernov @ 22:04:42 on 06-06-2012 1
15 187 34969  Dmitry Kamenetsky @ 08:31:54 on 06-08-2012 1
18 308 94864  Alex Chernov @ 22:07:18 on 06-06-2012 1
20 382 145924  Alex Chernov @ 22:11:32 on 06-06-2012 1
21 383 146689  Alex Chernov @ 22:15:33 on 06-06-2012 1

Вот это красиво! Это достойные результаты.
То, что получено по известным алгоритмам, это всё ерунда.

Кстати, вот решение у Алексея Чернова: C=20, N=382x382. И сразу же решение: C=21, N=383x383.
Предположу, что тут действовали так. Сначала из решения для C=20 получили решение для C=21, тоже квадрат 382х382; это делается элементарно. А потом 21-цветный квадрат 382х382 достроили до квадрата 383х383.

-- Пт июн 08, 2012 09:29:57 --

Прочитала на форуме конкурса последнее сообщение администратора.
Кажется, ожидается новая версия программы Эда?

Если так, то учесть замечания было бы очень кстати.

-- Пт июн 08, 2012 09:50:36 --

Виновата

С показом решений разобралась. Всё там правильно!
Просто решение для C=10 очень длинное, и я сначала подумала, что показаны сразу два решения.
И на старуху бывает проруха

[Nataly-Mak]

Вот это весьма интересно:

Цитата:

I just want to express my thanks for this contest. What is so fascinating for me is the mixture of

1. mathematical ideas and

2. programming skills

which are both necessary to get good results. Up to now I just worked on 1. and got insight in some parts of discrete mathematics I did not know before. All my ideas up to now are condensed in only 7 single lines of Mathematica code, which generate all my three different types of squares (exept n= 3 and 4, which I just copied from somewhere). All these solutions are highly regular, but I suppose that the better solutions are irregular and really need some programming.

Это пишет конкурсант, который сейчас на 5-ом месте. Как я поняла, он пока не писал никаких программ, работает по пункту 1 - математические идеи.
При этом говорит, что у него все решения получаются регулярными.

А что такое "регулярные решения"?

[Nataly-Mak]

Цитата:

Почему бы вам не написать программу которая преобразают квадратный формат в формат программы Эда (и наоборот)?

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

Ну и... допустим, я напишу программу для перевода строки в квадратний формат.
И мне придётся переводить "туда-сюда". Весёленькое занятие

А между прочим, программа Эда - это не только проверка и визуальный показ решения; это ещё и программа ручного поиска решений! В этом её основная ценность.

Как я уже писала, всё просто: достраиваю квадрат вручную и ввожу его в эту программу, в ней быстренько вручную нахожу решение (программа устраняет ошибки!).

[Nataly-Mak]

Ну, вот, уже легче стало в одну сторону знаю, как преобразовывать формат.

И получила ещё одно решение достраиванием и использованием программы Эда: C=6, N=28x28.
Не исключено, что этим способом можно дойти до N=36x36.

[Nataly-Mak]

Алгоритм, который я нашла в статье (ссылка на статью дана выше), основанный на уникальных перестановках, оказывается, работает не только для степеней простых чисел, но и для простых чисел.

Проверила для C=3.
Вот два ортогональных квадрата 3-го порядка:

1 2 3
2 3 1
3 1 2

1 2 3
3 1 2
2 3 1

выписываем из этих квадратов уникальные перестановки, их 6 штук, добавляем строки из одинаковых чисел и получаем базовый прямоугольник 3х9:

1 1 1
2 2 2
3 3 3
1 2 3
2 3 1
3 1 2
1 3 2
2 1 3
3 2 1

Пока всё очень просто. Дальше ещё проще: в базовом прямоугольнике 3х9 надо заменить числа 1, 2, 3 на соответствующие группы из трёх чисел:

1={1,2,3}
2={2,3,1}
3={3,1,2}

Всё! 3-цветный квадрат 9х9 готов:

1,2,3,1,2,3,1,2,3,
2,3,1,2,3,1,2,3,1,
3,1,2,3,1,2,3,1,2,
1,2,3,2,3,1,3,1,2,
2,3,1,3,1,2,1,2,3,
3,1,2,1,2,3,2,3,1,
1,2,3,3,1,2,2,3,1,
2,3,1,1,2,3,3,1,2,
3,1,2,2,3,1,1,2,3

И не надо делать никаких разбиений, как в алгоритме, который изложил Pavlovsky.

[Nataly-Mak]

Интереная лемма мне попалась при просмотре статей:

Если Gn,m strong-c-colorable, то Gn,cm strong-c-colorable.

Правда, не совсем понимаю, что это за "strong-c-colorable". Но если это как раз такие прямоугольники (квадраты), какие строятся по условию конкурсной задачи, то интересный вывод из этой леммы можно сделать для С=5.

[Zealint]

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

Правда, не совсем понимаю, что это за "strong-c-colorable".

Как же Вы так читаете посты других участников? Или просто не читаете?

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

В статье описывается strong c-coloring, то есть сильная раскраска из с цветов. Это когда нет ни одного прямоугольника в котором две левые вершины одного цвета и две правые вершины одного цвета. Например вот 2х4 2-coloring

1212
1221

но он не является strong 2-coloring из за самого левого 2х2.

-- Пт июн 08, 2012 18:19:42 --

Ой, забыл, что вам мои советы не нужны : )

[Nataly-Mak]

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

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

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

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

Я очень внимательно читаю все посты!
И вот ещё цитата, где тоже говорится про эти самые "strong C-coloring".
И тут излагается алгоритм построения как раз того, что нам нужно по конкурсной задаче.

Только dimkadimon так и не отвтил на мой вопрос: какая нам разница в видах раскраски? В условии конкурсной задачи где-нибудь сказано про эти виды?

Я привела 5-цветный прямоугольник 8х28 и сказала, что он удовлетворяет условию конкурсной задачи.
А dimkadimon сказал, что я неправильно понимаю. А что же неправильно я понимаю?
Вот это он так и не объяснил!
Похоже, что я всё правильно понимаю, это он не по делу выступил со своим коментом по поводу видов раскраски?

[Zealint]

Смысл в том, что strong coloring подходит под условие задачи, но вот разница: если раскраска strong, то она обязательно подходит под условия, но если раскраска подходит под условия, то не обязательно strong. Это означает, что шансов на то, чтобы построить strong раскраску меньше, чем построить обычную. Я не уверен, что strong раскраска вообще может существовать для таких размеров, которых уже достигли участники.