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

[Nataly-Mak]

Alexu007 в сообщении #592206 писал(а):

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

Кстати, всего за несколько минут построила в программе Эда диагональное решение C=7, N=25x25. Строится очень легко!
...
Это уже 27х27, дальше туго идёт расширение.

Моя программа-рэндом нашла 7-33. Это говорит о чём?

Это говорит о том, что можно вообще не писать никаких программ

Цитата:

Кстати, как вам мои (alexu007) успехи? С помощью рэндома я буду твёрдым середнячком.

Потрясные успехи

[если написать решение C=2, N=4x4 (это без рэндома напишет каждый), содрать из Интернета решения для С=3, С=4, будет уже твёрдо 3 балла. На этом можно оганичиться. Уже успех! ]

Вот был конкурс с перекладыванием карт. В нём участвовали 360 человек. Можно было с потолка написать последовательность для каждого N, ввести её и запросто оказаться на 200-ом месте И чего мы (целой командой) голову ломали три месяца??? Эх, не было в нашей команде Alexu007! Он бы сразу сказал нам эту сногсшибательную идею.

Цитата:

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

Может. Смело рисуйте!

Многие содрали с Интернета решение C=4, N=18x18 (я в том числе ) Чего голову ломать там, где люди уже много лет её ломали? Спасибо людям!

-- Чт июл 05, 2012 08:39:04 --

Pavlovsky

(Оффтоп)

Наврала вчера. О построении ОЛК с помощью квази-разностных матриц написано не в теме "Латинские квадраты", а в теме "Магические квадраты" (стр. 38).
Идею попробовал реализовать tolstopuz. Там его подробный отчёт об этом.

Я пробовала реализовать этот алгоритм для ОЛК 4-го порядка, это прекрасно удалось. С ОЛК 10-го порядка, понятно, возникают вычислительные сложности. Но идея, как мне кажется, очень хорошая.

[Alexu007]

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

Может. Смело рисуйте!
Многие содрали...

Я подумаю. У меня пока мой честный трудовой результат.

[Pavlovsky]

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

Pavlovskyв одной из моих статей есть идея - использовать для поиска 3-х попарно ортогональных ЛК 10-го порядка квази-разностные матрицы. Эту идею пробовал реализовать tolstopuz.Где-то в теме "Латинские квадраты" есть его сообщение по этому поводу.Задача очень хорошая! Задача века Обязательно поучаствуйте.

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

[Nataly-Mak]

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

По ссылке проект распределенных вычислений. Участие сторонних мозгов не требуется. Просто предоставляешь свой компьютер для работы уже написанной программы.

А... Так это просто предоставить им свои вычислительные ресурсы.
Ну, это дело совсем плёвое

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

Кстати, я им подкинула свою идею Может, кто заинтересуется.
Мне там сообщили, что давно нарыли мою статью "Ортогональные латинские квадраты десятого порядка". Статья им понравилась

-- Чт июл 05, 2012 11:32:31 --

Моё "честное, трудовое" решение C=4, N=13x13; диагональное, построено за 5 минут в программе Эда:

13,13,A,A,C,A,D,B,C,D,B,C,A,C,D,A,C,A,D,B,C,D,B,C,A,C,D,B,C,A,D,B,C,D,B,C,A,C,D,B,A,A,D,B,C
,D,B,C,A,C,D,B,A,A,D,B,C,D,B,C,A,C,D,B,A,A,D,B,C,D,B,C,A,C,D,B,A,A,D,C,C,D,B,C,A,C,D,B,A,A,
D,C,D,D,B,C,A,C,D,B,A,A,D,C,D,B,B,C,A,C,D,B,A,A,D,C,D,B,B,C,A,C,D,B,A,A,D,C,D,B,B,C,A,C,D,B
,A,A,D,C,D,B,B,C,B,C,D,B,A,A,D,C,D,B,B,C,B,A,D,B,A,A,D,C,D,B,B,C,B,A,C

От максимального решения составляет 0,5216 балла. Совсем неплохо

[Nataly-Mak]

Идём дальше, немного испортим диагональность, получаем C=4, N=14x14:

