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

[Pavlovsky]

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

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

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

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

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

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

Второго места вам уже мало?

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

[dimkadimon]

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

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

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

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

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

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

[Nataly-Mak]

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

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

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

Цитата:

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

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

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

[Pavlovsky]

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) скорее всего есть.

[Nataly-Mak]

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

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

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

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

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

[Nataly-Mak]

Невероятно! Пятеро россиян в десятке сильнейших!

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

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

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

[Nataly-Mak]

Если я правильно понимаю, вот готовый полный 5-цветный прямоугольник 8х28:



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

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

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

[dimkadimon]

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

Если я правильно понимаю, вот готовый полный 5-цветный прямоугольник 8х28:

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

[Nataly-Mak]

Вот, я так и думала, что неправильно понимаю, точнее - вообще не понимаю
Вы не могли бы пояснить, чем отличаются эти три вида раскраски?

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

Кстати, программа Эда прямоугольники тоже может проверять, я уже пробовала. Правда, она выдаёт какое-то потолочное значение для 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 (если пока так и не поняли).

[Nataly-Mak]

Итак, ввожу в программу Эда приведённый выше прямоугольник 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 тоже не допускает никаких достраиваний, то есть они просто в принципе невозможны для этого квадрата.

[Zealint]

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

Но! Вполне возможно, что данный квадрат 25х25 тоже не допускает никаких достраиваний, то есть они просто в принципе невозможны для этого квадрата.

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

Цитата:

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

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

[Pavlovsky]

Лафа закончилась. На форуме конкурса, тоже обратили внимание на статью. Правда пока топчутся на месте, но это уже дело времени.
http://infinitesearchspace.dyndns.org/c ... ic-squares

[Nataly-Mak]

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

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

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

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

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

[Pavlovsky]

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

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

Вряд ли.

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

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

[Nataly-Mak]

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

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

Но! Вполне возможно, что данный квадрат 25х25 тоже не допускает никаких достраиваний, то есть они просто в принципе невозможны для этого квадрата.

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

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