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

[Nataly-Mak]

Pavlovsky
спасибо за подробный ответ.
Я только не поняла, каким способом вы ищете матрицу для заполнения унитарными ЛК.
Вот вы пишете, что можно попытаться найти матрицу 8х8 для С=10. Но это опять же очень мало, это даст только решение C10N90. А матрицу 9х9 нельзя пытаться искать? Такая матрица дала бы решение С10N100.

---
Забросила на форум конкурса свою гипотезу.
Продублирую для тех, кто не посещает тот форум:

Цитата:

In the attachment you see a set of 10 mutually orthogonal rectangles 9x10 corresponding to the 10-strong coloring 83x10.
The last row of each rectangle there are three elements.
Hypothesis
is impossible to make a similar set of 10 mutually orthogonal rectangles 9x10, so that in the last row of each rectangle will be the four elements.
Please prove or disprove the hypothesis.

Просьба относится и ко всем форумчанам этого форума.
Набор из 10 попарно ортогональных прямоугольников 9х10, о котором говорится в сообщении, выложен чуть выше.

Ну, не получается у меня 10-сильная раскраска 84х10
Сильно подозреваю, что её вообще не существует в природе.
Всех спрашиваю, спрашиваю: кто нашёл? Никто не признаётся

Можно посмотреть здесь и то прикрепление, о котором говорится в сообщении.

[Pavlovsky]

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

Я только не поняла, каким способом вы ищете матрицу для заполнения унитарными ЛК.

Естественно перебором. Как говорил Сергей, перебором ищу математически строгие закономерности.

Есть масса способов сократить перебор.

1) Так как базовый ЛК я использую полученный циклическим сдвигом и все семейство унитарных ЛК тоже строится циклическим сдвигом. То появляется простое условие проверки отстутсвия запрещенных прямоугольников.
Квадрат из 4-х ЛК N-раскрашиваем, если (A+D-C-B)mod N≠0 ,где A,B,C,D номера латинских квадратов.

A   B
C   D

То есть не надо строить подквадраты из ЛК и проверять на наличие запрещенных прямоугольников.
2) Первую строку и колонку заполняем базовым ЛК (№1). При этом мы ничего не теряем.
3) Так как первая строка и колонка заполнена 1, то в оставшейся подматрице в строках и колонках не должно быть одинаковых чисел (номеров ЛК)
4) Вторую строку и колнку можно нормализовать. То есть числа, во второй колонке и строке составляют возрастающую последовательность.
5) И еще одна процедура сильно сокращающяя перебор. Пусть в текущем узле перебора мы перебрали все варианты и они оказались все негодными. То есть нужно делать возврат. Но тогда для каждого чилса i в текущем узле мы можем определить узел, выбор числа в котором сделал не возможным выбрать число i в текущем узле. Определим среди этих узлов для каждого i самый поздний узел v. Тогда возврат мы можем сделать сразу на несколько шагов назад, до узла v.

[Nataly-Mak]

Pavlovsky
жаль, что не находятся бОльшие матрицы. Такая красивая идея!
Но, может быть, вы не до конца выполнили перебор?

[Pavlovsky]

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

Но, может быть, вы не до конца выполнили перебор?

Конечно не до конца. С 1С-Преприятие много не наперебираешь. Но Сергей получил анологичные результаты. Может Сергею удастся построить матрицу 12х12 для С=15?? Правда для него искать результат C15N195 - зря терять время.

В этом направлении есть еще идеи. Так что копаем.

[svb]

Pavlovsky

Цитата:

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

Маленькое замечание. В целом, я могу подтвердить связь "полевого" (даже расширенного) подхода с сильной окрашенностью и ограниченность подобного подхода для больших $C$. Но, использование сдвигов базового квадратика при заполнении большого квадрата не всегда сводится к сильной окрашенности - пример $C=6$. К сожалению, и этот подход обрывается на $C=6$. Это пока не доказано, но это вопрос времени. Следующим возможным шагом могло бы быть использование произвольных перекрасок базового квадратика, но этот подход может натолкнуться на вычислительные трудности перебора. Использование подобного подхода для получения сильноокрашенного прямоугольника полностью эквивалентен подбору матриц $R$, о котором я недавно писал. Здесь вычислительные трудности не столь большие, но таким способом не удается найти даже C6N36.

Цитата:

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

Вот с подобным мне трудно согласиться. Поиск нового "языка задачи" нельзя назвать "погоней за миражами" и уж никак не опасен. При удачном выборе "языка" многие вещи могут стать очевидными. Ярким примером может служить подход Галуа при решении уравнений. Современная математика построена на подобном подходе, хотя у него есть серьезный недостаток при обучении - отрыв от конкретики - но это уже другая история

