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

[svb]

Pavlovsky

Цитата:

Естественно она у меня есть.

В бумажном виде и с 70-ого года

[Nataly-Mak]

Да, Холл молодец, хорошую книгу написал.
Впрочем, не один только Холл, многие иностранцы очень большие молодцы
Ещё мне понравилась книга Д. Райзера, кажется, "Комбинаторный анализ" называется (могу ошибаться, точно не помню, ох уж эта забывчивость ну, нет у человека в мозгу ПЗУ, увы, всё он забывает: интегралы, поля, формулы для решений всяких уравнений и т.д. и т.п.; ИМХО не беда, что человек забыл формулу решения уравнения, её можно посмотреть в справочнике; главное, чтобы он в нужный момент понял, какое именно у него уравнение и какая ему нужна формула).
Так вот, отвлеклась в сторону, простите
Итак, иностранцы-то молодцы. А вот назовите мне хоть одну приличную книгу по латинским квадратам русского автора.
Я когда занималась ЛК, ничего не нашла. Мне даже дама из Швеции прислала ссылку на лекции некоего Таранникова. Да, лекции, конечно, читают в некоторых вузах. Посмотрела я эти лекции, банальщина, все хорошо известные вещи просто излагаются. То есть всё то, что можно найти в книгах зарубежных авторов. А где собственные результаты? Пересказывать я тоже умею В моих статьях много пересказов из англоязычных статей и книг. Но... хоть малая толика есть и собственных результатов.

Если кого интересует книга Д. Райзера (может, ещё не запаслись бумажным вариантом ), могу скинуть. Правда, у меня на английском языке, русского издания нет.

[svb]

Nataly-Mak

Цитата:

Если кого интересует книга Д. Райзера

Похоже вы меня принципиально игнорируете

[dimkadimon]

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

Nataly-Mak

Цитата:

Если кого интересует книга Д. Райзера

Похоже вы меня принципиально игнорируете

И не только вас...

А вот ее только попробуй проигнорировать.

[Pavlovsky]

Цитата:

1 Artem Karavaev 19.984500 07-25-2012 @ 11:03:47
2 Nick Gardner 19.947100 07-24-2012 @ 18:06:24
5 Dmitry Kamenetsky 19.915300 07-25-2012 @ 18:12:26

В стане лидеров оживление. Чего то рано. До конца конкурса еще больше месяца. И похоже люди окончательно перешли на перебор.

[Nataly-Mak]

Мне любопытно, когда оживятся конкурсанты с 9-10 позиции

Цитата:

7 Valery Pavlovsky 19.880200 07-23-2012 @ 21:46:25
8 Natalya Makarova 19.833100 07-23-2012 @ 20:46:07
9 Wes Sampson 19.776900 07-07-2012 @ 00:50:31
10 Tom Sirgedas 19.704500 06-07-2012 @ 07:11:18

Tom Sirgedas набрал 19,7 баллов всего за 9 дней от начала конкурса!

А некоторые ёжики (как я, например) почти два месяца ковыряются

[Nataly-Mak]

Россияне, украинцы иногда ходят парами. Американцы ходят толпами

Цитата:

52 Rob Garretson 4.810730 06-07-2012 @ 08:19:11
53 Cyrus 4.787500 06-08-2012 @ 19:37:05
54 Kyle Jones 4.725710 06-16-2012 @ 11:05:45
55 Ray Hartung 4.382130 05-31-2012 @ 05:41:38
56 Leon Bun 4.344590 07-02-2012 @ 19:26:05

Насчитала 21 американца. Ну, последних двух (администратора и его сына) можно не считать, администратор участвует ещё и как Niel Brewer, а сын просто так зарегистрировался, для численности.

Всё равно 19 из 87 - это почти 22%. Ужас!
Хотя россиян в этом конкурсе тоже немало.
Ещё много немцев.
Остальных умеренное количество (от 1 до 5).
Интересно, а сколько стран представлено на конкурсе?

-- Ср июл 25, 2012 22:26:49 --

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

Ещё мне понравилась книга Д. Райзера, кажется, "Комбинаторный анализ" называется (могу ошибаться, точно не помню...)

Ох и наврала про книгу
Сейчас открыла и посмотрела.
Герберт Дж Райзер
название у меня почему-то отсутствует, но судя по названию первой главы ("Основы комбинаторной математики") книга называется "Комбинаторная математика".
Книга написана в 1963 г. (!), переведена на русский язык в 1965 г., переводчик К. А. Рыбников. И у меня как раз русское издание (кстати, книга М. Холла тоже на русском языке; спутала с какой-то другой англоязычной книгой). В общем, давно всё это было, вот и забыла
Прошу простить мою забывчивость.
Да, и в книге Райзера есть глава 7, которая называется "Ортогональные латинские квадраты", вот эту главу я и читала в этой книге, когда занималась ЛК.

[Pavlovsky]

Некоторые результаты лидеров (по данным разведки).


-- Чт июл 26, 2012 08:49:40 --

Цитата:

41 Alexander Prokopchuk 7.982830 07-26-2012 @ 03:41:30
42 Victor Dimitriev 7.858300 07-21-2012 @ 10:50:36
43 Alexu007 7.765220 07-20-2012 @ 14:06:15

Alexu007 пока отстает в российско-украинском индивидуальном соревновании.

[Nataly-Mak]

Хорошо работает разведка

Добавлю:
Pavlovsky имеет точно такие результаты, как Wroblewski.

У меня близкие результаты:

93 135 185 186 308 382 383

Застряла в третьем классе

-- Чт июл 26, 2012 09:04:32 --

