Prime Sums

[Nataly-Mak]

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

Думать за человека он не может!

Он может получать хорошие результаты по программе, написанной человеком. Тут думать не нужно!

И при равных качествах программы результаты будут выше на более мощном компьютере. С этим трудно поспорить!

[tolstopuz]

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

Ну почему же? Я не говорю о всех людях сразу, а говорю только о двух конкурсантах.
И это представить вполне реально. Я могу назвать вам кандидатов с умом не хуже того венгра. Например, тот же А. Чернов, который победил в прошлом конкурсе.
Вот вам и два конкурсанта с одинаковым умом, то есть в такой степени одинаковым, что они способны сделать отличную программу. И что же мы видим: венгр на первом месте, а А. Чернов только на 5-ом. В чём же причина? И почему вы это не можете представить?

Не бывает одинаковых умов. Одни сильны в одних задачах, другие - в других. В некоторых задачах Project Euler я "этого венгра" обгонял, во многих других - наоборот.

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

tolstopuz в сообщении #631849 писал(а):

Решил слегка почесать свой кластер

Кластеры они не в туалетах. Кластеры они в головах. (С) профессор Преображенский.

Я потому так и написал, что никакого кластера у меня нет :)

[Nataly-Mak]

Вот блин!
Ну, программу одну и ту же давайте возьмём. Это можете представить? Ну, к примеру, программу А. Чернова.
И загрузим её
а) на моём компьютере;
б) на кластере венгра.

Где результаты будут выше?

(Оффтоп)

Да что тут представлять-то? Когда я это в реале уже проходила. Был один конкурс, давно. Я тогда выложила в теме свой довольно эффективный алгоритм решения задачи. А. Чернову этот алгоритм понравился, он его реализовал. У меня тоже были две реализации: своя и С. Беляева, он тогда участвовал в моей команде. Обе эти реализации были довольно слабые. И А.Чернов прислал мне свою программу. Конечно, я сразу же начала её крутить. И что же? Программа была написана под два ядра, у меня тогда ещё компьютер был одноядерный. Это раз. Сразу одна ветвь алгоритма перестала работать (перебор вглубь). А у Чернова работали обе ветви. Далее: быстродействие. То, что у него выполнялось за секунды, у меня выполнялось за минуты. Ну, и что тут рассуждать?! И ёжику всё понятно.

Нет, вы доказываете, что всё зависит только от ума. А я утверждаю, что в задачах с преобладанием переборной составляющей бОльшая часть зависит не от ума, а от техники.
И всё, давайте на этом поставим точку. Что-то мы слегка зациклились.

[tolstopuz]

(Оффтоп)

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

Вот блин!
Ну, программу одну и ту же давайте возьмём. Это можете представить?

Не могу. Есть другие задачи типа взлома RSA, где программа одна и та же, и влияет только быстродействие компьютера. В конкурсе же соревнуются программно-аппаратные комплексы, где вносят вклад обе составляющие. И программа у каждого участника своя.

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

Программа была написана под два ядра, у меня тогда ещё компьютер был одноядерный. Это раз. Сразу одна ветвь алгоритма перестала работать (перебор вглубь). А у Чернова работали обе ветви.

Обычная ошибка в программе. Грамотно написанные многопоточные программы работают и на одном ядре, просто в два раза медленнее.

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

Далее: быстродействие. То, что у него выполнялось за секунды, у меня выполнялось за минуты.

То есть если у вас программа выполнялась бы 100 лет, то у него завершилась бы за три года. Не сильно утешает.

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

А я утверждаю, что в задачах с преобладанием переборной составляющей бОльшая часть зависит не от ума, а от техники.

Мой опыт решения сотен задач Project Euler на заведомо неэффективном языке (с форой в 100 раз) показывает обратное.

[Pavlovsky]

Пока суть да дело. Слабал програмку проверки возможности построения квадрата по заданной схеме и набору простых чисел.
Как и ожидалось, для N=5 построить квадрат с суммой 500 невозможно. С суммой 502, программа говорит, что построить можно легко.

То есть для n=5 502 это теоретический минмум.

[Nataly-Mak]

Кто-то тут переживал, что венгр потерял один минимум и один максимум
Он подкорректировал идею для N=6,7 и... теперь всё ОК:

Цитата:

1 Robert Gerbicz 50.000000 10-17-2012 @ 20:04:46

-- Чт окт 18, 2012 02:19:40 --

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

То есть для n=5 502 это теоретический минмум.

