2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5, 6, 7, 8 ... 130  След.
 
 Re: Новый конкурс программистов
Сообщение30.05.2012, 11:32 
Заблокирован
Аватара пользователя


22/03/08

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

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

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


22/03/08

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

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

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


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

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


22/03/08

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

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

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

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

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


20/07/09
3955
МФТИ ФУПМ
Цитата:
Juha Saukkola нашел решение 17х17 для C=4. В статьях проблема 17х17 для C=4 числится как открытая. Вот так всегда. Кто то начинает с абсолютного нуля, а у кого то есть сильные домашние заготовки.

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

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


22/03/08

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

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

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

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

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

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

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

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


22/03/08

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

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

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

Придумала простенький алгоритм для 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 квадратика (квадратища!) построить :D

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

Изображение

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

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

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


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

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

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

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


22/03/08

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

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

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

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

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


21/02/10
1594
Екатеринбург
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. Достаточно изучить эту статью и реализовать описанный там алгоритм.

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


22/03/08

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

Сварганила ещё один квадратик, 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

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


21/02/10
1594
Екатеринбург
Nataly-Mak в сообщении #578831 писал(а):
О! Я смотрела эту статью. Чтобы её изучить да ещё реализовать описанный там алгоритм, у меня мозгов точно не хватит.

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

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


22/03/08

7154
Саратов
Pavlovsky в сообщении #578833 писал(а):
Собственно неспешно приступаю к изуечению этой главы. Может кто составит компанию?

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

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

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

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


21/02/10
1594
Екатеринбург
Nataly-Mak в сообщении #578836 писал(а):
Команду набираете...

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

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

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

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


22/03/08

7154
Саратов
Pavlovsky в сообщении #578838 писал(а):
Призываю прежде чем кодить - изучить теорию.

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

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

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

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

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

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

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

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



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

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


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

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