| 1 Жалолов Шахзод, 03 января 2023 г. 21:09:20 |
| is this problem solved with simple np
|
|
|
|
|
| 2 МИРЖАХОН КАЙИМОВ МИРТЕМИРОВИЧ, 20 декабря 2022 г. 21:11:21 |
| do not use string
|
|
|
| 3 МИРЖАХОН КАЙИМОВ МИРТЕМИРОВИЧ, 20 декабря 2022 г. 21:10:08 |
| meet in the middle jalka a recursive function and bitset the end :)))))))))))))
|
|
|
| 4 Боровиков Кирилл Андреевич, 20 февраля 2022 г. 10:50:33 |
| Можно сделать простой рекурсией с параметрами void f(int ind, int sum) ind - текущий индекс в массиве значений A, sum - текущая сумма
|
|
|
| 5 Зеленский Данил Олегович, 09 августа 2021 г. 6:27:10 |
| Спасибо люди за meet-in-the-middle.
|
|
|
| 6 Икроми СИНО, 23 марта 2021 г. 13:17:49 |
| Leetcode лучше чем acmp там на языки есть оделённые ограничение. Это Задача на с++ AC а на питон тот же код Limit
|
|
|
| 7 Владислав Войтов, 24 мая 2020 г. 10:02:23 |
| meet-in-the-middle рулит, только я использовал map c++ , он так же за логарифм работает, как двоичное оптимизированное дерево поиска
|
|
|
| 8 Бабаджанов Шероз, 14 апреля 2020 г. 6:31:35 |
| Админ почему 7 WA
|
|
|
| 9 Левин Михаил Константинович, 25 декабря 2019 г. 22:18:24 |
| 7 Неизвестный, 16 декабря 2018 г. 17:58:28 Для n=3 s=3 a1=1 a2=2 a3=2 Что будет? No solution Очень помог данный комментарий. Первый элемент гарантированно с плюсом! Остальные уже можем либо брать либо не брать. Задача показалась мне сразу простой. Запилил сбор знаков по маске mask | (1 << pos) + и mask & (maxMask - (1 << pos)) - И пот над 5 тестом)
|
|
|
| 10 Зинов Вадим, 10 декабря 2019 г. 1:26:00 |
| Кек, не стал париться, закешировал суммы половины элементов по маске) Зашло =D
|
|
|
| 11 Зинов Вадим, 10 декабря 2019 г. 0:46:53 |
| Классная задача! Правда я ее еще не решил, но все равно норм
|
|
|
| 12 Абдыкапаров Нурислам, 26 ноября 2019 г. 10:16:55 |
| 3 3 -1+2+2 или "No Solution"?
|
|
|
| 13 Уткир, 14 октября 2019 г. 10:37:36 |
| 3 3 4 0 1 ? 4+0-1 или 4-1
|
|
|
| 14 Якина Ангелина Ивановна, 13 сентября 2019 г. 19:18:39 |
| Действительно, можно добавить "усложнённую версию задачи" с n<=40, чтобы можно было решать только с помощью meet-in-the-middle.
|
|
|
| 15 Ерёменко Владислав Владиславович, 12 мая 2019 г. 14:55:15 |
| Пробовал использовать массивы и строки - TLE, использовал bitset -задача заработала в 5 раз быстрей и прошла))
|
|
|
| 16 Неизвестный, 16 декабря 2018 г. 17:58:28 |
Для n=3 s=3 a1=1 a2=2 a3=2 Что будет?
No solution
|
|
|
| 17 Гичев Илия Алексеевич, 23 сентября 2018 г. 21:14:40 |
Что выводить при тесте 24 -589200265 39385534 30476916 15911293 38371549 21530652 45043938 12621967 42525363 2134761 14111218 9238325 43955014 16000617 3519470 49174155 14322640 17458132 48699570 47268475 42502438 22440056 6954642 45947784 38376824 всё испробовал пишет WA
39385534-30476916-15911293-38371549-21530652-45043938-12621967-42525363-2134761-14111218-9238325-43955014-16000617-3519470-49174155-14322640-17458132-48699570-47268475-42502438-22440056-6954642-45947784-38376824=-589200265
|
|
|
| 18 Чернацкий Евгений Геннадьевич, 28 июля 2018 г. 14:06:15 |
| Также решается с помощью перебора по маскам и кода Грея. Простой перебор по маскам дает сложность O(2^N*N), а в коде Грея соседние маски отличаются одним битиком и асимптотика улучшается до O(2^N)
|
|
|
| 19 Строганов Никита Сергеевич, 25 июля 2018 г. 21:33:21 |
| Спасибо предыдущему комментатору, освоил meet-in-the-middle)
|
|
|
| 20 Яндулов Богдан, 19 июля 2018 г. 17:45:39 |
Не прошёл полный перебор (хотя там всё на битовых операциях было) и пришлось воспользоваться техникой meet-in-the-middle (почитайте, отличная вещь). Итоговая асимптотика: O(2^(N/2) * N), что в худшем случае даёт ~50 000 операций. Так что можно смело увеличивать N до 40.
Можно перебор за O(2^N). Главное не пересчитывать сумму для каждого варианта, чтобы не стало O(N*2^N).
|
|
|