Я в этом нисколько не сомневалась
Этот минимум уже и найден конкурсантами.
Думаю, что не подлежит никакому сомнению и максимум для N=5 равный 790.

И тут не надо делать тупой перебор из 25! вариантов, разумеется. Всё гораздо проще, идеи лежат на поверхности, и для N=5 они легко реализуемы.

[Nataly-Mak]

Тэкс, тем временем моя простенькая программка выдаёт-таки улучшения для N=6
За два решения надо иметь 4 балла, у меня 3,13. Плоховато, но для начала сойдёт.
Замечу, что это уже работает не случайная генерация квадратов. Случайная генерация у меня дала очень низкие результаты и я быстро от неё отказалась.

Это просто разминка, нет пока никаких капитальных программ.

[Nataly-Mak]

Красивое соседство

Цитата:

31 Pavel Burdanov 6.531420 10-18-2012 @ 09:42:03
32 Konstantin Porozov 5.589110 10-14-2012 @ 04:07:57
33 Natalya Makarova 4.314330 10-18-2012 @ 14:28:46

Написала программку для квадратов 7х7 так, на живую нитку. Программа не шустро работает, однако квадраты выдаёт, правда, полуфабрикаты, то есть в них не 14 нужных линий, а меньше. Вот с 14 никак не хочет выдавать
Ну и ладно, а голова у меня на что?
Беру найденный программой квадрат с 12 нужными линиями:

24  31  2  23  16  9  46 
 15  1  48  49  3  4  5 
 33  7  10  12  13  14  18 
 35  19  20  22  25  26  28 
 41  29  30  36  37  38  39 
 34  42  43  44  6  8  11 
 45  17  40  47  21  27  32

Ещё две линии добавляю вручную. Вот это было интересно
Немного подумать никогда не мешает.
И результат для квадрата 7х7 получен гораздо быстрее компьютера.
А программка пыхтит, пусть пыхтит, может, ещё чего-нибудь найдёт интересненькое.

А результат такой кругленький получился - 2500, что почти среднее арифметическое текущих максимума и минимума на конкурсе.

[Pavlovsky]

Промежуточная задачка. В квадрате уже заполнены некоторые ячейки.
Есть 2N линий. Для каждой линии задана сумма. Есть набор оставшихся чисел.
Необходимо заполнить свободные ячейки числами из набора.

Попробовал решить задачу без перебора, жадным алгоритмом. Увы так просто не получилось.

[Pavlovsky]

6 890 Robert Gerbicz @ 21:04:23 on 10-18-2012
Блин надо срочно дописывать алгоритм. А то, без меня, все рекорды найдут. По моим подсчетам можно попытаться поискать решение 888. Но успех этого поиска маловероятен.

[Nataly-Mak]

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

Промежуточная задачка...

Моя задачка проще (см. предыдущий пост), решается в уме
Есть уже заполненный квадрат с $K$ нужными линиями. Если отметить все эти линии, хорошо видно числа, не лежащие ни на одной из этих линий. Это "свободные электроны"
Надо переставить эти числа и получить недостающие ($2N-K$) линий.

Пример привела - кадрат 7х7, в котором уже есть 12 правильных линий. Две линии добавляются шутя

Хорошо, когда "свободных электронов" много. Если в уме трудно их на место поставить, можно и программку сделать, машина мигом поставит, если это возможно.

Чего там у венгра ещё нет? Рекорда для N=7?

[Nataly-Mak]

Иллюстрация к примеру



Шесть "свободных электронов". Переставляются легко.

-- Чт окт 18, 2012 22:54:53 --

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

... многие его рекорды побиваемые.

dimkadimon
а ваш рекорд для N=7 побиваем?

[dimkadimon]

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

dimkadimon
а ваш рекорд для N=7 побиваем?

Вполне возможно.

[Pavlovsky]

Теоретическая оценка для четных N

N 6 min 888 max 1776
N 8 min 2752 max 5568
N 10 min 6664 max 13536
N 12 min 13752 max 28008
N 14 min 25408 max 51816
N 16 min 43264 max 88320
N 18 min 69216 max 141384
N 20 min 105400 max 215400
N 22 min 154216 max 315264
N 24 min 218304 max 446400
N 26 min 300568 max 614736
N 28 min 404152 max 826728

Сравните с результатами Robert Gerbicz. Конкурс можно завершать?!

[Pavlovsky]

Правда есть еще нечетные числа. Там все не понятно. Например, нашел схему размещения зачетных линий для N=5 с оценкой 484!