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

[Nataly-Mak]

Эх, хоть чуть-чуть постоять рядом с великими

1 Andrew Morozov 7.812720 05-30-2012 @ 12:24:25
2 Jarek Wroblewski 7.810000 05-30-2012 @ 09:19:13
3 Natalya Makarova 6.687840 05-30-2012 @ 12:29:02
4 Mark Mammel 6.039020 05-30-2012 @ 09:02:09
5 Ray Hartung 5.652930 05-30-2012 @ 08:58:05
6 Wes Sampson 5.210190 05-30-2012 @ 11:35:27

[Nataly-Mak]

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

Кто-нибудь объяснит, как программа работает?

[Pavlovsky]

5 25 625 Jarek Wroblewski @ 11:04:36 on 05-30-2012
7 49 2401 Jarek Wroblewski @ 11:05:38 on 05-30-2012
11 121 14641 Jarek Wroblewski @ 11:06:25 on 05-30-2012
13 169 28561 Jarek Wroblewski @ 11:07:27 on 05-30-2012
19 361 130321 Jarek Wroblewski @ 11:19:13 on 05-30-2012

Wroblewski явно нашел алгоритм построения решения N=C^2

[Nataly-Mak]

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

-- Ср май 30, 2012 16:31:00 --

Да, весёленький старт

Это первый конкурс, в котором я участвую прямо со старта.
Активно народ подключается, уже 25 человек. Россиян пока трое, как всегда стесняются
Новый россиянин появился, Артём Караваев, в прошлых конкурсах я его не видела.

[Nemiroff]

Цитата:

Juha Saukkola нашел решение 17х17 для C=4. В статьях проблема 17х17 для C=4 числится как открытая. Вот так всегда. Кто то начинает с абсолютного нуля, а у кого то есть сильные домашние заготовки.

http://blog.computationalcomplexity.org ... 18x18.html
4-coloring остался только для матрицы 21*12, вроде бы. Для 2 и 3 цветов вообще все варианты рассмотрены.

[Nataly-Mak]

Мне пришло письмо от Дмитрия Каменецкого.
Думаю, что оно будет интересно всем:

Цитата:

Я не знаю как писать на новый форум, поэтому пишу тут. Как вы уже наверное догадались, задача спрашивает как покрасить доску NxN в C цветов чтобы не было ни одного прямоугольника с углами одного цвета. Чтобы использовать программу Эда, надо в самом начале нажать randomize. Это нужно чтобы обнулить все данные. Программа показывает прямоугольники только того квадратика который наведён мышкой. Задача решена для C<=4. Уже доказано что оптимальное решение для C=4 это N=18. Для C>5 известны лишь приближения.

Наверное, он хотел сказать, что для C>4 известны лишь приближения. Опечатка получилась.

Он прислал письмо через почту конкурса. Вот ведь: а я не знаю, как пользоваться почтой конкурса.

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

Вот такие у меня пока догадки
Вообще мне нравится, как Эд сделал программу, спасибо ему огромное.
Только ни фига не понимаю, как она работает.

Такой ещё вопрос:
ввожу решение. В некоторых случаях оно в программе отображается нормально, как в квадрате NxN, а в некоторых случаях почему-то всё сдвигается, в первом столбце только один символ остаётся. Вот этот момент совсем не понимаю. Хотя решение и в этом случае программа делает правильно. Умная программа!

[Nataly-Mak]

Дмитрий
вы читаете эту тему, судя по полученному сейчас второму письму.

Принимайте участие в обсуждении, пожалуйста!
На этом форуме всё точно так же, как на форуме ПЕН, где вы уже писали. Зарегистрируйтесь, как обычно это делается на всех форумах. И далее без проблем пишите в тему.

Мне вот непонятно немного, как работает программа Эда, вы могли бы пояснить эти непонятные моменты.
Это будет интересно не только мне.
----

Придумала простенький алгоритм для C=21. Весьма любопытно, что дальше будет. Но! дальше, увы, двигаться вручную вряд ли смогу
Нужна программа, а как её написать, не представляю. Вот же опять такая ситуация: вручную делаю, а программу написать не могу.

Алгоритм основан на циклическом сдвиге. Собственно этот алгоритм для меня не новость, я много занималась латинскими квадратами и прекрасно знаю, что такое циклический сдвиг. Как только прочитала описание задачи, недолго думая ввела все 20 решений в виде латинских квадратов. Кто видел старт, видел, как я блестяще стартовала
Набрала 14 баллов, вышла на первое место. Это было красиво!
Но, к сожалению, быстро закончилось, потому что латинские квадраты дали минимальные решения, и как только другие конкурсанты стали находить лучшие решения, я стремительно начала терять баллы.

Да, так вот решение для C=21 в виде латинского квадрата даёт всего N=441. Здесь 21 фишек разных цветов размещены в квадрате 21х21.
Затем начала применять свой алгоритм циклического сдвига.
(Кстати, посмотрела в Интернете решения, во многих тот же циклический сдвиг.)

