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

[Nataly-Mak]

svb в сообщении #586497 писал(а):

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

А задача с картами имеет какие-нибудь связи с интересными областями математики?
А задача с посадкой деревьев? (кстати, о связях этой задачи с областями математики есть в книге Гарднера, там очень солидный список).
А почему же не берётесь перечислять связи новой задачи с очень интересными областями математики? Перечислили бы. Очень интересно!

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

Так в чём же принципиальное отличие новой конкурсной задачи?

Цитата:

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

А мне кажется, что многие (и я в том числе ) именно "тупо" применили готовые алгоритмы.
И совсем даже не обязательно понимать механизмы создания этих алгоритмов, важно правильно понять сами алгоритмы, то есть механизм их действия, а не механизм их создания.

Впрочем, это моё мнение. Я его никому не навязываю. Ничего не утверждаю, ничего не доказываю, ни с чем не спорю

-- Пн июн 18, 2012 21:28:53 --

Кстати, интересный вопросик...
Тут dimkadimon выкладывал набор из 32 непересекающихся комбинаций из чисел 1,2,3,...,10. Он утверждает, что такие комбинации найти несложно.

Я посмотрела на эти комбинации. На мой взгляд в них нет никакой закономерности, совершенно хаотично числа в комбинациях расположены.
Могу предположить, что комбинации найдены простым перебором.
Думаю, что перебором можно найти и набор из более чем 32 комбинаций (я по программке добавления по одной комбинации запросто добавила к этому набору ещё 3 комбинации).
Но не пишу программу перебора, потому что это, вообще говоря, мало интересно. Ну, заставлю я машину сутки-двое-трое искать перебором эти комбинации. И что? Положим, найдёт их машина штук 80-85. И что мне это даст? Это даст мне максимум решение N=85x85.
Я абсолютно не напрягаясь получила решение N=82x82. Так на фига мне эта программа перебора?

[Scryer]

Есть много алгоритмов, а не только три. Может быть, есть только три "лучших" алгоритмы, но # 6 парень сказал на форуме, что он использует только один алгоритм, с 7 строк Mathematica, чтобы получить там (плюс опубликованных решений для цветной = 3 и цвет = 4).

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

Я сделал алгоритм, который делает цвет ^ 2 - цвет + 1 случай, но она должна быть отличной от той, другие нашли, потому что это дает 36x36 вместо 31x31 для цветов = 6. Кроме того, слишком медленно (пока) для цветных = 14 и выше.

Мои лучшие баллы в семи различных алгоритмов, а также опубликованы цвет = 3 и цвет = 4.

[Nataly-Mak]

Scryer в сообщении #586540 писал(а):

Есть много алгоритмов, а не только три.

Речь идёт о базовых алгоритмах.

Как я уже говорила, повторюсь (извиняюсь за повторение):
изложенный мной базовый алгоритм (основанный на лемме, найденной в одной из статей) работает для С простых и являющихся степенями простых, а также вообще для любых C, для которых можно найти некоторый набор уникальных перестановок или непересекающихся комбинаций. Я применила его, например, ещё для C=6.

Именно поэтому алгоритм назван базовым.

-- Пн июн 18, 2012 22:46:38 --

Написала программку формирования комбинаций длины 12 из чисел 1,2,3,4,5,6. Программа очень простая, она не делает полный перебор, а просто добавляет по одной комбинации пока это возможно.

Это просто лёгкий эксперимент; весьма интересно посмотреть вообще на такие комбинации.
Ну, вот сформировала набор из 7 таких комбинаций, это G7,12 strong-(6,2)-coloring:

1 1 1 1 1 1 1 5 5 5 5 3
1 2 2 2 2 2 2 1 1 1 1 1
2 1 3 3 3 3 2 1 2 2 2 2
1 2 3 4 4 4 3 2 2 3 3 4
1 2 4 3 5 5 4 3 3 2 4 5
1 2 5 5 3 6 5 4 4 4 2 6
1 2 6 6 6 3 6 6 6 6 6 2

Далее составила из этого исходного прямоугольника прямоугольник 7х36 6-coloring по лемме 4.3. Всё получилось!

Теперь у меня жуткий исследовательский интерес: возможно ли составить прямоугольник 36х12 strong-(6,2)-coloring!
Но программу полного перебора всё равно писать не буду. Скучно!

-- Пн июн 18, 2012 23:11:10 --

svb
только не говорите, что я себя обманываю

