ИС
А вот это уже как раз не проще subset sum.
Size: a a a
2020 November 08
K
собственно можно просто сделать количество транзакций равным числу всех участников-1. Все должники сливают одному, он раскидывает по кредиторам. Победа.
Можно просто брать пару должник-кредитор и выкидывать того, у кого меньше
MK
Можно просто брать пару должник-кредитор и выкидывать того, у кого меньше
А может сделать как на бирже?
MK
Упорядочить всех в стакан
MK
И начать с середины вычёркивать
K
Нет разницы, всё равно в худшем случае n-1
@N
Упорядочить всех в стакан
Ну это будет ровно вариант с "все кидают одному + чекаем, множества размера 2"
MK
ЭЭ нет
MK
Будет n-1 транзакция
A
могут быть множества размера 3, 4 и так далее
@N
Будет n-1 транзакция
Так это уже достигли выше
A
у меня вот такой вопрос - верно ли, что если мы сможем хотя бы как-нибудь разделить на два множества, в каждом из которых нулевая сумма, то тем самым мы точно не пропустим какое-то более эффективное решение, в котором есть группа, часть которого из одного, а часть из другого
A
и.. наверно нет. Пример: -1, -1, -2, 1, 1, 2. Мы можем разбить на (-1, -1, 2) и (1, 1, -2) и тем самым лишимся более оптимального разбиения на (1,-1), (1,-1), (2,-2)
@N
у меня вот такой вопрос - верно ли, что если мы сможем хотя бы как-нибудь разделить на два множества, в каждом из которых нулевая сумма, то тем самым мы точно не пропустим какое-то более эффективное решение, в котором есть группа, часть которого из одного, а часть из другого
Еще интересен этот вопрос не для произвольного множества, а для минимального
@N
То есть ввести понятие "простоты" групп, и работает ли здесь аналог основной теоремы арифметики
@N
То есть ввести понятие "простоты" групп, и работает ли здесь аналог основной теоремы арифметики
Не работает, контрпример
2 3 :: 1 4
1 4 :: 2 3
vs
1 :: 1
2 :: 2
3 :: 3
4 :: 4
Разложение с простыми группами не сработает.
2 3 :: 1 4
1 4 :: 2 3
vs
1 :: 1
2 :: 2
3 :: 3
4 :: 4
Разложение с простыми группами не сработает.
RR
А где-то есть полное условие задачи?
@N
А где-то есть полное условие задачи?
RR
А ограничения? Условие про то что суммы точно равны намекает, что вряд ли задача промышленная
MS
Йо! Я хочу отсортировать элементы одного массива согласно элементам другого массива. Как мне это сделать в О(1) памяти (инплейс)?