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

[Zealint]

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

Он же сам признаётся: не знает, что такое регулярные решения.

Ну так и Вы не знаете : ) А когда Вам на это указывают, начинаете негодовать. Верный признак непонимания или нежелания разобраться. Ладно, как хотите; что мне нужно, я выяснил.

[dimkadimon]

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

dimkadimon
скажите, пожалуйста, вы получили 10-сильный прямоугольник 84х10?
Или вы достраивали большие квадраты 10-coloring, то есть от квадрата 92х92 к квадрату 93х93, потом к 94х94?
Помнится, вы писали давно, что нашли решение 94х94, а вот 10-сильный прямоугольник 84х10 не нашли. Хочу ещё раз уточнить.

Меня интересует, есть ли у вас опровержение моей гипотезы, что не существует 10-сильный прямоугольник 84х10.

Уточняю ещё раз. Я не получал сильную раскраску 84х10. Она может существовать, а может не существовать. На даный момент нет доказательств ни в одну и ни в другую сторону. Я получил 94х94 от 85-строчки Pavlovsky.

[Nataly-Mak]

dimkadimon
спасибо за уточнение.

А у вас есть 10-сильный прямоугольник 84х10 с ошибками?

[dimkadimon]

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

dimkadimon
спасибо за уточнение.

А у вас есть 10-сильный прямоугольник 84х10 с ошибками?

Есть, но в нём тоже 4 ошибки:

(Оффтоп)

6,1,2,1,3,4,5,2,5,1,
1,2,1,3,4,5,4,3,1,10,
2,1,3,4,5,2,3,1,10,2,
1,3,6,5,2,3,6,10,10,7,
3,4,5,10,3,6,10,10,7,10,
4,5,2,3,9,10,10,6,10,6,
5,2,3,1,6,10,7,10,2,4,
2,3,1,6,6,7,10,2,4,8,
3,1,10,6,7,10,2,4,3,7,
1,10,10,7,6,2,1,8,7,6,
10,10,7,6,2,4,8,7,2,10,
10,7,10,10,4,8,7,2,10,5,
7,10,2,4,8,7,2,10,6,5,
10,2,6,8,7,2,10,5,6,1,
2,4,8,7,2,10,5,5,1,5,
4,8,7,10,6,5,5,1,6,7,
8,7,2,6,10,5,6,5,7,4,
7,2,10,5,10,6,5,7,4,9,
2,10,4,5,9,5,7,4,9,1,
10,5,5,1,5,7,1,9,1,7,
5,5,1,5,7,4,9,1,7,5,
5,1,4,7,4,9,6,7,6,8,
1,5,7,4,1,6,7,5,8,8,
5,7,6,9,9,7,5,8,8,10,
7,4,9,1,7,5,8,8,10,8,
4,9,1,7,10,8,8,10,8,1,
9,1,7,5,8,8,10,8,1,4,
1,7,4,8,8,10,8,1,4,3,
7,5,8,8,6,8,6,4,5,10,
5,6,8,6,8,6,1,3,10,1,
8,8,10,8,9,4,3,10,1,8,
8,10,8,1,4,1,10,1,8,9,
10,6,1,4,3,10,6,8,9,9,
8,1,6,3,6,6,8,9,9,5,
6,4,3,6,9,8,9,9,6,9,
4,3,10,1,8,9,9,5,9,2,
3,10,1,8,1,9,5,9,10,4,
10,1,8,9,1,5,9,10,4,6,
1,8,9,9,5,9,10,4,2,5,
8,9,9,5,1,10,1,2,6,2,
9,9,4,9,6,4,2,5,10,9,
9,5,9,6,4,2,5,10,9,3,
5,9,10,4,2,5,10,9,5,3,
9,10,6,10,10,10,9,3,5,8,
10,4,2,5,6,9,3,3,8,3,
4,2,4,6,1,3,3,8,5,5,
2,5,10,9,3,1,8,3,6,4,
5,10,9,3,3,8,3,5,4,7,
10,9,3,3,8,1,5,4,7,8,
9,3,3,8,3,5,1,7,8,5,
3,3,8,3,10,4,7,8,6,3,
3,8,3,5,4,7,8,5,5,6,
8,3,5,4,7,8,5,3,2,6,
3,5,6,7,8,5,3,2,2,9,
5,4,7,8,10,3,2,2,9,6,
4,7,8,5,3,2,2,9,2,8,
7,8,5,3,2,2,9,2,8,4,
8,5,3,10,2,9,2,8,4,1,
5,3,2,10,1,2,8,4,1,9,
3,2,2,9,2,8,1,1,9,8,
2,2,9,10,8,4,6,9,8,6,
2,9,2,8,4,6,9,8,2,7,
9,2,8,4,9,9,8,2,7,7,
2,8,6,1,1,8,4,7,7,3,
8,4,1,9,8,2,7,6,5,7,
4,1,9,8,2,7,7,3,7,9,
6,9,8,10,7,7,3,7,9,4,
9,8,2,7,7,3,7,9,4,2,
8,2,7,7,3,7,9,4,10,3,
2,7,7,3,7,9,1,10,5,9,
7,7,3,7,1,4,10,3,9,7,
7,3,7,9,4,10,3,9,7,1,
3,7,9,4,6,3,9,7,1,1,
7,9,6,6,3,9,7,1,1,6,
9,4,10,3,1,7,6,1,2,1,
4,10,3,9,7,6,6,2,1,3,
10,3,9,7,9,6,4,1,3,4,
3,9,7,1,9,2,6,3,4,5,
9,7,1,1,2,6,3,4,6,6,
7,1,1,10,9,3,1,5,2,3,
6,6,10,2,5,3,4,6,8,8,
4,4,6,2,4,4,1,4,4,4,
1,6,5,2,9,1,2,7,5,2,
6,8,4,4,10,1,1,6,3,10

