2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 62, 63, 64, 65, 66, 67  След.
 
 Re: Prime Sums
Сообщение16.01.2013, 16:53 
Аватара пользователя


20/01/10
766
Нижний Новгород
Pavlovsky
Богатая идея, рассматривать подсхемы!

 Профиль  
                  
 
 Re: Prime Sums
Сообщение16.01.2013, 20:06 
Аватара пользователя


20/01/10
766
Нижний Новгород
Об одном наблюдении.

Базовое распределение:
$\begin{array}{l}
 {\rm M_4:1}{\rm ,2},...,{\rm a[4]}{\rm ,} \\ 
 {\rm M_3:a[4] + 1},...,{\rm a[4] + a[3]}{\rm ,} \\ 
 {\rm M_2:a[4] + a[3] + 1},...,{\rm a[4] + a[3] + a[2]}{\rm ,} \\ 
 {\rm M_1:a[4] + a[3] + a[2] + 1},...,{\rm a[4] + a[3] + a[2] + a[1]}{\rm ,} \\ 
 {\rm M_0:a[4] + a[3] + a[2] + a[1] + 1},...,{\rm n}^{\rm 2}  \\ 
 \end{array}$
$a[i]$-количество клеток, через которые проходят $i$ линий.
Базовому распределению соответствует оценка схемы min.
Ищется распределение, которое должно иметь оценку min+top.
При росте top количество таких распределений быстро растет.
Я попробовал рассматривать только часть подобных распределений, а именно, только такие, которым соответствует не более одного обмена между соседними уровнями u и (u-1).

Запуск перебора: set_top(top,1)
Код:
procedure set_top(x,y:integer);
var k,u,v,i,j,b:integer;
begin
  if x=0 then begin cop(m0,m);run;exit;end;
  if y>4 then exit;
  if opt then begin u:=y-1;v:=y end else begin u:=y;v:=y-1 end;
  set_top(x,y+1);
  for k:=1 to x do
  for i:=0 to a[u]-1 do for j:=0 to a[v]-1 do
    if (m0[v,j]-m0[u,i])=k then begin
      b:=m0[v,j];m0[v,j]:=m0[u,i];m0[u,i]:=b;
      set_top(x-k,y+1);
      b:=m0[v,j];m0[v,j]:=m0[u,i];m0[u,i]:=b;
    end;
end;

здесь:
m,m0 - рабочее и базовое распределения,
m[u-уровень,i-индекс от 0 до a[u]-1].
cop(m0,m) - копирование распределения m0 в распределение m, которое затем обрабатывается процедурой поиска решения run.

При поиске максимального решения используется та же процедура, только меняется базовое распределение $m0[i,j]=n^2+1-m0[i,j]$ и задается значение opt=true. Как видно из текста, рекурсия начинается с уровня 1 до 4. Я пробовал и обратное направление с уровня 4 до 1, но результат был печальным. При малых top можно просмотреть все распределения и, поэтому, разницы нет. При больших top число распределений может превышать несколько тысяч. Так вот, при рекурсии от 1 до 4, как показал эксперимент, хорошие распределения выдаются в начале перебора.

Дело за малым :-) - нужна хорошая процедура поиска решений run.

 Профиль  
                  
 
 Re: Prime Sums
Сообщение17.01.2013, 11:26 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Хорошая сейчас появилась практика: сообщать потенциальным конкурсантам о начале нового конкурса :-)
Вот такое письмо сегодня получила:

Цитата:
Dear Natalia Makarova,
I'm launching a new programming contest at Al Zimmermann's Programming Contests on January 19th.
The contest details will be available beginning on that date at http://azspcs.net.

Очень приятно, что организаторы конкурса не забыли своих прежних конкурсантов.

Эх, может быть, и поучаствую в новом конкурсе :wink: если... там не будет Gerbicz.
А он, скорее всего, там будет :-)

 Профиль  
                  
 
 Re: Prime Sums
Сообщение17.01.2013, 13:22 
Аватара пользователя


25/08/12
171
Germany
Nataly-Mak в сообщении #672679 писал(а):
Очень приятно, что организаторы конкурса не забыли своих прежних конкурсантов. Эх, может быть, и поучаствую в новом конкурсе если... там не будет Gerbicz.А он, скорее всего, там будет

I suggest not to make a new thread in this forum for Al's contest, but to use the official discussion group
http://tech.groups.yahoo.com/group/AlZi ... gContests/
There is no need to talk English in Al's discussion group, you also can talk Russian there.
In this way everything is more transparent and the chance, that some paranoid contestants make accusations of cheating is much smaller.

 Профиль  
                  
 
 Re: Prime Sums
Сообщение17.01.2013, 14:21 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Herbert Kociemba в сообщении #672708 писал(а):
I suggest not to make a new thread in this forum for Al's contest, but to use the official discussion group
http://tech.groups.yahoo.com/group/AlZi ... gContests/

В прошлых конкурсах от AZ мы обсуждали задачу на этом форуме, а также ещё на одном. И никто не был против этого.
Разве Правила конкурса запрещают обсуждение задачи на других форумах?

Цитата:
There is no need to talk English in Al's discussion group, you also can talk Russian there.

