2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1 ... 73, 74, 75, 76, 77, 78, 79 ... 130  След.
 
 Re: Новый конкурс программистов
Сообщение26.07.2012, 13:56 
Аватара пользователя


21/02/10
1594
Екатеринбург
Nataly-Mak в сообщении #599539 писал(а):
Pavlovsky
вы можете подтянуться! Для вас будет вполне достойная позиция №3
Ещё один красивый алгоритм для С=15,21 и всё получится.


Все идет своим чередом, согласно воле всевышнего. Пытаюсь открыть четвертый класс, есть подвижки. Пробую другие подходы. Смотреть задачу из предыдущего моего поста. Может надо посмотреть решения для С=15,21. Есть кое какие наработки.

-- Чт июл 26, 2012 16:01:00 --

svb в сообщении #599558 писал(а):
Важное уточнение: $(A + D - B - C)\bmod (N + 1) \ne 0$

Принимается. Долго думал, решил что mod лишнее. Оказывается не лишнее.

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение26.07.2012, 14:16 
Аватара пользователя


20/01/10
766
Нижний Новгород
Pavlovsky
Цитата:
Принимается. Долго думал, решил что mod лишнее. Оказывается не лишнее.
Т.е. как бы добавляется один дополнительный цвет. Для $N=5$ в вашей формулировке получается целый класс окрасок для C6N36. Для $N=p-1$, где $p$-простое имеются очевидные "полевые" решения, обрезанная таблица умножения. Но вот почему для $N=9$ перебор дает отрицательный результат? Кстати и для $N=7$ тоже отрицательный результат.

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение26.07.2012, 14:22 
Аватара пользователя


21/02/10
1594
Екатеринбург
svb в сообщении #599576 писал(а):
Т.е. как бы добавляется один дополнительный цвет.


Вроде этот факт учтен.

Цитата:
Квадрат надо заполнить числами от 0 до N.

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение26.07.2012, 15:34 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Есть!!!

Цитата:
21 392 153664 Alex Chernov @ 15:29:29 on 07-26-2012 1

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение26.07.2012, 19:31 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
И ещё шаг:

Цитата:
21 393 154449 Alex Chernov @ 16:57:24 on 07-26-2012 1

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение27.07.2012, 06:57 
Аватара пользователя


21/02/10
1594
Екатеринбург
svb в сообщении #599576 писал(а):
Т.е. как бы добавляется один дополнительный цвет. Для в вашей формулировке получается целый класс окрасок для C6N36. Для , где -простое имеются очевидные "полевые" решения, обрезанная таблица умножения. Но вот почему для перебор дает отрицательный результат? Кстати и для тоже отрицательный результат.

Сергей раскрываем карты? Или так полунамеками и будем общаться? Может к теме кто то еще подключится?!

-- Пт июл 27, 2012 09:14:17 --

Nataly-Mak в сообщении #599731 писал(а):
И ещё шаг:

Цитата:
21 393 154449 Alex Chernov @ 16:57:24 on 07-26-2012 1


И все таки Алексей одну строчку заныкал. Я ожидал результат C21N394. :D

-- Пт июл 27, 2012 09:25:57 --

Цитата:
21 394 155236 Alex Chernov @ 09:23:58 on 07-27-2012 1


Ловко я Алексея на чистую воду вывел! Не удалось спрятать! :D

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение27.07.2012, 08:09 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Не-а, не вывели, у него ещё пара строк припрятана :D

А я разобралась со своим регулярным решением C14N184 (второй класс).
Да, от него мне удалось получить решение C15N186.
Но такое решение у меня уже было получено от решения С14N185 в третьем классе.