[Nataly-Mak]

Да, любопытно, существует ли такой прямоугольник.
Я пробовала искать от самых разных исходных прямоугольников, н-и-ч-е-г-о! Меньше 4 ошибок получить не удалось.

[dimkadimon]

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

Да, любопытно, существует ли такой прямоугольник.
Я пробовала искать от самых разных исходных прямоугольников, н-и-ч-е-г-о! Меньше 4 ошибок получить не удалось.

А зачем он вам? Решение 94х94 все равно уже нашли.

[Nataly-Mak]

Научный интерес

Там получается интересный набор из 10 латинских прямоугольников 9х10 с неполной последней строкой. Вот сделать эти прямоугольники попарно ортогональными равносильно задаче нахождения 10-сильного прямоугольника 84х10.

[dimkadimon]

Друзья, я сегодня нашёл C15N198! Значит всё таки можно улучшить старые решения. Как только Нейл откроет доступ к сайту я его выложу.

[Nataly-Mak]

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

Друзья, я сегодня нашёл C15N198!

Здорово! Поздравляю!

Конечно, улучшить можно, я в этом нисколько не сомневаюсь.
Думаю, что и 198х198 не предел.

Меня вот очень интересует метод, который здесь был показан Pavlovsky. Этот метод описан и в статье alexBlack.
Базовые матрицы и блоки, которыми эти базовые матрицы заполняются.

Но меня смущают некоторые расхождения в описании метода Pavlovsky и alexBlack.
Например, первое расхождение:
Pavlovsky пишет, что все элементы в базовой матрице (кроме первой строки и первого столбца) должны быть различны. У alexBlack этого условия нет.

Далее, Pavlovsky приводит ещё одно условие, которому должны удовлетворять элементы базовой матрицы:
A+D-B-C <>0 (mod N).
У alexBlack этого условия нет.

В статье alexBlack написано, что для С=6 было найдено 10 базовых матриц 5х5, что даёт решение C6N36.
Для С=10 тоже удалось сделать полный перебор, максимальная базовая матрица 8х8, что даёт решение C10N90.
Такой же результат получил и Pavlovsky.

А вот какую максимальную базовую матрицу можно получить этим методом для С=15

Матрица 12х12 дала бы решение C15N195, это уже не актуально.
Матрица 13х13 дала бы решение C15N210