Получила прямоугольник 90х10 10-strong, в котором 79 ошибок. Решение C10N100 на горизонте
Горизонт, как известно, кажется очень близким, однако при приближении к нему он снова и снова отодвигается. Боюсь, что точно так будет и с решением C10N100.

[dimkadimon]

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

Получила прямоугольник 90х10 10-strong, в котором 79 ошибок. Решение C10N100 на горизонте
Горизонт, как известно, кажется очень близким, однако при приближении к нему он снова и снова отодвигается. Боюсь, что точно так будет и с решением C10N100.

Я могу получить 10-сильное 90х10 с 75 ошибками, но это ничего не значит. Эти ошибки очень тяжело убрать. У меня бывало что оставалась всего одна ошибка и я её не мог 3 дня убрать. Вообще начинаю думать что C10N100 может не существовать и что C5N26 возможно проще найти.

[dimkadimon]

Алексей нашел C15N196! На 4 лучше прежнего результата и на 5 больше чем у остальных. А я думал что N195 максимум.

Если он найдет C21N394 то победа почти в кармане.

[Nataly-Mak]

alexBlack
Браво, браво, браво!!! (в ладошки хлопаю по-настоящему )
Вы гигант русской мысли!
Я болею весь конкурс только за вас.

Вот это действительно классное решение. И для С=21 пока ведь непревзойдённое решение.
Так держать, Алексей!

Мало интересу "трясти" перебором. Интересно придумать новые алгоритмы.

-- Чт июл 26, 2012 14:17:22 --

Наша гордость!

Цитата:

15 196 38416 Alex Chernov @ 11:53:36 on 07-26-2012 1
21 390 152100 Alex Chernov @ 20:56:57 on 07-07-2012 1

Пусть иностранцы поломают голову

-- Чт июл 26, 2012 14:25:13 --

Положение в группе лидеров мне снова нравится. Надо немножко подтянуться Pavlovsky

Pavlovsky
вы можете подтянуться! Для вас будет вполне достойная позиция №3
Ещё один красивый алгоритм для С=15,21 и всё получится.

[Pavlovsky]

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

Увы, достаточно неудачный пример для экспериментов. Вот взгляните на таблицу смещений квадратика

Код:
0 0 0 0 0
0 1 2 4 5
0 2 4 1 3
0 3 1 5 2
0 4 3 2 1

Для подобной таблицы уже нет Перебором это быстро проверяется. Иначе я уже выложил бы решение

Задача по мотивам

Дано. Пусть дан квадрат NxN. Квадрат надо заполнить числами от 0 до N. Прямоугольником будем называть прямоугольник c вершинами в центрах клеток и сторонами,параллельными сетке.

Определение. Прямоугольник вида
AB
CD
, где A,B,C,D числа в вершинах прямоугольника, будем называть запрещенным, если выполняется соотношение: $(A + D - B - C)\bmod (N + 1) = 0$.
Это определение сильнее условий конкурса, так как A-A=A-A. И даже сильнее С-сильноокрашенного квадрата A-A=B-B. Но и построить надо квадрат небольших размеров.

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

svb утверждает, что построить квадрат для N=9 невозможно. А для каких N возможно?? И почему для N=9 невозможно??

-- Чт июл 26, 2012 15:34:16 --

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

Алексей нашел C15N196!

Офигеть ведь с утра он ввел C15N194. Когда успел еще пару строк добавить?! Какой будет результат для С21 боюсь представить!

-- Чт июл 26, 2012 15:45:33 --

Цитата:

1 Artem Karavaev 19.944500 07-25-2012 @ 11:03:47
2 Alex Chernov 19.941800 07-26-2012 @ 13:53:36

Первое место Артема Караваева устояло! Все таки в категории (10,12,14,18,20) заданий значительно больше чем в категории (15,21). Чем ответит Артем?! Откроет пятый класс решений?!

[Nataly-Mak]

Пока нет настоящего решения C10N100, выкладываю первое приближение:



В приближении 790 ошибок. Оно получено из раскраски 90х10 10-strong, в которой 79 ошибок. Интересно, что количество ошибок в результате расширения увеличилось ровно в 10 раз, каждая репликация повторяет те же 79 ошибок.

Ещё интересный факт: в приближении все 10 цветов занимают по 1000 ячеек!
Такое вот равномерное распределение. Только ведь наверняка все 10 цветов не чисты от ошибок. Вот в чём беда!

У кого есть лучшее приближение?

Если решение C10N100 не существует (что, однако, пока не факт!), то хотя бы найти самое лучшее к нему приближение.
Как я уже писала, для решения C6N37 у меня все приближения имеют минимум 36 ошибок.

Да, а для решения C10N100 у меня было самое первое приближение с 18575 ошибок, потом с 15000 ошибок... И вот найдено с 790 ошибками. Прогресс налицо

-- Чт июл 26, 2012 14:53:00 --

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

Первое место Артема Караваева устояло! Все таки в категории (10,12,14,18,20) заданий значительно больше чем в категории (15,21). Чем ответит Артем?! Откроет пятый класс решений?!

Всего 0,0027 балла. Уверена, что Алексей это отыграет!

[svb]

Pavlovsky
Определение. Прямоугольник вида

Цитата:

AB
CD
, где A,B,C,D числа в вершинах прямоугольника, будем называть запрещенным, если выполняется соотношение: C-A=D-B.
Это определение сильнее условий конкурса, так как A-A=A-A. И даже сильнее С-сильноокрашенного квадрата A-A=B-B. Но и построить надо квадрат небольших размеров.

Важное уточнение: $(A + D - B - C)\bmod (N + 1) \ne 0$