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

[Nataly-Mak]

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

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



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

Имеем хорошую заготовку для решения C=5, N=784. Осталось совсем чуть-чуть, достроить 20 строк

Вот этот 5-цветный прямоугольник для нашей конкурсной задачи годится?
Я понимаю так, что годится.
А dimkadimon говорит, что я неправильно понимаю.
А что же направильно?
Не годится этот прямоугольник нам?
Этот прямоугольник будет "strong 5-coloring"? Или какой он будет "5-coloring"?
В терминологии однако должна быть полная ясность.

Ага, кажется поняла. Этот прямоугольник "не strong". Правильно?
Ну, так для конкурсной задачи он всё равно годится.

-- Пт июн 08, 2012 22:25:21 --

dimkadimon
напрасно вы были так против моего замечания по программе Эда.

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

[Zealint]

Цитата:

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

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

[Nataly-Mak]

Эхма! Ну и накручено

Дык нам-то всё это зачем?
Ещё раз вопрошаю: для конкурсной задачи имеют значение все эти "strong"?
По-моему, не имеют.

По условию конкурсной задачи надо, чтобы в любом прямоугольнике все 4 вершины не были одного цвета. Вот и всё!
Приведённый мной 5-цветный прямоугольник 8х28 этому условию удовлетворяет.

[dimkadimon]

Есть три вида раскраски:

