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

[Nataly-Mak]

Ага, значит, с C3N10 рэндом справился. Молодец!
А вот для С=4 даже до 16х16 недотягивает.

[Nataly-Mak]

Решение C9N82 с одной пустой ячейкой (правый нижний угол), аналогичное решению C5N26:



Пустая ячейка при окраске в любой из 9 цветов даёт 9 ошибок.
Каждый цвет занимает 747 ячеек.

Наверное, аналогичные решения есть C7N50, C8N65.
А кто-нибудь пробовал построить решение C6N37? Сколько минимум ошибок удалось получить? У меня 36 ошибок.

-- Ср июл 18, 2012 13:55:51 --

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

Моё решение 3-10:

И моё решение C3N10:

10,10,B,A,A,C,C,B,C,B,B,A,C,B,A,B,B,C,A,A,B,C,A,A,C,C,A,C,B,A,B,B,C,B,B,A,C,A,A,B,C,A,A,B,C,A
,C,B,B,C,A,C,B,C,B,B,C,C,B,A,A,A,A,C,A,C,B,A,B,B,C,C,C,C,C,B,A,A,C,B,A,B,B,B,A,A,A,C,C,C,C,B,
C,A,B,C,B,B,A,C,A,B

У кого-нибудь есть красивые оригинальные решения C3N10, C4N18?
У меня и у Alexu007 решения нерегулярные, рэндомовские.

[Nataly-Mak]

Это оригинальное решение C3N10, которое выложил на форуме конкурса Tom Sirgedas:



Выше я уже выкладывала копию его картинки; не всё сразу поняла на этой картинке (там пробелы есть), сейчас записала в программу Эда и всё стало понятно.

10,10,A,B,B,C,C,A,C,A,B,A,C,A,B,B,C,A,A,C,A,B,B,C,A,B,A,C,A,C,B,A,B,B,C,A,A,C,C,A,A,B,A,A,C,C
,A,B,B,C,B,C,C,C,A,A,B,A,C,B,B,C,A,C,C,A,C,B,A,B,C,B,C,A,A,C,B,C,B,A,C,B,A,B,A,B,C,C,B,B,A,C,
B,A,B,A,B,B,C,C,C,A

[dimkadimon]

[quote="Nataly-Mak в [url=http://dxdy.ru/post596422.html#p596422]
-- Сб июл 14, 2012 17:55:32 --

Вот такая строка для С=10 получилась. Закономерностей море.

(Оффтоп)

[/quote]
Что-то очень мало вы выжали из 85-символьной строки.
Прямоугольник 92х100 10-coloring из этой строки получается легко:



Прямоугольник 93х100 у меня получился всего с 20 ошибками, а содержащийся в нём квадрат 93х93 имеет всего 13 ошибок. Увы, без ошибок не получается [/quote]
[/quote]

Расскажите пожалуйста как вы получили етот 92х100 из той 85-символьной строки?

[Pavlovsky]

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

[Nataly-Mak]

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

Расскажите пожалуйста как вы получили етот 92х100 из той 85-символьной строки?

Этот вопрос автору метода, пожалуйста

Pavlovsky
вы зря его отложили, как мне кажется.
Его надо дожать. Если не до 100х100, то хотя бы до 95х95.
Усовершенствуйте ваш напильник и должно получиться что-то приличнее, чем 91х91.

А быстро вы, однако, среагировали Не успела я дописать сообщение, как ваш ответ уже появился.

[dimkadimon]

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

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

идея №1: заполнять квадрат 26х26 сначала единичками (их надо записать в квадрат не менее 136), потом двойками и т.д.

Для начала надо найти хотя бы одно решение 26х26 заполненное единичками. У Tom Sirgedas есть такое решение. А у наших такое решение есть? В идеале надо найти все не изоморфные решения.

К решению можно предъявить дополнительные требования.

5 цветов распределить так первый цвет 136 штук, остальные цвета по 135 штук. 136*1+135*4=676=26*26.
136 распределить по колонкам(строкам) в 6-ти колонках 6 символов, в 20-ти колонках 5 символов.6*6+20*5=136.
135 распределить по колонкам(строкам) в 5-ти колонках 6 символов, в 21-ти колонках 5 символов.5*6+21*5=135.

Равномерное распределение всегда самое лучшее!

Я могу заполнить 26х26 138ю единичками что на 2 единички больше нужного, поетому решение 26х26 вполне может сушествовать. А вот 27х27 могу заполнить только 145ю единичками, значит 27х27 может не сушествовать.

-- 18.07.2012, 22:02 --

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

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

Расскажите пожалуйста как вы получили етот 92х100 из той 85-символьной строки?

Этот вопрос автору метода, пожалуйста

Pavlovsky
вы зря его отложили, как мне кажется.
Его надо дожать. Если не до 100х100, то хотя бы до 95х95.
Усовершенствуйте ваш напильник и должно получиться что-то приличнее, чем 91х91.

А быстро вы, однако, среагировали Не успела я дописать сообщение, как ваш ответ уже появился.

Ну да ладно, буду сам думать :) Кстати советую спрятать етот 92х100 - решение слишком хорошее и дает 0.957 баллов.