Но вот возможна ли матрица 13х13

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

Кроме того, метод допускает расширение.
Всё описанное выше рассматривалось в предположении, что блоки (в терминологии Pavlovsky - унитарные латинские квадраты) составляются одинаково, а именно: циклическим сдвигом.
Но! У нас есть пример этого же метода в применении к С=8,9 и другим степеням простых, когда блоки составляются иначе, а базовая матрица суть таблица умножения.
Почему бы и для С=15 не попробовать другой способ составления блоков?

[Знаю, что для С=15 не существуют таблицы сложения и умножения.
Вместе с тем, ничто не мешает нам по-другому составлять блоки и для этих блоков искать базовую матрицу. Я не знаю, как именно "по-другому", надо думать.]

[Pavlovsky]

Может кому будет интересно. Алгоритм получения решений третьего класса. С помощью этого алгоритма получены все мои решения в конкурсе.
Берем за основу сильно окрашенный прямоугольник размером (С^2)х(С+1), заполненный С цветами. Для получения решения третьего класса надо добавить две строки, так что бы свойство сильноокрашенности сохранилось. При этом используется дополнительный цвет С+1. Одна строка очевидна - строка заполненная цветом С+1.
Долго безуспешно пытался добавить еще одну строку. Пока не понял в чем проблема. Исходный прямоугольник формировал стандартным образом, так что в нем появлялись длинные одноцветные строки. Когда понял, что они мешают, проблема была легко решена.

Пример для С=5. Красным выделены ячейки, которые надо заменить на число 6.

[Nataly-Mak]

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

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

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

Пример
исходный прямоугольник 9-сильный 81х10, результат - добавлено две строки и один цвет, 10-сильный прямоугольник 83х10:

[Pavlovsky]

Покритикуйте плиз качество гуглоперевода.

Цитата:

Description of the algorithm used to obtain all of my solutions in the current competition.
Is taken as the starting C-strong-colored rectangle (C^2)x(C+1). You need to add two lines, so that the property would C-strong-colored preserved. One line is obvious - the string filled with color C+1.

Long tried unsuccessfully to add another line. Until I realized what the problem is. Original rectangle formed in the standard way, so that it appeared the long-color line. When he realized that they were in the way, the problem was easily solved.

Example for C = 5.
http://www.imageup.ru/img221/1034993/plyusodin.jpg
Red color of the cell in which it is necessary to write the number 6.

[Nataly-Mak]

Так переводит сам Гугл

Цитата:

Длинные безуспешно пытался добавить еще одну строку. Пока я не понял, в чем проблема. Оригинальный прямоугольника, образованного стандартным способом, так, что она появилась в долгосрочной цвет линии. Когда он понял, что они были в пути, эта проблема легко решается.

Я уже насобачилась переводить туда-сюда
Раз этак десять переведу туда-сюда, вроде сносно получается.

Значит так: сначала перевожу свой текст на английский, потом этот английский текст скармливаю Гуглу опять же и перевожу его на русский. Если что-то очень плохо выглядит, тогда делаю изменения в оригинальном русском тексте и снова всё повторяю.

[venco]

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

Покритикуйте плиз качество гуглоперевода.

Ужасно. Без оригинала на русском понять практически невозможно.
Немножко поправил, чтобы смысл появился (стилистику ещё бы поправить тоже):

The algorithm I used to obtain all of my solutions in the current competition.
Take a C-strong-colored rectangle (C^2)x(C+1) as a starting grid. Then you need to add two lines so that the property of C-strong-colored is preserved. One line is obvious - it's a string filled with color C+1.

I've tried a long time to add another line without success, until I realized what was the problem - the original rectangle is formed in the standard way so it contains long single-color lines. When I realized that they were in the way the problem was easily solved.

Here is an example for C = 5.

The cells that need to be replaced with number 6 are colored red.

[Pavlovsky]

venco Большое спасибо. Согласен, над стилистикой надо поработать. Уж слишком сложные предложения получились. Надо их сделать проще и понятнее. Но увы сам я это не осилию. Я как та собачка все понимаю, но сказать не могу.

PS Еще немного подожду и отправлю как есть.