Программа моя, похоже, врёт, или я что-то совсем ничего не понимаю

Понимала так, что в strong-(6,2)-coloring могут повторяться только числа 1,2, остальные не могут. Так и в программу закладывала, но, видимо, ошиблась.
В исходном прямоугольнике 7х12 у меня поторяются также числа 2,3.

Но! прямоугольник-то 7х36 получился правильный, программа Эда в нём ошибок не показывает, вот он:

1,1,1,1,1,1,1,5,5,5,5,3,3,3,3,3,3,3,3,1,1,1,1,5,5,5,5,5,5,5,5,3,3,3,3,1, 
1,2,2,2,2,2,2,1,1,1,1,1,3,4,4,4,4,4,4,3,3,3,3,3,5,6,6,6,6,6,6,5,5,5,5,5,
2,1,3,3,3,3,2,1,2,2,2,2,4,3,5,5,5,5,4,3,4,4,4,4,6,5,1,1,1,1,6,5,6,6,6,6,
1,2,3,4,4,4,3,2,2,3,3,4,3,4,5,6,6,6,5,4,4,5,5,6,5,6,1,2,2,2,1,6,6,1,1,2,
1,2,4,3,5,5,4,3,3,2,4,5,3,4,6,5,1,1,6,5,5,4,6,1,5,6,2,1,3,3,2,1,1,6,2,3,
1,2,5,5,3,6,5,4,4,4,2,6,3,4,1,1,5,2,1,6,6,6,4,2,5,6,3,3,1,4,3,2,2,2,6,4,
1,2,6,6,6,3,6,6,6,6,6,2,3,4,2,2,2,5,2,2,2,2,2,4,5,6,4,4,4,1,4,4,4,4,4,6

Так где и что не так? В чём мои неправильные действия? В непонимании термина strong-(6,2)-coloring?

[Nataly-Mak]

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

там же написано, что он strong (5,3)-coloring.
Это значит, что если оба левых угла и оба правых угла имеют один цвет, то он у левых и правых углов разный, и от 1 до 3. Остальные ячейки красятся в 5 цветов по типу strong.

Вот читаю пояснение. Пытаюсь понять.
Это для strong (5,3)-coloring. Насколько я понимаю цифра 5 здесь означает количество цветов раскраски, а цифра 3 - то, что написано в пояснении.

А если для strong (5,2)-coloring? Тогда цвета одинаковых углов могут быть от 1 до 2? Я так поняла. Неправильно?

Похоже, перегрелась

-- Пн июн 18, 2012 23:28:20 --

Ещё, чёрт побери этот английский!

