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

[Nataly-Mak]

DVN
Простите великодушно
Мне показалось, что у вас флаг Белоруссии.

И с логином удивительно.
Внизу (справа) на странице показывают, кто из участников ввёл новые результаты; вот я вас там видела в момент ошибки под именем "Виктор Ди". Далее, в самом сообщении об ошике фигурировало "Виктор Димитриев". Поэтому и подумала, что вы ввели такой логин.

Что-то у них не срослось... да

Кстати, если вы не так же ленивы, как ваш персональный соперник, и в состоянии прочитать эту ветку, наверняка можете в два счёта получить джентльменский набор решений №1, который даст вам сразу 19,7109 баллов (при текущих рекордах).

Pavlovsky даже разрекламировал этот набор на форуме конкурса
И почему до сих пор этот набор есть всего у 12 конкурсантов - никак в толк не возьму!

-- Вт июл 10, 2012 20:59:04 --

Посмотрела флаги Украины и Белоруссии...
Можно только с глубокого бодуна спутать: голубой - жёлтый, красный - зелёный.

Но я вроде вчера не пила

[Pavlovsky]

Возникла такая задача.

Преамбула. Простой вариант задачи.
Дано: Алфавит из N символов.
Необходимо. Составить, из символов алфавита, строку максимальной длины, чтобы любая соседняя пара символов была различна.

Задача легко сводится к поиску Эйлерова пути в ориентированном графе. Соответсвенно строится строка длиной N*N+1.

Сложный вариант задачи.
Дано: Алфавит из N символов.
Необходимо. Составить, из символов алфавита, строку максимальной длины, удовлетворяюющую условию:

Для каждого i (1<=i<=N-1). Любая пара символов находящихся на расстоянии i была различна. Расстоянием между двумя числами будем считать модуль разности их номеров позиции в строке.

Пример. Для алфавита {1,2,3,4} можно составить такую строку.
1,1,2,1,3,4,4,1,4,3,2,2,4,2,3,1

-- Ср июл 11, 2012 08:22:40 --

DVN в сообщении #594218 писал(а):

Свободного времени нет совсем, на победу не претендую. Но у меня персональный соперник - Alexu007. У нас метод аналогичный, результаты у меня чуть похуже.

Вызов брошен. Ждем принятия вызова от Alexu007. Зрители запасаются попкорном.
Исходные позиции:

Цитата:

41 Alexu007 7.511470 07-07-2012 @ 19:16:09
45 Victor Dimitriev 6.424870 07-08-2012 @ 18:05:18

[Zealint]

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

Преамбула. Простой вариант задачи.
Дано: Алфавит из N символов.
Необходимо. Составить, из символов алфавита, строку максимальной длины, чтобы любая соседняя пара символов была различна.

Вообще непонятно. Что значит "любая соседняя пара символов была различна"? Что такое различная пара и соседняя пара?
Например, 1,2,1,2,1,2 - это различные пары?

Цитата:

Зрители запасаются попкорном.

У меня ещё остался после наблюдения за темой про википедию в этом же разделе.

[Pavlovsky]

Zealint в сообщении #594328 писал(а):

Вообще непонятно. Что значит "любая соседняя пара символов была различна"? Что такое различная пара и соседняя пара?Например, 1,2,1,2,1,2 - это различные пары?

Выпишем все соседние пары символов из вашего примера
12 (позиции 1,2)
21 (позиции 2,3)
12 (позиции 3,4)
21 (позиции 4,5)
12 (позиции 5,6)
Как видите существует множество повторов пар 12 и 21
Возмем пример 1,1,2,1,3,4,4,1,4,3,2,2,4,2,3,1. Выпишем все соседние пары
11
12
21
13
34
44
41
14
43
32
22
24
42
23
31
Легко убедится что среди этого набора нет двух одинаковых соседних пар.
Выпишем теперь все пары находящиеся на расстоянии 2.
12 (позиции 1,3)
11 (позиции 2,4)
23 (позиции 3,5) и т.д
14
34
41
44
13
42
32
24
22
43
21
Опять в этом наборе нет одинаковых пар. Можно убедиться, что одинаковых пар нет и на расстоянии 3. То есть это решение удовлетворяет условиям сложной задачи.

