Prime Sums

[Pavlovsky]

Очередной поток сознания.

Задача.
Дан прямоугольник k - количество строк, m - количество колонок. Так же дан набор натуральных чисел $(a_1,...,a_m)$. Необходимо каждую строку прямоугольника заполнить числами от 1 до m. Каждое число используется ровно один раз. То есть каждую строку прямоугольника заполнить перестановкой чисел [1,...,m]. Заполнение должно быть таким, что сумма чисел в колнке i должна равняться $a_i$.

Вопросы.
1) Является ли задача NP-полной?
2) Существует ли полиномиальный алгоритм решения задачи?
3) Существует ли псевдополиномиальный алгоритм решения задачи?
4) Какие необходимые и достаточные условия существования решения для набора $(a_1,...,a_m)$ можно сформулировать?
Следующие необходимые условия очевидны:

$k \le a_i \le km$

$\sum_{i=1}^{m}{a_i}=\frac{m(m+1)}{2}k$

Если упорядочить $(a_1,...,a_m)$ по возрастанию:
$\sum_{i=1}^{j}{a_i} \ge \frac{j(j+1)}{2}k$ для всех j $1 \le j \le m$

5) Можно ли, для заданных k и m, определить интервал $[A_{km},B_{km}]$. Такой что любые m различных чисел, взятых из этого интервала, образуют набор $(a_1,...,a_m)$, для которого существует решение задачи.

[Nataly-Mak]

Возвращаясь к вопросу о взаимно-дополнительных схемах...

Есть некоторая схема для N=6 с результатом 890.
В этой схеме числа распределены так:
с весом 0 - 5 чисел
1 - 8
2 - 9
3 - 10
4 - 4

Рисую взаимно-дополнительную схему, то есть беру теперь не использованные в первой схеме 12 линий. В этой схеме числа распределены так:
с весом 0 - 4 числа
1 - 10
2 - 9
3 - 8
4 - 5
Соответственно распределяю числа по множествам M0,M1,M2,M3,M4.

Вопрос: обязана ли взаимно-дополнительная схема дать максимальное решение 1758

[Pavlovsky]

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

Вопрос: обязана ли взаимно-дополнительная схема дать максимальное решение 1758

Если учесть, что суммы у нас должны быть простыми числами, то не обязана.

[Nataly-Mak]

Что-то не очень убедительно.
А разве в новой схеме при соответствующем разложении чисел на множества M0,M1,M2,M3,M4 никак не получится набрать 12 нужных простых сумм по зачётным линиям?
Мы ведь сделаем перебор.

От меня этот момент ускользает
Вот сижу и думаю: программировать или не программировать эту взаимно-дополнительную схему?
Сделала оценки всех 12 линий, по оценкам они вполне годные. Почему бы и нет

[Pavlovsky]

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

А разве в новой схеме при соответствующем разложении чисел на множества M0,M1,M2,M3,M4 никак не получится набрать 12 нужных простых сумм по зачётным линиям?

Фраза "Не обязана", не исключает ситуацию, что это возможно.

-- Ср ноя 21, 2012 10:24:09 --

Про доплнительную схему можно сказать только одно.
Основная и дополнительная схемы имеют одинаковые теоретические оценки (минимум и максимум).

[svb]

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

Gerbicz в сообщении #647347 писал(а):

It should be forbidden to give out the primes for an optimal (or any) grid.

I agree.

А вам не кажется, что в ваших сообщениях содержится серьезная подсказка? Любое решение при N>7 я получаю за несколько секунд, при этом даже не подозреваю какие простые суммы получаются. То, что вы сообщили, говорит об использовании значений простых сумм в ваших алгоритмах. Или вы пошутили?

[dimkadimon]

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

:?:
А вам не кажется, что в ваших сообщениях содержится серьезная подсказка? Любое решение при N>7 я получаю за несколько секунд, при этом даже не подозреваю какие простые суммы получаются. То, что вы сообщили, говорит об использовании значений простых сумм в ваших алгоритмах. Или вы пошутили?

Совсем нет. В моём сообщении нет никаких намеков на мой метод. На самом деле я не использую значения простых сумм. Я просто считаю что такие вещи не должны тут обсуждаться, потому что они слишком близки к хорошим решениям которые можно ввести. Опять же очень сложно оценить что можно, а что нельзя обсуждать. Окончательное решение должен принимать администратор конкурса (Нейл), но он к сожалению не особо читает этот форум. Если бы я был администратором я бы попробовал написать точные правила о том что можно а что нельзя. Нарушение этих правил я бы наказывал дисквалификацией участника.

[Nataly-Mak]

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

Фраза "Не обязана", не исключает ситуацию, что это возможно.

Верно.
Но я хотела знать следующее: можно ли утверждать, что обязана?
Вы отвечаете, что нельзя это утверждать.

Дальше уже пошли мои разглагольствования

[svb]

dimkadimon

Цитата:

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

С одной стороны, можно обсуждать алгоритмы без конкретной реализации, а с другой стороны, весьма сомнительные претензии к Nataly-Mak, которая ничего, кроме того, что у нее есть решение для 4850, не сообщила. Даже, если бы она привела схему (а их очень и очень много в данном случае), для которой годятся эти простые суммы, то и в этом случае весьма проблематично использовать эту информацию для получения решения. Поэтому мне и показались смешными ваши претензии Но, в целом, дело ваше.

[Nataly-Mak]

Кстати, первым выложил разложение результатов на простые суммы svb, и сделал он это по просьбе dimkadimon

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

Можете привести примеры? Я думаю рекордные разложения должны быть в конце списка, ведь на то они рекордные.

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

dimkadimon

Вот два примера:

2752:
229 223 211 199 197 193 181 179 167 163 151 149 139 131 127 113 рекордный
223 211 199 197 193 191 181 173 167 163 157 151 149 139 131 127 последний

4850:
331 313 311 307 293 283 281 277 271 269 263 257 251 241 239 229 223 211

Для 4850 рекордное разложение совпадает с последним. Можно, конечно, предположить, что и для последнего разложения из списка для 2752 существует рекорд.

Но Gerbicz это почему-то не заметил. Отсюда делаю логичный вывод: ему нравится цепляться именно ко мне. Ну, и занесла его на основании этого вывода в список игнорируемых пользователей. Пусть теперь цепляется, сколько хочет

[whitefox]

Gerbicz в сообщении #647347 писал(а):

Nataly: "Минимальное решение 4850 для N=9 существует и для такого разложения"

It should be forbidden to give out the primes for an optimal (or any) grid.

Полная и абсолютная ерунда.
Любой школьник напишет простенькую программу, находящую разложение числа 4850 на 18 простых.

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

[Nataly-Mak]

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

...которая ничего, кроме того, что у нее есть решение для 4850, не сообщила.

Могу ещё сообщить, что у меня есть решение 4850 и с таким разложением на простые суммы, какое привёл svb (см. цитату выше)

[svb]

Nataly-Mak
Совсем плохо, теперь меня с dimkadimon, наверное, дисквалифицируют

[Nataly-Mak]

svb
вас в этом случае возьму в свою команду

[svb]

Nataly-Mak
Договорились