[Pavlovsky]

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

Усовершенствуйте ваш напильник

Я поработал над напильником улучшил результат с 89х89 до 91х91 дальше у меня дело застопорилось. Поэтому перкинулся на другие идеи. Сейчас работаю над алгоритмом для С=15,21 с оценкой C^2-2C. То есть над решениями С15N195 и C21N399.

[Nataly-Mak]

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

Я могу заполнить 26х26 138ю единичками что на 2 единички больше нужного, поетому решение 26х26 вполне может сушествовать.

А после единичек в квадрат 26х26 вам удалось вписать двойки?

[dimkadimon]

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

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

Я могу заполнить 26х26 138ю единичками что на 2 единички больше нужного, поетому решение 26х26 вполне может сушествовать.

А после единичек в квадрат 26х26 вам удалось вписать двойки?

Удалось, и даже тройки. А вот остальные не могу вписать без "дырок".

[dimkadimon]

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

Наверное, аналогичные решения есть C7N50, C8N65.
А кто-нибудь пробовал построить решение C6N37? Сколько минимум ошибок удалось получить? У меня 36 ошибок.

Моя гипотеза: для всех n=p^k, где p простое можно построить n-раскраску (n^2+1)x(n^2+1) с n ошибками базируясь на решении n^2 x n^2.

[Nataly-Mak]

dimkadimon
это уже не гипотеза, а теорема

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

...для С=5, элементарно строится квадрат 30х30 с вырезанным углом 5х5.
В общем случае. Для С=p^s строится квадрат размером C^2+C. С вырезанным углом СхС.

Я написала:

Цитата:

Наверное, аналогичные решения есть C7N50, C8N65.

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

Приведу иллюстрацию примера svb, уже ставшего классическим в этой теме:



Этот пример - замечательное доказательство теоремы, которую dimkadimon всё ещё считает гипотезой.

[Pavlovsky]

Tom Sirgedas на базе решения C4N18 разрабатывает решения C10N98 и C15N195! Насколько перспективно это направление?!

[Nataly-Mak]

Tom Sirgedas выложил квадрат 27х27 со 146 единичками (если я правильно поняла):

Цитата:

rectangle 27x27 with 146 cells filled

.. X...XXX...... ............

.. XXXX......... ............

XX ...X..XXX.... ............

.X ..X..X...X... XX..........

.X .X..X.....X.. ..XX........

.X X..........XX ....XX......

X. ..X.X......X. ......XX....

X. .X...X......X ........XX..

X. X........XX.. ..........XX

.. X.......X.... X.X...X.X...

.. X......X..... .X.X...X.X..

.. .X....X...... .X..X.X...X.

.. ..X...X...... ...X.X..X..X

.. ...XX........ X....X...XX.

.. ...X.X....... ..X.X..X...X

.. .X.....X...X. X..........X

.. .X......XX... .....X.X....

.. ..X....X....X ..X.......X.

.. ..X.....X.X.. ....X....X..

.. ...X.....X..X ...X..X.....

.. ...X......XX. .X......X...

.. ....X..X.X... ....X...X...

.. ....X...X...X .X.........X

.. .....X.X..X.. .....XX.....

.. .....X..X..X. ...X......X.

.. ......X..X.X. ..X......X..

.. ......X...X.X X......X....

Ссылка:
http://pastebin.com/82BVf17Q

[dimkadimon]

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

dimkadimon
это уже не гипотеза, а теорема

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

...для С=5, элементарно строится квадрат 30х30 с вырезанным углом 5х5.
В общем случае. Для С=p^s строится квадрат размером C^2+C. С вырезанным углом СхС.

Я написала:

Цитата:

Наверное, аналогичные решения есть C7N50, C8N65.

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

Приведу иллюстрацию примера svb, уже ставшего классическим в этой теме:



Этот пример - замечательное доказательство теоремы, которую dimkadimon всё ещё считает гипотезой.

Простите, но я тут не вижу никакого доказательства. Красивая картинка ето не доказательство! Поетому пока что ето гипотеза и не теорема.

-- 19.07.2012, 13:11 --

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

Tom Sirgedas на базе решения C4N18 разрабатывает решения C10N98 и C15N195! Насколько перспективно это направление?!

Такое впечатление что он их уже нашел и просто не выложил!