[Nataly-Mak]

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

Возникла такая задача.

А что даёт эта задача применительно к конкурсной задаче?
Из чего она возникла?

Я подумала, что это даёт, например, характеристическую строку для диагонального решения. Проверила ваш пример в сложном варианте; взяла 15 первых чисел, попыталась по этой строке построить диагональное решение C4N8, нет, не получилось.

Зато характеристическая строка наобум построенного диагонального решения C4N8 у меня имеет такой вид:

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

Очевидно, что условия вашей задачи даже в простом варианте в этой строке чисел не выпоняются.

[Pavlovsky]

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

А что даёт эта задача применительно к конкурсной задаче?

Этого я пока не буду рассказывать. Так смутные идеи по поводу. Относитесь к этой задаче пока как к независимой задаче. Понравилась простота формулировки.

[whitefox]

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

Этого я пока не буду рассказывать. Так смутные идеи по поводу. Относитесь к этой задаче пока как к независимой задаче. Понравилась простота формулировки.

Так, прикинем.
Получается, что для решения C10N100 нужно построить строку по Вашим правилам при N=10 длиной не менее 98.
Это так?

[Pavlovsky]

whitefox в сообщении #594430 писал(а):

нужно построить строку по Вашим правилам при N=10 длиной не менее 98.Это так?

На самом деле достаточно 90. А может еще меньше. Если повезет, может оказаться достаточным и 80.

-- Ср июл 11, 2012 17:25:55 --

Вместо того чтобы гадать зачем это нужно, лучше бы помогли...
Например алгоритм Флери строит один эйлеров цикл. Но мне надо перебрать все эйлеровы циклы. Погуглил но как то везде невнятно говорят.
http://forum.vingrad.ru/forum/s/216cb1a ... 29518.html

К тому же в алгоритме Флери не нравится процедура проверки связанности. Слишком долго будет выполняться..

[Nataly-Mak]

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

Вместо того чтобы гадать зачем это нужно, лучше бы помогли...

Э-э-э... А разве можно оказывать техническую помощь? Вроде вы мне говорили, что "это неправильно"

[Pavlovsky]

Например, чтобы построить решение С5N25 достаточно строки длиной 18
1,1,2,1,3,4,2,2,5,2,3,1,5,5,4,5,3,2
Надо немного напильником пройтись.

[Zealint]

Закрыл все числа 10,12,14,18,20. Осталось 15 и 21, но там всё плохо...

[Pavlovsky]

Zealint в сообщении #594465 писал(а):

но там всё плохо...

ИМХО совсем даже не плохо.

Цитата:

1 Artem Karavaev 19.974300 07-11-2012 @ 19:37:19

[Zealint]

Я имел в виду, что не могу даже повторить рекорд alexBlack. В 15 отстаю на 1, а в 21 - на 3. Это при том, что как раз с этими числами мой "алгоритм" должен был работать без всяких проблем. Но он не пашет...

[Nataly-Mak]

Здорово!
Наши держат планку довольно высоко:

Цитата:

10 94 8836 Artem Karavaev @ 19:50:31 on 07-09-2012 1
12 136 18496 Artem Karavaev @ 19:18:29 on 06-30-2012 1
14 186 34596 Artem Karavaev @ 06:56:57 on 07-10-2012 1
15 192 36864 Alex Chernov @ 16:04:06 on 06-23-2012 1
18 310 96100 Artem Karavaev @ 17:37:19 on 07-11-2012 1
20 384 147456 Artem Karavaev @ 08:19:18 on 07-10-2012 1
21 390 152100 Alex Chernov @ 20:56:57 on 07-07-2012 1

Но почивать на лаврах рано
Иностранцы могут отыграть эти рекорды.

[whitefox]

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

Например, чтобы построить решение С5N25 достаточно строки длиной 18
1,1,2,1,3,4,2,2,5,2,3,1,5,5,4,5,3,2
Надо немного напильником пройтись.

У меня уже напильник стёрся, а получить из вашей строки C5N25 не получилось.