2014 dxdy logo

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

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




На страницу Пред.  1 ... 6, 7, 8, 9, 10, 11, 12 ... 130  След.
 
 Re: Новый конкурс программистов
Сообщение03.06.2012, 10:50 
Аватара пользователя
Nataly-Mak в сообщении #580111 писал(а):
Для вас конкурс закончился?


Конкурс еще не начался. Решения для C=5 и более далеки от теоретического максимума.

Конкурс начнется когда для C>=5 будут найдены решения больше чем С^2. Интересно кто первый это сделает??

-- Вс июн 03, 2012 12:51:55 --

Nataly-Mak в сообщении #580116 писал(а):
Второго места вам уже мало?

Второго места мне хватило бы за глаза, если бы оно было на момент окончания конкурса.

 
 
 
 Re: Новый конкурс программистов
Сообщение03.06.2012, 11:18 
Аватара пользователя
Nataly-Mak в сообщении #580111 писал(а):
Код:
1  Alex Chernov 20.000000 06-03-2012 @ 11:16:57
2  Jim Gillogly 17.127500; 06-03-2012 @ 10:48:58
3  Nick Gardner 16.579800 06-01-2012 @ 11:21:51

Браво, Алексей!

Для вас конкурс закончился? :D

От души поздравляю!!


От души поздравляю Алексея! Но должен предупредить что он скоро может потерять первое место когда Tom Sirgedas найдёт лучше результаты для С=15 и 21.

Да интересно кто первый найдёт больше чем С^2 для С>=5? Я нашёл 26х26 для С=5 где 5 неправильных прямоугольников. Вроде близко, но так далеко...

 
 
 
 Re: Новый конкурс программистов
Сообщение03.06.2012, 11:57 
Аватара пользователя
dimkadimon в сообщении #580131 писал(а):
Но должен предупредить что он скоро может потерять первое место когда Tom Sirgedas найдёт лучше результаты для С=15 и 21.

Хм... мы все ещё можем потерять свои места, конкурс в самом начале. Но Алексей первым получил 20 баллов! Это здорово. Пока он имеет все максимальные решения. Что будет дальше, посмотрим. Алексей ведь тоже не будет стоять на месте, и у него появятся новые результаты и для C=15, и C=21, и для других C.

Цитата:
Да интересно кто первый найдёт больше чем С^2 для С>=5? Я нашёл 26х26 для С=5 где 5 неправильных прямоугольников. Вроде близко, но так далеко...

А полный перебор здесь не проходит? Ну, как-то оптимизировать его немножко, чтобы был не совсем тупой перебор.

Какой теоретический максимум для C=5? N=841?

 
 
 
 Re: Новый конкурс программистов
Сообщение03.06.2012, 12:11 
Аватара пользователя
Nataly-Mak в сообщении #580143 писал(а):
Какой теоретический максимум для C=5? N=841?


Верхняя граница для максимума F(C)<С^2+C.

С=3 F(C)<12 есть решение F(C)=10. Доказано, что оно максимально возможное.
С=4 F(С)<20 есть решение F(C)=18. Доказано, что оно максимально возможное.
C=5 F(C)<30. Наверно решения 29х29(841) не существует. А вот решение 28х28(784) скорее всего есть.

 
 
 
 Re: Новый конкурс программистов
Сообщение03.06.2012, 13:19 
Аватара пользователя
Уф! Еле дождалась ввода решения для C=19.
Долго проверяется решение. Я уж думала, что вообще зависла. Ну, всё нормально, решение принято.

Итак, закончила с C простыми.
Теперь надо разобраться с C=8, 9, 16.

-- Вс июн 03, 2012 15:07:10 --

Кстати, о составлении исходного квадрата CxC для простых C.

Я начала вручную составлять такие квадраты по алгоритму из указанной выше статьи, начиная с C=5. Сначала составляла все разбиения на C групп, потом только несколько разбиений, а начиная с C=13 уже обошлась вообще без разбиений. Выявила все закономерности в таких квадратах. Теперь запросто могу составить такой квадрат для любого простого C без всяких разбиений.
И как я уже говорила, для составления квадрата C^2xC^2 мне достаточно одного исходного квадрата CxC.

 
 
 
 Re: Новый конкурс программистов
Сообщение03.06.2012, 15:19 
Аватара пользователя
Невероятно! Пятеро россиян в десятке сильнейших!

Код:
1  Alex Chernov 20.000000 06-03-2012 @ 11:16:57
2  Valery Pavlovsky 18.617900 06-03-2012 @ 11:36:45
3  Jim Gillogly 17.127500 06-03-2012 @ 10:48:58
4  Nick Gardner 16.579800 06-01-2012 @ 11:21:51
5  Natalya Makarova 16.367800 06-03-2012 @ 14:06:34
6  Herbert Kociemba 16.099100 06-02-2012 @ 19:56:53
7  Tom Sirgedas 15.929800 06-01-2012 @ 01:47:16
8  Artem Karavaev 14.207900 06-02-2012 @ 16:12:03
9  Anton Voropaev 13.089300 06-03-2012 @ 16:12:22