Итак, с оценкой "отлично" перехожу в третий класс.
А вот в третьем классе я пока двоечница :D
Решение C14N185 у меня есть, но оно нерегулярное.
Однако мне удалось получить от него решение C15N187.
Чуть не хватило до C15N188, как раз одну строку не могу добавить :-(

Ну, ничего, может быть, научусь ещё :?

Да, а во втором-то классе надо ещё попробовать решение C21N384 получить. Это должно получиться, т.к. решение C20N382 у меня регулярное в этом классе.

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение27.07.2012, 12:12 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Уф! Одолела решение C21N384 во втором классе.
Теперь этот класс полностью закрыт.

Цитата:
6 Jarek Wroblewski 19.821700 07-09-2012 @ 09:37:20
7 Valery Pavlovsky 19.821700 07-23-2012 @ 21:46:25
8 Natalya Makarova 19.790400 07-27-2012 @ 13:04:36

Такие хорошие джентльмены не берут двоечницу из третьего класса в свою компанию :D
Всего каких-то 0,0313 балла не хватает :-(

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение27.07.2012, 12:22 
Аватара пользователя


20/01/10
766
Нижний Новгород
Pavlovsky
Цитата:
Сергей раскрываем карты? Или так полунамеками и будем общаться? Может к теме кто то еще подключится?!
Можно и раскрыть:
Изображение
Требований к базовому квадрату особых нет. Путь достаточно тупиковый.

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение27.07.2012, 12:31 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Удивительно! Большинство конкурсантов работает в группе решений C=10,12,14,15,18,20,21.

Изображение

Правда, у Алексея Чернова решения C=15,21 совсем другой категории, нежели у большинства конкурсантов.

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение27.07.2012, 12:58 
Аватара пользователя


21/02/10
1594
Екатеринбург
svb в сообщении #599998 писал(а):
Требований к базовому квадрату особых нет. Путь достаточно тупиковый.


Тогда начну с квадрата опубликованного Сергеем. Кстати мое решение C6N36 один в один такой квадрат. Решение C6N36 нашло 20 человек, надеюсь остальные не посещают этот форум. Правда у Alexu007 всего C6N27, но вроде он принципиально не пользуется чужими решениями. :D В конце концов исключить Сергея из конкурса, в котором он не принимает участие, будет трудно. :D

Заполним последние 6 строк и колонок как показано на рисунке. Это будет Г-крюк (по терминологии Картеси) Тогда пространство над Г-крюком будет состоять из матрицы 5х5 где в каждой ячейке будет латинский квадрат 6х6.
Вариантов различных ЛК 6х6 окрашенных в 6 цветов миллион и еще пара. Простейшее решение, для сокращения перебора, ограничить круг используемых ЛК. Например возьмем первый попавшийся ЛК и циклическим сдвигом получим другие ЛК с другой раскраской. Итого получится 6 ЛК. Из них и будем достраивать наш квадрат. Пронумеруем ЛК от 0 до 5. В порядке циклического сдвига. 0 - исходный ЛК.
Получилалась задача:
Дано. Пусть дан квадрат 5x5. Квадрат надо заполнить числами от 0 до 5.
Определение. Прямоугольник вида
AB
CD
, где A,B,C,D числа в вершинах прямоугольника, будем называть запрещенным, если выполняется соотношение: $(A + D - B - C)\bmod (6) = 0$.
Необходимо заполнить квадрат так, чтобы в нем не было запрещенных прямоугольников.

Решений у этой задачи много. Вот еще одно
Код:
2   1   1   1   1
1   1   2   3   4
1   3   1   4   2
1   2   5   1   3
1   5   4   2   1


Увы этот подход не дает уже решений для C=8,10 и более.
Выход из ситуации видится в увеличении множества базовых ЛК из которых будем строить квадрат. Но как? Ничего умного пока не придумал.

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение27.07.2012, 13:14 
Аватара пользователя


20/01/10
766
Нижний Новгород
Pavlovsky
Цитата:
В конце концов исключить Сергея из конкурса, в котором он не принимает участие, будет трудно.
А может я захочу :-) . Но, увы, шансы мои тают :-( , хотя я честно продолжаю поиски.
Я сейчас завершаю отчаянную попытку для $C=15$, решил пожертвовать одним $C$ - в конце концов $C(C-1)$ для 15 дает 210, все лучше, чем ничего :-) . Лихо начал, но уже для $C=12$ перебор дал нулевой результат :-(

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение27.07.2012, 13:29 
Аватара пользователя


21/02/10
1594
Екатеринбург
Возможен другой вариант заполнения квадрата, предложенный svb.
Изображение
Пример для С=4.

Здесь под Г-крюком образовалась матрица 4х4 из ЛК 3х3. Причем в каждом ЛК должен отсутствовать один из 4-х цветов.

Для сокращения перебора можно выбрать 4 базовых ЛК в каждом остутствует один цвет. Из каждого базового ЛК циклическим сдвигом получить серию ЛК. Получается 4х3=12 ЛК.

Вот тут у меня сразу образовался затык.

Возможно ли вообще из этого множества ЛК строить значимые решения.

К тому же красивое условие $(A + D - B - C)\bmod (N + 1) \ne 0$ действует если ЛК принадлежат одной серии. А придумать просто проверяемое условие для всего множества ЛК пока не получилось.

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение27.07.2012, 13:56 
Аватара пользователя


20/01/10
766
Нижний Новгород
Была, уже забытая, идея покрутить матрицы вида
Код:
  *  0  0  0  0  0
  0  *  1  0  3  2
  0  0  *  2  1  3
  0  1  3  *  4  0
  0  2  0  1  *  4
  0  3  2  4  0  *
Закона получения квадратиков в звездочках не было найдено, но вручную, кажется, это удавалось.

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение27.07.2012, 14:09 
Аватара пользователя


21/02/10
1594
Екатеринбург
Ну и последнее.
Изображение
Для построения решения С6N36 достаточно построить сильноокрашенный прямоугольник 30х5. Как показано на рисунке. То есть заполнить матрицу 6х5 перестановками. В каждой перестановке все числа различны. В этом направлении присутсвуют все трудности предыдущих идей.
Отмечу только что перестановки полученные из базовой циклическим сдвигом подходят под основное условие $(A + D - B - C)\bmod (N + 1) \ne 0$.

Все свои карты я выложил.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 1937 ]  На страницу Пред.  1 ... 73, 74, 75, 76, 77, 78, 79 ... 130  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: YandexBot [bot]


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group