[Nataly-Mak]

(Оффтоп)

Вот в соседней теме тест прошла на шизофрению

И кстати, стишок свой там опубликовала, о котором тут упоминала.
Вот он

НА ГРАНИ СНОВИДЕНИЯ И БРЕДА

Мелькают тени моих видений…
Я сумасшедшая? или гений?
На грани сновидения и бреда
“С ума схожу иль восхожу?..”
Из сновидений ушла поэзия,
Ушла любовь…
Квадраты строю, квадраты строю
На грани сновидения и бреда.
Боюсь, что больше не проснусь
И не дострою мой самый лучший,
Мой самый главный,
Во сне построенный магический квадрат.

4 февраля 2009 г.

И сейчас опять квадраты строю "на грани сновидения и бреда"

Вчера удалось-таки найти 20-сильную раскраску 363х20. И это был очень хитрый финт Вот внезапно осенило после долгих мучений. Настроила уже около сотни 19-сильных раскрасок, и ни к одной из них 2 строки не добавляются. Вдруг озарение... делаю так и... две строки мгновенно добавляются к первой же 19-сильной. Ещё одна маленькая победа! Эх, к сожалению, очень редки подобные озарения.

Теперь никак не даётся 21-сильная 365х20 И ведь здесь достаточно даже 365х19, всё равно не получается, 6 ошибок - хоть застрелись.
Так и придётся сделать только решение C21N385. До C21N386 ёжик не дотягивает

А в это время Алексей Чернов находит C21N398

[Nataly-Mak]

Всё, надоело!
Ввела решение C21N385.
Так хотелось в компанию гениев втереться, но увы, не получилось

Цитата:

6 Jarek Wroblewski 19.793100 07-09-2012 @ 09:37:20
7 Valery Pavlovsky 19.793100 07-23-2012 @ 21:46:25
8 Natalya Makarova 19.788300 08-11-2012 @ 12:34:08

