Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Курсы ККДП
Дистрибутивы
Статьи
Ссылки


 
[Вернуться к задаче]   1 2
  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).
 1 2

Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!

Красноярский краевой Дворец пионеров, (c)2006 - 2023, E-mail: admin@acmp.ru