1. strong (с,с')-coloring
2. strong c-coloring
3. c-coloring

На конкурсе нужен третий вид. Все раскраски 2ого вида они так же раскраски 3ого вида, но не наоборот. Причём можно превратить strong c-coloring MxN в c-coloring Mx(Nc). Имено через это превращение в статье описывается нахождения 3ого вида для простых чисел с.

[Nataly-Mak]

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

Есть три вида раскраски:
Причём можно превратить strong c-coloring MxN в c-coloring Mx(Nc). Имено через это превращение в статье описывается нахождения 3ого вида для простых чисел с.

Вот-вот, именно эту лемму я и процитировала выше. Теперь полностью поняла её смысл.

-- Сб июн 09, 2012 05:42:04 --

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

Интереcная лемма мне попалась при просмотре статей:

Если Gn,m strong-c-colorable, то Gn,cm strong-c-colorable.

Вот эта лемма.

Виновата, наврала в цитате.
Gn,cm будет не strong-c-colorable, а c-colorable.

В том посте уже нельзя исправить ошибку, поэтому здесь исправляю.

Картинка из статьи

[Nataly-Mak]

Ещё раскраска

Показываю два решения C=3, N=81, полученные по двум разным алгоритмам:



По гармонии раскраски второе решение мне нравится гораздо больше

Первое решение построено по алгоритму, который описал Pavlovsky. Второе решение - по алгоритму, описанному мной (ссылку на статью приводила выше), построение решения по этому алгоритму здесь показано.

[Scryer]

Nataly-Mak писал(а):

Making this table for different c feels like playing Sudoku.

[Nataly-Mak]

Очевидное утверждение

Если квадрат NxN c-coloring, то следующий квадрат (N+1)x(N+1)

. . . . . . С+1
. . . . . . С+1
. . . . . . С+1
. . . . . . C+1
С+1 . . . С+1

будет (с+1)-coloring.

Пример

этот квадрат 9х9 3-coloring:

1,2,3,1,2,3,1,2,3,
2,3,1,2,3,1,2,3,1,
3,1,2,3,1,2,3,1,2,
1,2,3,2,3,1,3,1,2,
2,3,1,3,1,2,1,2,3,
3,1,2,1,2,3,2,3,1,
1,2,3,3,1,2,2,3,1,
2,3,1,1,2,3,3,1,2,
3,1,2,2,3,1,1,2,3

По указанному свойству получаем из этого квадрата квадрат 10х10 4-coloring:

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

Полезное свойство.

Кстати, решение C=3, N=81 элементарно достраивается программой Эда до решения C=3, N=100.
Например, из приведённого выше решения C=3, N=81 получаем в программе Эда такое решение C=3, N=100:

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

Из этого решения по указанному свойству элементарно получается решение C=4, N=121.

Приведённое выше решение C=4, N=100 элементарно достраивается в программе Эда до решения C=4, N=121:

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

А это решение тоже легко достраивается до решения C=4, N=144:

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

Интересно, можно ли дойти таким способом до максимального решения C=4, N=324.

-- Сб июн 09, 2012 09:44:56 --

Решение C=4, N=169 тоже довольно легко получилось:

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

Хорошая игрушка
Спасибо Эду!

[Nataly-Mak]

И решение C=4, N=196 получилось

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

[Nataly-Mak]

Итак, я завершила первый этап конкурса
Результаты:

2 4 16 1.000000 05-30-2012 @ 07:37:46
3 10 100 1.000000 05-30-2012 @ 15:39:17
4 18 324 1.000000 05-30-2012 @ 15:21:28
5 25 625 1.000000 06-01-2012 @ 05:26:42
6 28 784 0.604938 06-08-2012 @ 12:59:50
7 49 2401 1.000000 06-01-2012 @ 07:30:35
8 64 4096 1.000000 06-06-2012 @ 21:21:02
9 81 6561 1.000000 06-07-2012 @ 06:52:04
10 82 6724 0.777431 06-08-2012 @ 15:14:26
11 121 14641 1.000000 06-02-2012 @ 00:47:54
12 122 14884 0.828915 06-08-2012 @ 15:46:57
13 169 28561 1.000000 06-02-2012 @ 13:44:29
14 170 28900 0.853615 06-08-2012 @ 16:18:24
15 171 29241 0.836198 06-08-2012 @ 16:32:23
16 256 65536 1.000000 06-07-2012 @ 21:21:11
17 289 83521 1.000000 06-03-2012 @ 11:08:03
18 290 84100 0.886532 06-09-2012 @ 07:45:53
19 361 130321 1.000000 06-03-2012 @ 13:46:43
20 362 131044 0.898029 06-09-2012 @ 14:54:39
21 363 131769 0.893616 06-09-2012 @ 13:44:21
Total  764149 18.579275

Что здесь собственно моё? Это решение C=6, N=784, то есть всего 0,6 баллов. Всё остальное может получить любой конкурсант по известным алгоритмам.

Никакого удовлетворения от полученных результатов!
Задачу я ещё и не начинала решать как следует. Стоит ли начинать?

Алгоритм построения решения C=6, N=1296 так и не нашла (самой додуматься не получается, думалка плохая ).
Ну, если бы нашла, это дало бы мне ещё 0,4 балла. Они погоды уже не делают.

Мой прогноз такой: к концу конкурса в десятке сильнейших борьба будет за каждую тысячную (или даже десятитысячную) долю балла.
Уже сейчас почти все первые 10 конкурсантов (кроме одного) имеют более 19 баллов

1  Alex Chernov 19.925900 06-08-2012 @ 17:45:54
2  Tom Sirgedas 19.877800 06-07-2012 @ 07:11:18
3  Il brigante Pennastorta 19.877800 06-08-2012 @ 16:28:33
4  Nick Gardner 19.689100 06-09-2012 @ 12:46:53
5  Herbert Kociemba 19.667900 06-08-2012 @ 12:33:12
6  Artem Karavaev 19.619300 06-05-2012 @ 09:50:07
7  Valery Pavlovsky 19.619300 06-05-2012 @ 23:19:08
8  Jarek Wroblewski 19.219400 06-04-2012 @ 08:14:00
9  Anton Voropaev 19.219400 06-04-2012 @ 15:38:59
10  Wes Sampson 18.754200 06-09-2012 @ 04:46:41

Ну и куда дальше?..

Всё будет зависеть оттого, как много новых, доселе неизвестных решений найдут конкурсанты. А сделать это очень сложно.

[Nataly-Mak]

Ну, нет у меня готового алгоритма для C=6, не знаю я, где он лежит
Ну и чёрт с ним.
Придумывать самой намного интереснее!

Итак, у меня было для C=6 решение N=784.
Сейчас удалось построить решение N=900. До квадрата 30х30 додумалась
Остался последний шаг - додуматься до квадрата 36х36.

[Nataly-Mak]

Последний шаг разбился на мелкие шажочки
Одолела решение C=6, N=961.

Вот в этих шажочках и кайф!

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

[dimkadimon]

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

Ну, нет у меня готового алгоритма для C=6, не знаю я, где он лежит
Ну и чёрт с ним.
Придумывать самой намного интереснее!

Итак, у меня было для C=6 решение N=784.
Сейчас удалось построить решение N=900. До квадрата 30х30 додумалась
Остался последний шаг - додуматься до квадрата 36х36.

Ни у кого нет готового алгоритма для С=6. Я придумал сам. Для С=8 и С=16 были готовые алгоритмы, но я о них не знал и поэтому придумал сам.

[Nataly-Mak]

Стоп!
А как же вот это:

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

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

Но есть еще алгоритм! Для С=2K с решением С^2-C+1. Его знают 6 человек. Надо еще раз посмотреть статьи.

Это алгоритм для С=р^к+1, где р простое число и к>=1.

Если p=5, k=1, то ведь C=6.
Не так ли?
Так о каком алгоритме вы здесь говорили? По-моему, для C=6 он как раз подходит.

А также и для C=10, при p=3, k=2
и для C=12, при p=11, k=1
и для C=14, при p=13, k=1
и для С=18, при p=17, k=1
и для C=20, при p=19, k=1


Или я неправильно понимаю вашу формулу?

[dimkadimon]

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

Стоп!
А как же вот это:

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

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

Но есть еще алгоритм! Для С=2K с решением С^2-C+1. Его знают 6 человек. Надо еще раз посмотреть статьи.

Это алгоритм для С=р^к+1, где р простое число и к>=1.

Если p=5, k=1, то ведь C=6.
Не так ли?
Так о каком алгоритме вы здесь говорили? По-моему, для C=6 он как раз подходит.

А также и для C=10, при p=3, k=2
и для C=12, при p=11, k=1
и для C=14, при p=13, k=1
и для С=18, при p=17, k=1
и для C=20, при p=19, k=1


Или я неправильно понимаю вашу формулу?

Да но етот алгоритм не даст C=6 36x36, он даст только 31х31. Для 36х36 нет известного алгоритма, поетому считайте что те кто нашел 36х36 сделали открытие.