Сейчас получила решение для C=21, N=5329, то есть уже построила квадрат 73х73.
Удивительно! Алгоритм работает. И весьма интересно, до какого N он будет работать.
На конкурсе для C=21 найдено решение в квадрате 273х273, то есть N=74529.

Если бы написать программу, можно было бы проверить, до какого N будет работать мой алгоритм.
И пока не знаю, что у меня получится для других C.
Теперь становится понятно, откуда в рекордах берутся такие огромные числа. Но вручную это невозможно сделать.

Хе-хе, я им там хорошо БД заполнила: для C=21 вводила решения на каждом шагу, то есть для каждого N. Может быть, ещё попробую 2-3 квадратика (квадратища!) построить

Фрагмент решения C=21, N=5329



Хорошо виден циклический сдвиг.

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

[Zealint]

Я вам хочу сказать, что алгоритм полного перебора для C=21 даёт гораздо лучшее решение, чем у Вас. Алгоритм простой:

Сначала красим всё наугад.
Если видим какой-нибудь прямоугольник, выбираем наугад одну из его четырёх вершин и перекрашиваем в случайный цвет.
Так делаем несколько миллиардов раз (пока не станет всё правильно). Этим алгоритмом легко получается NxN=116x116 (13456 балла).

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

[Nataly-Mak]

Цитата:

Я вам хочу сказать, что алгоритм полного перебора для C=21 даёт гораздо лучшее решение, чем у Вас.

А кто вам сказал, что у моего алгоритма предел N=116x116?
Так что насчёт лучшего ещё надо доказать!

И кроме того, мой алгоритм работает гораздо быстрее полного пребора. Никаких миллиардов вариантов! Вручную я дошла до квадрата 73x73.

Программу по моему алгоритму тоже можно написать за несколько минут.

[Pavlovsky]

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

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

Первая ссылка в описании
http://www.cs.umd.edu/~gasarch/papers/grid.pdf
"Rectangle Free Coloring of Grids"

If p is a prime and s ∈ N, then $G_{p^{2s},p^{2s}}$ is $p^s$-colorable

Чтобы полчуить результаты Wroblewski. Достаточно изучить эту статью и реализовать описанный там алгоритм.

[Nataly-Mak]

О! Я смотрела эту статью. Чтобы её изучить да ещё реализовать описанный там алгоритм, у меня мозгов точно не хватит. Один вид сложнейших формул меня сразу страшно напугал
Мне бы чего попроще.

Сварганила ещё один квадратик, N=75x75, оказывается, у меня уже до N=74 были построены квадраты. Вввела и этот результат, пополняю БД конкурса

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

Вот хвостик таблицы моих результатов:

Цитата:

19 625 0.004796 05-30-2012 @ 18:49:02
20 676 0.013967 05-30-2012 @ 18:58:58
21 5625 0.075474 05-31-2012 @ 09:54:47
Total 14360 4.962541

[Pavlovsky]

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

О! Я смотрела эту статью. Чтобы её изучить да ещё реализовать описанный там алгоритм, у меня мозгов точно не хватит.

Достаточно изучить главу 4.3. Собственно неспешно приступаю к изуечению этой главы. Может кто составит компанию?

[Nataly-Mak]

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

Собственно неспешно приступаю к изуечению этой главы. Может кто составит компанию?

Команду набираете...

Я тоже хотела бы обрести хороших помощников. В прошлом конкурсе у меня был замечательный помощник (с форума ПЕН). Он вообще-то совсем не программист и играл всё время вручную, но, тем не менее, получил несколько отличных результатов. В нашем 11-ом месте его заслуга огромна.
На этом форуме я уже отправила личное приглашение одному форумчанину, он пока молчит.

Ещё один квадратик смастерила - 76х76 для C=21

[Pavlovsky]

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

Команду набираете...

Призываю прежде чем кодить - изучить теорию.

Wroblewski получил результаты где количество цветов, простое число. Но согласно утверждению аналогичные результаты можно получить для количества цветов степень простого числа. То есть еще для C=8,9,16.

Например рекорд для C=16 принадлежит Алексею Чернову 128х128. Но этот результат можно как минимум удвоить до 256х256.

[Nataly-Mak]

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

Призываю прежде чем кодить - изучить теорию.

На изучение теории может уйти очень много времени. Конкурс уже закончится

Есть результат N=6084 для С=21.
До N=6400 вполне могу дойти, дальше сложно вручную.

Конечно, толку мало, потому что до максимума ещё как до Луны, но это ручная работа А она, как известно, всегда ценится очень высоко. Этот алгоритм я сама придумала, в этом вся прелесть моего участия в конкурсе. А на место плевать, пусть хоть будет тридцать-последнее

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

Пример
сейчас мой результат для C=21 N=6084, результат на конкурсе для этого C N=74529. Коэффициент K=0,0816.
Смотрим, что даст улучшение результата, например, до N=6400. Это даст всего 0,00427 балла.

Так что улучшать надо сразу на миллион