14,14,A,A,C,A,D,B,C,D,B,C,A,D,D,B,A,C,A,D,B,C,D,B,C,A,C,D,B,B,C,A,A,B,C,D,B,C,A,D,D,B,A,C,A
,D,B,C,D,B,C,A,C,D,B,A,A,C,D,B,C,B,A,C,A,C,D,B,A,D,A,B,B,C,D,B,C,A,C,A,B,A,A,D,C,D,C,D,B,C,A
,C,D,B,A,A,D,C,D,D,D,B,B,A,C,D,B,A,A,C,C,C,B,D,B,C,A,C,D,B,A,A,D,C,D,B,B,A,C,A,C,D,B,A,A,D,
C,D,B,A,C,D,A,C,D,B,A,A,D,C,D,D,B,C,B,A,C,D,B,A,B,D,C,D,B,B,C,B,A,A,D,B,A,A,D,C,D,B,B,C,B,A
,C,C,B,A,C,D,A,D,B,A,D,B,B,C,D,C

Уже 0.6 балла!

И никаких программ! И всё честно
Далее пристраиваем к этому квадрату строку и столбец 5-го цвета, получаем: C=5, N=15x15, маловато, конечно, всего 0.36 балла, ну, для начала годится.

Кстати, диагональное решение для C=5 элементарно строится в программе Эда до N=17x17 (выше я показала это решение). Это уже лучше, чем 15х15.

Ну, а чтобы, к примеру, набрать около 1 балла, наверное, достаточно для каждого С ввести обычный латинский квадрат. Совсем без программ, даже и в программу Эда не надо заходить. А в конкурсе поучаствуют всё же
Как та муха, которая сидела на рогах вола - "Мы пахали..."

-- Чт июл 05, 2012 12:23:19 --

Верно утверждение: если существует Gn,m strong c-coloring, то существует
Gn,cm c-coloring.

Обратное утверждение верно?

-- Чт июл 05, 2012 12:25:31 --

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

Теорема 4.5 в любимой нами статье гарантирует существование прямоугольника 12x66 strong (10,2)-coloring.

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

Никто не знает...

[Nataly-Mak]

На конкурсе спячка, на форуме спячка

Обещали интересную борьбу впереди. И где борьба? Где значимые результаты?

Вот Jarek заиграл, может, он найдёт эти самые значимые... От него вполне можно ждать

[Nataly-Mak]

Ну, наконец-то компания джентльменов пополнилась

Цитата:

7 Tom Sirgedas 19.751700 06-07-2012 @ 07:11:18
8 Il brigante Pennastorta 19.751700 06-08-2012 @ 16:28:33
9 Natalya Makarova 19.751700 06-27-2012 @ 15:36:36
10 Jarek Wroblewski 19.751700 07-05-2012 @ 17:22:20

Кто следующий?

[Nataly-Mak]

Выше я показала прямоугольник 9х20 (раскрашен в 10 цветов), удовлетворяющий условиям леммы Макаровой-Беляева.
Мне удалось построить прямоугольник 81х20, удовлетворяющий условиям этой леммы.

И вот результат применения этой леммы (что бы там ни говорили, а лемма-то работает!) - прямоугольник 81х100 10-coloring:



Ну, кто смелый? Прямоугольник 94х20 (или 95х19, или... 100х20) надо раскрасить в 10 цветов, чтобы он удовлетворял условиям леммы Макаровой-Беляева.
Когда уже есть 81х20, меньше остаётся сомнений в том, что есть 94х20. Не так ли?

[Alexu007]

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

Идём дальше, немного испортим диагональность, получаем C=4, N=14x14:

Уже 0.6 балла!

И никаких программ! И всё честно
Далее пристраиваем к этому квадрату строку и столбец 5-го цвета, получаем: C=5, N=15x15, маловато, конечно, всего 0.36 балла, ну, для начала годится.

Кстати, диагональное решение для C=5 элементарно строится в программе Эда до N=17x17 (выше я показала это решение). Это уже лучше, чем 15х15.

Для С4 моя программа-рэндом мгновенно находит N15x15, и до 16х16 ну прям чуток не дотягивает, собирает 251 из 256, жаль... для C5 - N20x20, дальше результаты к сожалению довольно быстро падают: 27,33,43,48 и т.д., а время работы программы ещё быстрее растёт. Улучшить алгоритм перебора тоже пока не удаётся. Мне уже жаль свой ноут грузить такими задачами, хочу в выходные подрядить комп на работе.

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

[Nataly-Mak]

От очень красивого прямоугольника 81х100 10-coloring, только что полученного, было рукой подать до квадрата 92х92 10-coloring.

Ух! Покинула компанию очень приятных джентльменов

Цитата:

7 Natalya Makarova 19.772900 07-06-2012 @ 00:02:51
8 Tom Sirgedas 19.751700 06-07-2012 @ 07:11:18
9 Il brigante Pennastorta 19.751700 06-08-2012 @ 16:28:33
10 Jarek Wroblewski 19.751700 07-05-2012 @ 17:22:20

Замечу: решение получила с помощью леммы Макаровой-Беляева.

svb
Вперёд! Наша лемма работает!

-- Пт июл 06, 2012 00:17:33 --

Alexu007 в сообщении #592538 писал(а):

...без утомительной ручной работы.

Ручная работа для меня не утомительна, это так - просто развлечение.
Основная работа у меня - мозговой штурм. Вот это утомительно! Сейчас квадрат 92х92 сделала, аж дым валит из головы

И ровно в 24.00 сделала. В полночь случаются чудеса

[svb]

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

Ух! Покинула компанию очень приятных джентльменов

А говорили спячка.

Цитата:

svb
Вперёд! Наша лемма работает!

Застрял я, дальше результата Павловского никак не продвинусь

[Nataly-Mak]

Ах! Вам уже надо дальше результата Павловского

Ну, тогда берите выше - дальше результата Чернова!

Весь день валялась, вечером поднялась, разозлилась... и вот...

[Nataly-Mak]

alexBlack в сообщении #590430 писал(а):

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

Кажется Алексей наконец тоже нашел 93х93.

Ага, даже 100x93, дополнением strong 9-colorings.

У меня теперь тоже есть прямоугольники 10-coloring: 81х100 (показан выше), и 91х100.
Вроде есть и 92х100 (вот тут как раз добавление строки!), возможно, что дальше легко получить и 93х100.
Но с добавлением строк к прямоугольнику 91х100 (который получился очень регулярный, без всякой "тряски") пока не разбиралась.
Точнее так: строку я добавила, но только предварительно обрезала прямоугольник 91х100 до 91х92. Получилось регулярное решение 92х92.

Надо будет попытаться получить решение 93х93 из прямоугольника 91х100.

[Pavlovsky]

Браво Наталия, круто! Блин, опередили, только вчера решил продолжить строительство прямоугольника 100х20. Прямоугольник 36х12 построил мгновенно. Застрял на поиске прямоугольника 64х16.

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

У меня теперь тоже есть прямоугольники 10-coloring: 81х100 (показан выше), и 91х100.Вроде есть и 92х100 (вот тут как раз добавление строки!), возможно, что дальше легко получить и 93х100. Но с добавлением строк к прямоугольнику 91х100 (который получился очень регулярный, без всякой "тряски") пока не разбиралась.Точнее так: строку я добавила, но только предварительно обрезала прямоугольник 91х100 до 91х92. Получилось регулярное решение 92х92.Надо будет попытаться получить решение 93х93 из прямоугольника 91х100.

Так как вы оказались победителем в этой гонке. Дарю призовую идею.

Строки можно добавлять к прямоугольнику 81х20. А затем при репликации по лемме 4.3 эти строки просто копировать в новые копии исходного прямоугольника. Требования к этим дополнительным строкам простые.
1) не образовывалось запрещенных прямоугольников
2) В дополнителных строках в каждой колнке должны быть различные числа. То есть дополнительных строк может быть не больше 10(С).

Получается довольно не обременительный перебор. Надо собрать строку из 20-ти чисел.

[Nataly-Mak]

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

Так как вы оказались победителем в этой гонке.

Я пока ещё не победитель.
Победителем будет тот, кто найдёт 100х100 10-coloring, или для начала 94х94, т.к. текущий максимум 93х93.
У меня пока нет даже и 93х93.

В вашей призовой идее ничего не поняла.
То, что можно добавлять строки к прямоугольнику 81х20, - это понятно. Не только можно, но и нужно! В этом вся соль метода. Чем больше будет строк в этом прямоугольнике, тем лучше. Понятно и то, что строки надо добавлять так, чтобы выполнялись требования нашей леммы. Вот пока у меня только прямоугольник 81х20 с такими свойствами получился. Из него, применив лемму, сразу получила прямоугольник 81х100 10-coloring.

Кстати, результат 93х93 имеют уже четверо:

Цитата:

10 93 8649 Dmitry Kamenetsky @ 09:24:27 on 06-05-2012 4

Каменецкий (первым получил), Чернов. Кто ещё? Возможно, Караваев и Herbert.