В лемме 4.3 применяется термин strongly (c,c')-cоlorable.
В других местах этой же статьи применяется термин strong (c,c')-coloring.

Это одно и то же или нет?

Скорее всего, опять сама себя спрашиваю

[Nemiroff]

strongly $(c,c')$-cоlorable - значит, что объект как-то там сильно раскрашиваемый. То есть, его можно сильно $(c,c')$ раскрасить. И применяется к объекту, который красится.
Вообще, суффикс -able можно перевести как -абельный (даже если реально такого слова в русском языка нет): cоlorable - раскрашивабельный.

strong $(c,c')$-coloring - это, собственно, раскраска. То есть, слово "coloring" буквально означает "раскраска".
Let $\varphi$ be a strong $(c, c )$-coloring - пусть $\varphi$ - это раскраска в сильном $(c, c )$ смысле (ну или как-то так).

[svb]

Об особенностях перевода. Вот читаем:

Nemiroff в сообщении #586668 писал(а):

strongly $(c,c')$-cоlorable - значит, что объект как-то там сильно раскрашиваемый. То есть, его можно сильно $(c,c')$ раскрасить. И применяется к объекту, который красится.
Вообще, суффикс -able можно перевести как -абельный (даже если реально такого слова в русском языка нет): cоlorable - раскрашивабельный.

Можно и так, но со словом "сильно" ассоциируется Илья Муромец. Далее "able" - способный, а слова с таким суффиксом являются характеристикой объектов, которые способны к чему-либо. Например, если квадрат можно раскрасить некоторым способом, то значит он способен на это. Слово же "strongly" в данном случае лучше перевести как "строгий", хотя это и не по словарю. Т.е. способен к более "строгой" окраске, а не к более "сильной". Окраска того же вида, но с дополнительно наложенными условиями.

При таком подходе к переводу мы складываем картинку нового для нас объекта, а это куда полезнее, чем "текстуальная" бессмысленность - вроде все правильно, но непонятно

[Nataly-Mak]

Вот оно - определение всех этих "strong coloring":

Цитата:

Def 4.1 Let c, c', n,m ∈ N and let χ : Gn,m → [c]. Assume c'≤ c.
1. A half-mono rectangle with respect to χ is a rectangle where the left corners are the
same color and the right corners are the same color.
2. χ is a strong c-coloring if there are no half-mono rectangles.
3. χ is a strong (c, c')-coloring if for any half-mono rectangle the color of the left corners
and the right corners are (1) different, and (2) in [c'].

[немножко подкорректировала цитату, вместо с0, например, написала с']

Перевожу в Гугле:

Цитата:

Def 4.1 Пусть с, с0 , П, т ∈ N, и пусть χ: Gn, м → [с]. Предположим, c0 ≤ с. 1.1/2 моно прямоугольник по отношению к χ представляет собой прямоугольник, где левый углы того же цвета и правый углы имеют такой же цвет. 2. χ является сильным С-окраски, если нет половины моно прямоугольников. 3. χ является сильным (с, с0 )-раскраска, если для любой полу-моно прямоугольник цветом левого угла и правом углах (1) разные, и (2) [c0 ].

[перевод не корректировала ничуть]

Ну и? или я совсем тупая, или этот перевод совсем тупой, а может, само определение идиотское?

Читаем по порядку:

"Пусть с,c',n,m принадлежат множеству натуральных чисел N".

Это понятно. Пусть принадлежат

Читаем дальше: "...и пусть χ: Gn,m → [с]".
Уже не понимаю. Что это означает? Возможно, это определялось выше (по тексту статьи), но я ведь весь текст выше не читала.

"Предположим c'<=c" - это понятно даже ёжику.

Всё! Дальше у меня ступор. Ни одного из пунктов 1,2,3 я абсолютно не понимаю.

Догадаваюсь, что в пункте 1 определяются прямоугольники с одноцветными левыми и одноцветными правыми вершинами - "half-mono rectangle".

Далее предполагаю, что в пункте 2 определяется "strong-c-coloring". И тут догадываюсь, что это такая раскраска, при которой нет ни одного, определённого в пункте 1, "half-mono rectangles".

С этим пунктом вроде более-менее понятно.

Пример (из статьи) ... сейчас скопирую...

А вот как определяется в пункте 3 "strong (c, c')-coloring", убейте меня, я не понимаю

[Nemiroff]

svb в сообщении #586672 писал(а):

Слово же "strongly" в данном случае лучше перевести как "строгий", хотя это и не по словарю. Т.е. способен к более "строгой" окраске, а не к более "сильной".

Это как будет угодно: если в русском языке еще нет устойчивого термина для этого понятия, можете обозвать наиболее удобным для себя образом.

svb в сообщении #586672 писал(а):

Далее "able" - способный, а слова с таким суффиксом являются характеристикой объектов, которые способны к чему-либо. Например, если квадрат можно раскрасить некоторым способом, то значит он способен на это.

Я бы все же сказал, не "тот, который способен", а "тот, над которым можно производить действие".
Вот нет слова "летабельный", но если бы было, оно бы означало "то, на чем можно летать".
А здесь "раскрашивабельный" - "который поддается раскраске".

svb в сообщении #586672 писал(а):

При таком подходе к переводу мы складываем картинку нового для нас объекта, а это куда полезнее, чем "текстуальная" бессмысленность - вроде все правильно, но непонятно

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

Цитата:

χ is a strong (c, c')-coloring if for any half-mono rectangle the color of the left corners
and the right corners are (1) different, and (2) in [c'].

Назовем $x$ сильно $(c,c')$ раскрашиваемой, если для любого прямоугольника с одноцветными левыми и одноцветными правыми вершинами цвета левых правых вершин различны и принадлежат $[c']$

Цитата:

svb
пока я писала своё сообщение, появилось ваше.

Не понял. А меня тупо не читают?

[Nataly-Mak]

svb
пока я писала своё сообщение, появилось ваше.

Я вчера до часу ночи тупо смотрела на определение, которое привела в своём предыдущем посте (ваш пост ещё не читала)
Так и отправилась спать, ничего не поняв
Сейчас поднялась в 5 утра, и опять тупо смотрю на это определение...

Нет, похоже, я совсем тупая

[dimkadimon]

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

Цитата:

Этот прямоугольник будет "strong 5-coloring"? Или какой он будет "5-coloring"?
В терминологии однако должна быть полная ясность.

там же написано, что он strong (5,3)-coloring.
Это значит, что если оба левых угла и оба правых угла имеют один цвет, то он у левых и правых углов разный, и от 1 до 3. Остальные ячейки красятся в 5 цветов по типу strong.

Тут zealint уже объяснил что такое strong (c,c')-coloring.

[Nataly-Mak]

Копирую примеры из статьи к приведённомму определению.

Example 4.2

1. The following is a strong 4-coloring of G5,8

1 1 1 4 1 1 4 4
2 2 4 1 2 4 1 4
3 4 2 2 4 2 4 1
4 3 3 3 4 4 2 2
4 4 4 4 3 3 3 3

2. The following is a strong 3-coloring of G4,6

1 1 3 1 3 3
2 3 1 3 1 3
3 2 2 3 3 1
3 3 3 2 2 2

Эти примеры понятны. В раскрашенных по данному типу прямоугольниках нет ни одного прямоугольника, в котором две левые вершины одного цвета и две правые вершины одного цвета.

Выше я дала свою интерпретацию strong с-coloring прямоугольникам. Такие прямоугольники дают а) уникальные перестановки или б) непересекающиеся комбинации.

Именно на этих strong С-coloring прямоугольниках основан базовый алгоритм № 1. И с ним всё понятно.

А вот базовый алгоритм № 2 основан как раз на strong (с,c')-coloring прямоугольниках.
И чтобы его понять. необходимо как следует понять определение этих самых strong (с,c')-coloring прямоугольников.

-- Вт июн 19, 2012 05:43:13 --

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

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

Цитата:

Этот прямоугольник будет "strong 5-coloring"? Или какой он будет "5-coloring"?
В терминологии однако должна быть полная ясность.

там же написано, что он strong (5,3)-coloring.
Это значит, что если оба левых угла и оба правых угла имеют один цвет, то он у левых и правых углов разный, и от 1 до 3. Остальные ячейки красятся в 5 цветов по типу strong.

Тут zealint уже объяснил что такое strong (c,c')-coloring.

Ну, я же вчера привела эту цитату! Опять не видели??? Ну, зачем повторять-то?

Непонятно объяснил, мне непонятно.

svb
тут пост на пост наезжает
извините, я пока не могу ничего понять.
Тут ещё с повторениями... ох... сдохнуть можно

Сейчас давайте по порядку... Не спешите...

(dimkadimon, убедительно прошу вас не делать больше повторений!)

svb

Вчера я привела прямоугольник 7х12, который должен быть (по моей задумке) strong-(6,2)-coloring.
Но он таковым вроде не является (наврала в программе), по моим понятиям.

Тем не менее, лемму 4.3 я к нему применила и получила прямоугольник 7х36 6-coloring, этот прямоугольник тоже показан.

Так где ошибка? Объясните мне, пожалуйста.

-- Вт июн 19, 2012 05:50:56 --

Повторяю этот прямоугольник 7х12:

1 1 1 1 1 1 1 5 5 5 5 3
1 2 2 2 2 2 2 1 1 1 1 1
2 1 3 3 3 3 2 1 2 2 2 2
1 2 3 4 4 4 3 2 2 3 3 4
1 2 4 3 5 5 4 3 3 2 4 5
1 2 5 5 3 6 5 4 4 4 2 6
1 2 6 6 6 3 6 6 6 6 6 2

И повторяю вопрос: является ли этот прямоугольник strong-(6,2)-coloring?

По моим понятиям не является!

-- Вт июн 19, 2012 05:57:08 --

Nemiroff в сообщении #586674 писал(а):

Цитата:

svb
пока я писала своё сообщение, появилось ваше.

Не понял. А меня тупо не читают?

Цитаты не надо делать из последующего поста в предыдущий. Тогда вас будут читать.

[svb]

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

Читаем дальше: "...и пусть χ: Gn,m → [с]".

Цитата:

Уже не понимаю. Что это означает? Возможно, это определялось выше (по тексту статьи), но я ведь весь текст выше не читала.

Здесь речь о конкретной раскраске, т.е. задается конкретное отображение. Любопытно следующее: если квадраты могут быть "able", т.е. способные к чему-либо, то про конкретную раскраску такого нельзя говорить - она либо обладает некоторым свойством, либо нет - появляется суффикс "ing" и новые определения уже для конкретных раскрасок (конкретных отображений) "strong c-coloring" и "strong (c,c`)-coloring "

И далее до полного понимания

[Nataly-Mak]

svb в сообщении #586681 писал(а):

Здесь речь о конкретной раскраске, т.е. задается конкретное отображение. Любопытно следующее: если квадраты могут быть "able", т.е. способные к чему-либо, то про конкретную раскраску такого нельзя говорить - она либо обладает некоторым свойством, либо нет - появляется суффикс "ing" и новые определения уже для конкретных раскрасок (конкретных отображений) "strong c-coloring" и "strong (c,c`)-coloring "

И далее до полного понимания

Спасибо, кое-что проясняется но ещё далеко не всё.

Мне бы про мой прямоугольник...



По-моему, этот прямоугольник не является strong-(6,2)-coloring из-за прямоугольничка с левыми вершинами цвета 3 и правыми вершинами цвета 2.
Это так? Или не так?

[svb]

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

По-моему, этот прямоугольник не является strong-(6,2)-coloring из-за прямоугольничка с левыми вершинами цвета 3 и правыми вершинами цвета 2.
Это так? Или не так?

Конечно, вы правы. Цвет 3 не входит в множество [1,2]

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

[Nataly-Mak]

А пока решается вопрос с этим прямоугольником, повторю лемму 4.3, которую я к этому прямоугольнику применила.

Лемма 4.3

Если Gn,m strongly (c,c')-colorable, то Gn,xm - c-colorable
где x=[c/c']

[пересказала своими словами, как поняла]

В статье приводится пример для прямоугольника G8,6 strong-(6,2)-coloring. Этот прямоугольник превращается по лемме в G8,18 6-coloring.

Кстати, там в прямоугольнике 8х18, по-моему, есть ошибка.

-- Вт июн 19, 2012 06:41:43 --

svb в сообщении #586684 писал(а):

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

По-моему, этот прямоугольник не является strong-(6,2)-coloring из-за прямоугольничка с левыми вершинами цвета 3 и правыми вершинами цвета 2.
Это так? Или не так?

Конечно, вы правы. Цвет 3 не входит в множество [1,2]

Ну, слава Богу! Уф!

Но... тогда почему к этому прямоугольнику применилась лемма 4.3?????
Я её применила и получила прямоугольник 7х36 6-coloring!!

Этот прямоугольник приведён выше (могу повторить). Программа Эда не показывает в нём ошибок

-- Вт июн 19, 2012 06:54:27 --

Вот пример из статьи, это С8,6 strong-(6,2)-coloring:

1 1 2 2 3 6
1 2 1 2 4 5
2 1 2 1 5 4
2 2 1 1 6 3
3 4 5 6 1 2
4 5 6 4 1 1
5 6 3 3 1 2
6 3 4 5 1 2

Из него по лемме 4.3 получается G8,18 6-coloring.

Я тоже применила лемму к своему неправильному прямоугольнику, он не strong-(6,2)-coloring. А прямоугольник 7х36 у меня получился 6-coloring.

Или он всё же не 6-coloring??

Вот этот прямоугольник:

1  1  1  1  1  1  1  5  5  5  5  3  3  3  3  3  3  3  3  1  1  1  1  5  5  5  5  5  5  5  5  3  3  3  3  1 
1  2  2  2  2  2  2  1  1  1  1  1  3  4  4  4  4  4  4  3  3  3  3  3  5  6  6  6  6  6  6  5  5  5  5  5 
2  1  3  3  3  3  2  1  2  2  2  2  4  3  5  5  5  5  4  3  4  4  4  4  6  5  1  1  1  1  6  5  6  6  6  6 
1  2  3  4  4  4  3  2  2  3  3  4  3  4  5  6  6  6  5  4  4  5  5  6  5  6  1  2  2  2  1  6  6  1  1  2 
1  2  4  3  5  5  4  3  3  2  4  5  3  4  6  5  1  1  6  5  5  4  6  1  5  6  2  1  3  3  2  1  1  6  2  3 
1  2  5  5  3  6  5  4  4  4  2  6  3  4  1  1  5  2  1  6  6  6  4  2  5  6  3  3  1  4  3  2  2  2  6  4 
1  2  6  6  6  3  6  6  6  6  6  2  3  4  2  2  2  5  2  2  2  2  2  4  5  6  4  4  4  1  4  4  4  4  4  6