Симметрично так расположились :-)

Интересно, кто останется в десятке к концу конкурса...

 
 
 
 Re: Новый конкурс программистов
Сообщение04.06.2012, 02:10 
Аватара пользователя
Если я правильно понимаю, вот готовый полный 5-цветный прямоугольник 8х28:

Изображение

(это из той же самой статьи, о которой выше говорил Pavlovsky)

Имеем хорошую заготовку для решения C=5, N=784. Осталось совсем чуть-чуть, достроить 20 строк :-)
Может быть, в статье что-то говорится об этом прямоугольнике? Я ведь не читаю по-английски. Есть ли вообще возможность пристроить к этому прямоугольнику хоть одну строку? Или это максимально возможный 5-цветный прямоугольник?

Ну, достраивание мы уже проходили в теме "Магические квадраты" :wink:
Только там было другое достраивание - достраивался примитивный прямоугольник до примитивного квадрата. Суть процедуры однако похожа.

 
 
 
 Re: Новый конкурс программистов
Сообщение04.06.2012, 03:23 
Аватара пользователя
Nataly-Mak в сообщении #580569 писал(а):
Если я правильно понимаю, вот готовый полный 5-цветный прямоугольник 8х28:


Нет вы неправильно понимаете. В статье описываются три вида раскраски: strong (c,c')-coloring, strong c-coloring и просто c-coloring. Нам нужен имено третий вид, а этот 8х28 первого вида.

 
 
 
 Re: Новый конкурс программистов
Сообщение04.06.2012, 04:46 
Аватара пользователя
Вот, я так и думала, что неправильно понимаю, точнее - вообще не понимаю :D
Вы не могли бы пояснить, чем отличаются эти три вида раскраски?

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

Кстати, программа Эда прямоугольники тоже может проверять, я уже пробовала. Правда, она выдаёт какое-то потолочное значение для N. Но, надеюсь, что проверку на наличие ошибок она выполняет правильно.

Например, ввожу вот такой прямоугольник:

Код:
1,2,3,4,
4,3,2,1,
2,1,4,3,
3,4,1,2,
1,2,3,4,
3,4,1,2,
4,3,2,1,
2,1,4,3,
1,2,3,4,
2,1,4,3,
3,4,1,2,
4,3,2,1,
1,1,1,1,
2,2,2,2,
3,3,3,3,
4,4,4,4

Программа выдаёт: Colors 4, Size 8, говорит, что ошибок нет, и вот такое выдаёт решение:

Код:
A,B,C,D,
,C,B,A,
,A,D,C,
,D,A,B,
,B,C,D,
,D,A,B,
,C,B,A,
,A,D,C,
,B,C,D,
,A,D,C,
,D,A,B,
,C,B,A,
,A,A,A,
,B,B,B,
,C,C,C,
,D,D,D

Могу проверить и 5-цветный прямоугольник 8х28 в программе Эда. Если визуально не вижу ошибок, то программа их увидит.

-- Пн июн 04, 2012 06:05:15 --

Ох уж эти математики, вынули душу из задачи :-) Цифры, цифры... а где же раскраски?

Приведу небольшой раскрашенный квадрат, это решение C=3, N=81, построено по алгоритму, который описал выше Pavlovsky (из приведённой на сайте конкурса статьи).

Изображение

Решение это не максимальное, максимальное для C=3, N=100 (это решение, кажется, есть в той же статье).

Кстати, Zealint, если вы внимательно посмотрите на этот квадрат 9х9, поймёте, почему для его построения вполне достаточно одного квадрата 3х3 (если пока так и не поняли).

 
 
 
 Re: Новый конкурс программистов
Сообщение04.06.2012, 05:52 
Аватара пользователя
Итак, ввожу в программу Эда приведённый выше прямоугольник 8х28 из статьи:

Код:
1,1,5,4,3,3,2,2,
1,2,1,5,3,4,3,2,
2,1,1,5,4,3,3,2,
1,3,2,1,5,4,3,2,
2,1,2,1,5,3,4,3,
2,2,1,1,5,4,3,3,
1,5,3,2,1,4,3,2,
2,1,3,2,1,5,4,3,
3,2,1,2,1,5,3,1,
3,2,2,1,1,5,4,3,
1,5,4,3,2,1,3,2,
2,1,5,3,2,1,4,3,
3,2,1,3,2,1,5,4,
5,3,2,1,2,1,4,3,
3,3,2,2,1,1,5,4,
1,5,3,4,3,2,1,2,
2,1,5,4,3,2,1,3,
3,2,1,4,3,2,1,5,
4,3,2,1,3,2,1,5,
3,4,3,2,1,2,1,5,
4,3,3,2,2,1,1,5,
1,5,4,3,3,2,2,1,
2,1,5,3,4,3,2,1,
3,2,1,5,4,3,2,1,
5,3,2,1,4,3,2,1,
5,4,3,2,1,3,2,1,
5,3,4,3,2,1,2,1,
5,4,3,3,2,2,1,1