[про гениев не я придумала, dimkadimon написал о Вроблевском, что он "самый гениальный"

Цитата:

Кстати в этом соревновании есть очень силные участники, которые не раз в подобных соревнованиях выигрывали. Я говорю про людей как Tom Sirgedas, Wes Sampson, Jaroslaw Wroblewski (самый гениальный), Roland Postle, Il Brigante Pennasorta etc. Поэтому на мой взгляд даже войти в 10-ку лучших вполне хорошее достижение.

-- Сб авг 11, 2012 12:55:51 --



Нечто подобное у меня в мозгах

-- Сб авг 11, 2012 13:16:06 --

Да, итак, у меня есть следующие С-сильные раскраски:

класс 2:
10-сильная 82х10
12-сильная 122х12
14-сильная 170х14
15-сильная 172х14
18-сильная 290х18
20-сильная 362х20
21-сильная 363х20

кроме 15-сильной 172х14 здесь все раскраски регулярные. Хотя и 15-сильная регулярная здесь есть - 171х14.

класс 3:
10-сильная 83х10
12-сильная 123х12
14-сильная 171х14
15-сильная 173х14
18-сильная 291х18
20-сильная 363х20
21-сильная 364х20

Не смогла получить 21-сильную 365х20 в этом классе

класс 4:
10-сильная 84х10 5 ошибок
12-сильная 124х12 9 ошибок
14-сильная 172х14 18 ошибок
15-сильная 173х14 3 ошибки
18-сильная 292х18 39 ошибок

Подозреваю, что 10-сильная 84х10 вообще не существует. Однако не факт! И никто не опровергает и не доказывает мою гипотезу

[svb]

Как приятно попасть опять сюда после суточной борьбы с Trojan Winlock! Зараза редкая.

[Nataly-Mak]

И как её надо убивать? И где вы её подцепили?

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

[svb]

Nataly-Mak

Цитата:

И как её надо убивать? И где вы её подцепили?

Подцепил обычным путем - смотрел эху москвы, а в одном из комментариев была ссылка, на которую я зашел

Вот убивать было сложно. Загрузился с флешки, запустил сканер dr.Web - не помогло. В windows войти не могу, выйти в интернет не могу, в полном шоке. Переустановил windows в режиме ремонта - эффект 0.
Установил новый windows на диск D. В нем вышел в интернет, гуглом нашел информацию о вирусе, скачал AVZ и после многих попыток лечения все же удалось избавится, но это было что-то

Сейчас радуюсь.

[Vitaly12]

А как Вы вообще обнаружили, что подцепили вирус?

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

Nataly-Mak

Цитата:

И как её надо убивать? И где вы её подцепили?

Подцепил обычным путем - смотрел эху москвы, а в одном из комментариев была ссылка, на которую я зашел

Вот убивать было сложно. Загрузился с флешки, запустил сканер dr.Web - не помогло. В windows войти не могу, выйти в интернет не могу, в полном шоке. Переустановил windows в режиме ремонта - эффект 0.
Установил новый windows на диск D. В нем вышел в интернет, гуглом нашел информацию о вирусе, скачал AVZ и после многих попыток лечения все же удалось избавится, но это было что-то

Сейчас радуюсь.

[svb]

Vitaly12

Цитата:

А как Вы вообще обнаружили, что подцепили вирус?

Когда полностью заблокирован вход в систему и ты видишь только грозную заставку с требованием в течение 12 часов оплатить штраф по указанному телефону, то трудно не догадаться, что это вирус
Подробности нашел в интернете: http://sonikelf.ru/windows-zablokirovan-otpravte-sms-ili-naglost-vtoroe-schaste/

[Nataly-Mak]

Развлекаются люди по-разному... кому что... Богу - богово, Кесарю - кесарево

-- Сб авг 11, 2012 15:47:03 --

Выкладываю своё лучшее приближение к решению C10N94:



В раскраске 38 дырок; окрашивание любой дырки в один из цветов даёт одну ошибку, итого 38 ошибок.
По-моему, решение это совершенно бесперспективное, ибо такое в нём распределение цветов:

A - 883
B - 877
C - 877
D - 877
E - 875
F - 881
G - 881
H - 881
I - 883
J - 883

Можно ли кардинально изменить распределение цветов в раскраске, скажем, методом отжига? Возможно. Но у меня это не получилось.

Кстати, это решение получено из 85-символьной строки Pavlovsky.

[Alexu007]

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

Nataly-Mak

Цитата:

И как её надо убивать? И где вы её подцепили?

Подцепил обычным путем - смотрел эху москвы, а в одном из комментариев была ссылка, на которую я зашел

Вот убивать было сложно. Загрузился с флешки, запустил сканер dr.Web - не помогло. В windows войти не могу, выйти в интернет не могу, в полном шоке. Переустановил windows в режиме ремонта - эффект 0.
Установил новый windows на диск D. В нем вышел в интернет, гуглом нашел информацию о вирусе, скачал AVZ и после многих попыток лечения все же удалось избавится, но это было что-то

Сейчас радуюсь.

1. Ставим администратору пароль.
2. Создаём юзера
3. Работаем на компе от имени юзера без пароля.

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

Зато преимущества:

при улове "окна счастья" просто перезагружаешь комп, входишь в систему администратором (с вводом пароля) - там уже нет никакого "окна счастья" и всё работает, поскольку без знания пароля оно не может прописаться никуда кроме папок юзера ушастого. Запускаем восстановление системы - возврат на день-другой назад - ВСЁ. Перезагружаетесь, проблема исчезает. Можете продолжать увлекательное путешествие по порноресурсам сети. Главное - не лазать в инет админом.

Подхватывал эту гадость неоднократно в самых разных местах (кстати - на порно ни разу) - при соблюдении указанных мной правил лечится за 5-10 минут.

"Адью, до следующего раза,
Да не пристанет к нам зараза!!!"

[Nataly-Mak]

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

1. Ставим администратору пароль.
2. Создаём юзера
3. Работаем на компе от имени юзера без пароля.

Стоп, стоп!
Это вот так просто защититься?
А как это сделать надо? На домашнем компе это можно?
Научите, пожалуйста.

У меня да - есть какие-то там пользователи, то бишь - юзеры. А где сидит админ? Я его не видела ни разу. Ну, понятно, что админом тоже буду я. Как админа создать и поставить ему пароль?
Как потом создать юзера, то есть опять же меня только без пароля.

Далее, если "окно счастья" появится, надо перезагрузиться, да? А потом что?

-- Сб авг 11, 2012 21:54:59 --

Просматривала сейчас таблицу рейтинга участников.
Вот такая игра мне очень нравится:

Цитата:

22 Anton Voropaev 18.962000 06-04-2012 @ 15:38:59

Одна неделя! И почти 19 баллов. И никаких мучений и "трясок". Всё просто и красиво - непременно должно быть красиво!
Жаль, что Антон не является участником темы. Рассказал бы, как он так быстро управился