Я посетила указанную страницу. Мне там ничего не понятно, так как я не читаю по-английски. Где написано, что там можно писать по-русски?

Цитата:
In this way everything is more transparent and the chance, that some paranoid contestants make accusations of cheating is much smaller.

Предпочитаю быть подальше от людей такого типа, чтобы не вызывать на свою голову их бредовые обвинения.

 Профиль  
                  
 
 Re: Prime Sums
Сообщение17.01.2013, 14:28 
Аватара пользователя


21/02/10
1594
Екатеринбург
Зарегистрировался в дисскуссионной группе AlZimmermannsProgrammingContests. Пока там тишина. Попытался создать новую тему. Вышло сообщение: Модератор должен принять вас в группу. Жду...

 Профиль  
                  
 
 Re: Prime Sums
Сообщение17.01.2013, 14:41 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Pavlovsky
вам проще, вы знаете английский и можете свободно читать.

Для меня проще завести тему здесь. Если все против и поддерживают предложение Herbert Kociemba, быть по сему.
Буду решать задачу сама для себя, нигде не участвуя и ничего не обсуждая.

 Профиль  
                  
 
 Re: Prime Sums
Сообщение17.01.2013, 14:51 
Аватара пользователя


21/02/10
1594
Екатеринбург
Nataly-Mak Так можно обсуждать задачу как на этом форуме и так в дисскуссионной группе AlZimmermannsProgrammingContests.

А по русски там вроде как действительно можно вести обсуждение. По крайней мере при создании темы, необходимо задать язык темы.

-- Чт янв 17, 2013 16:53:46 --

Конечно на этом форуме все намного удобнее. Возможность писать формулы, вставлять картинки и etc.

 Профиль  
                  
 
 Re: Prime Sums
Сообщение17.01.2013, 15:04 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Pavlovsky в сообщении #672763 писал(а):
Так можно обсуждать задачу как на этом форуме и так в дисскуссионной группе AlZimmermannsProgrammingContests.

А зачем нужно параллельное обсуждение? Разве нам не достаточно обсуждения на нашем форуме? Мне, например, вполне хватает.

Цитата:
А по русски там вроде как действительно можно вести обсуждение. По крайней мере при создании темы, необходимо задать язык темы.

Ну, если вы создадите там тему на русском языке, то можно и там пообсуждать. Только не вижу особого смысла создавать тему там. Разве затем, чтобы быть под присмотром и чего не нарушить :D

 Профиль  
                  
 
 Re: Prime Sums
Сообщение17.01.2013, 15:06 
Аватара пользователя


21/02/10
1594
Екатеринбург
Nataly-Mak в сообщении #672767 писал(а):
Разве затем, чтобы быть под присмотром и чего не нарушить


Может тамошние модераторы будут строже и объективнее к нарушителям, чем местные. :D

 Профиль  
                  
 
 Re: Prime Sums
Сообщение17.01.2013, 18:00 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов

(Оффтоп)

Поговорка есть такая: "Бей своих, чтобы чужие боялись" :D
Вот в полном соответствии с этой поговоркой вас и ...

 Профиль  
                  
 
 Re: Prime Sums
Сообщение17.01.2013, 18:13 


02/11/12
141
Do not change. Participate as you normally do. His results on AZPC contests are poor. These contests are not about him. I have no reason to write an app if you are not there Natalya!.

 Профиль  
                  
 
 Re: Prime Sums
Сообщение17.01.2013, 18:24 
Аватара пользователя


20/01/10
766
Нижний Новгород
Pavlovsky в сообщении #672751 писал(а):
Зарегистрировался в дисскуссионной группе AlZimmermannsProgrammingContests.
Я уже давно в этой группе зарегистрирован, даже сообщения по почте от них получаю, хотя в конкурсах лично не участвовал. Форум очень неудобный, лучше использовать dxdy или EH. Форум dxdy является международным и более специализирован для обсуждения задач в отличии от форумов Yahoo. Причин менять площадку нет, организаторы Al Zimmermann's Programming Contests отлично знают о существовании dxdy.

 Профиль  
                  
 
 Re: Prime Sums
Сообщение17.01.2013, 19:10 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
mertz
спасибо :-) я постараюсь принять участие в конкурсе.

svb
я очень рада, что вы за обсуждение на нашем форуме.

Может, нам на ЕН уйти, чтобы Gerbicz нас не нашёл? (шутка) :D

 Профиль  
                  
 
 Re: Prime Sums
Сообщение17.01.2013, 19:56 
Аватара пользователя


25/08/12
171
Germany
I personally have no problem if there is a second thread about "factorials" in this forum. It was just a suggestion to use only the yahoo forum.

Btw. Al Zimmermann wrote in the Yahoo forum:

>On Thursday 11/10/2012 at 9:40 pm, Al Zimmermann wrote:
>
>The name changed, but the problem did not. The problem does indeed combine
>straight lines with factorials. But I've decided to emphasize the factorial
>aspect over the straight-line aspect.
>
>Al

Have look at

http://oeis.org/A217032

It is an interesting programming problem, indeed the only interesting programming problem I found about factorials.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 1005 ]  На страницу Пред.  1 ... 62, 63, 64, 65, 66, 67  След.

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



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

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


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

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