Программа выдаёт: Colors 5, Size 14, Errors 0. И вот такое решение:

Код:
D,E,E,D,C,C,B,B,
,B,A,E,C,D,D,D,
,A,B,E,D,C,C,B,
,C,B,A,E,D,C,B,
,A,B,A,E,C,D,C,
,B,A,A,E,D,D,E,
,E,C,B,B,D,C,B,
,A,C,B,A,E,D,C,
,B,A,B,A,E,C,A,
,A,B,A,A,E,D,C,
,E,D,C,B,D,D,C,
,A,E,D,D,A,E,C,
,B,A,C,B,D,E,D,
,C,B,A,B,A,D,C,
,C,B,C,A,A,E,D,
,E,C,D,C,B,A,B,
,A,E,D,C,B,A,C,
,B,C,D,C,B,A,E,
,C,B,A,E,D,A,E,
,D,C,C,A,B,A,B,
,D,E,D,B,A,D,E,
,E,D,C,C,B,B,A,
,A,E,D,D,C,B,B,
,B,A,E,D,C,B,A,
,D,B,A

Так какая же нам разница, какой здесь вид раскраски? Ведь условие конкурсной задачи выполняется: прямоугольник раскрашен в 5 цветов так, что вершины ни одного прямоугольника не одноцветны.

Вот только на мой главный вопрос я пока не получила ответа: допускает ли этот прямоугольник достраивание?
Если допускает, тогда действуем очень просто: в 9-ой строке пытаемся перебрать все возможные комбинации из 5 чисел, проверяя при этом выполнение условия раскраски.
Перебор, конечно, будет вязким.

Ещё можно пытаться достраивать известное решение C=5, N=625. Добавляем к этому квадрату одну строку и один столбец и... пошёл плясать перебор.
Но! Вполне возможно, что данный квадрат 25х25 тоже не допускает никаких достраиваний, то есть они просто в принципе невозможны для этого квадрата.

 
 
 
 Re: Новый конкурс программистов
Сообщение04.06.2012, 06:13 
Nataly-Mak в сообщении #580586 писал(а):
Но! Вполне возможно, что данный квадрат 25х25 тоже не допускает никаких достраиваний, то есть они просто в принципе невозможны для этого квадрата.

К сожалению, не получится, я пробовал. По крайней мере у меня возникшие в новой строке коллизии не убираются - нужно перестраивать весь квадрат.

Цитата:
Кстати, Zealint, если вы внимательно посмотрите на этот квадрат 9х9, поймёте, почему для его построения вполне достаточно одного квадрата 3х3 (если пока так и не поняли).

Да, вчера как раз понял. Надо просто отдохнуть немного для следующего рывка. Экзамены тут ещё...

 
 
 
 Re: Новый конкурс программистов
Сообщение04.06.2012, 07:56 
Аватара пользователя
Лафа закончилась. На форуме конкурса, тоже обратили внимание на статью. Правда пока топчутся на месте, но это уже дело времени.
http://infinitesearchspace.dyndns.org/c ... ic-squares

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

Связь с латинскими квадратами мне вообще пришла в голову в первую же минуту старта. Как я уже говорила, сразу ввела 20 латинских квадратов, набрала 14 баллов и покрасовалась на первом месте :-)
Любой латинский квадрат порядка n даёт решение задачи n^2 для C=n.

А вы бы помалкивали "в тряпочку", были бы теперь на первом месте :D

И нельзя сказать, что конкурсанты топчутся на месте, на 2-ое место вышел Ярослав Вроблевский. Уже не имеет 20 баллов Алексей Чернов; это означает, что какой-то из максимумов уже увеличен, и у Алексея этого максимума пока нет.

Я бы сказала, что россияне топчутся на месте :-) поэтому их отодвигают назад.

 
 
 
 Re: Новый конкурс программистов
Сообщение04.06.2012, 08:27 
Аватара пользователя
Nataly-Mak в сообщении #580597 писал(а):
А вы бы помалкивали "в тряпочку", были бы теперь на первом месте

Вряд ли.

Вроблевски первый разобрался в алгоритме. А то что знают двое, знает и сатана.

У Алексея Чернова есть классные результаты, например для С=6.

 
 
 
 Re: Новый конкурс программистов
Сообщение04.06.2012, 08:37 
Аватара пользователя
Zealint в сообщении #580589 писал(а):
Nataly-Mak в сообщении #580586 писал(а):
Но! Вполне возможно, что данный квадрат 25х25 тоже не допускает никаких достраиваний, то есть они просто в принципе невозможны для этого квадрата.

К сожалению, не получится, я пробовал. По крайней мере у меня возникшие в новой строке коллизии не убираются - нужно перестраивать весь квадрат.

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

 
 
 [ Сообщений: 1937 ]  На страницу Пред.  1 ... 6, 7, 8, 9, 10, 11, 12 ... 130  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group