2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 54, 55, 56, 57, 58, 59, 60 ... 130  След.
 
 Re: Новый конкурс программистов
Сообщение10.07.2012, 19:44 
Заблокирован
Аватара пользователя


22/03/08

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

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

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

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

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

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

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

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

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


21/02/10
1594
Екатеринбург
Возникла такая задача.

Преамбула. Простой вариант задачи.
Дано: Алфавит из 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

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


26/01/10
959
Pavlovsky в сообщении #594326 писал(а):
Преамбула. Простой вариант задачи.
Дано: Алфавит из N символов.
Необходимо. Составить, из символов алфавита, строку максимальной длины, чтобы любая соседняя пара символов была различна.

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

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

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

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


21/02/10
1594
Екатеринбург
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. То есть это решение удовлетворяет условиям сложной задачи.

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


22/03/08

7154
Саратов
Pavlovsky в сообщении #594326 писал(а):
Возникла такая задача.

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

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

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

Код:
2,1,2,1,3,4,4,1,4,3,2,2,4,2,1

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

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


21/02/10
1594
Екатеринбург
Nataly-Mak в сообщении #594373 писал(а):
А что даёт эта задача применительно к конкурсной задаче?

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

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


19/12/10
1546
Pavlovsky в сообщении #594377 писал(а):
Этого я пока не буду рассказывать. Так смутные идеи по поводу. Относитесь к этой задаче пока как к независимой задаче. Понравилась простота формулировки.

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

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


21/02/10
1594
Екатеринбург
whitefox в сообщении #594430 писал(а):
нужно построить строку по Вашим правилам при N=10 длиной не менее 98.Это так?

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

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

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

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

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


22/03/08

7154
Саратов
Pavlovsky в сообщении #594440 писал(а):
Вместо того чтобы гадать зачем это нужно, лучше бы помогли...

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

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


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

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


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

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


21/02/10
1594
Екатеринбург
Zealint в сообщении #594465 писал(а):
но там всё плохо...

ИМХО совсем даже не плохо.
Цитата:
1 Artem Karavaev 19.974300 07-11-2012 @ 19:37:19

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


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

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


22/03/08

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

Цитата:
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

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

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


19/12/10
1546
Pavlovsky в сообщении #594456 писал(а):
Например, чтобы построить решение С5N25 достаточно строки длиной 18
1,1,2,1,3,4,2,2,5,2,3,1,5,5,4,5,3,2
Надо немного напильником пройтись.
У меня уже напильник стёрся, а получить из вашей строки C5N25 не получилось. :-(

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 1937 ]  На страницу Пред.  1 ... 54, 55, 56, 57, 58, 59, 60 ... 130  След.

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



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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