| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3839 |
| 3 | Radewoosh | 3646 |
| 4 | jqdai0815 | 3620 |
| 4 | Benq | 3620 |
| 6 | orzdevinwang | 3612 |
| 7 | Geothermal | 3569 |
| 8 | ecnerwala | 3494 |
| 9 | Um_nik | 3396 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Um_nik | 164 |
| 2 | -is-this-fft- | 162 |
| 3 | maomao90 | 161 |
| 4 | atcoder_official | 158 |
| 4 | cry | 158 |
| 4 | awoo | 158 |
| 7 | nor | 155 |
| 7 | adamant | 155 |
| 9 | TheScrasse | 153 |
| 10 | maroonrk | 152 |
Здравствуй, сообщество Codeforces, и с наступающим Новым Годом!
Прошу у вас помощи по одной интересной задачке. У нас есть массив чисел и запросы вида "l r k". Запрос "l r k" означает "найти k-тую минимальную сумму подпоследовательностей на отрезке от l до r. Возможно ли решить эту задачу за полиномиальное время, и, если возможно, то как?
Заранее спасибо!
И вас с наступающим.
Что такое "k-я минимальная сумма"?
Откуда задача?
Я не уверен встречалась ли где-либо такая задача, её идея возникла в процессе придумывания задач для одного локального контеста. Идею мы придумали, а вот решить не смогли)
Если имеются в виду суммы на подотрезках, то, очевидно, можно. Просто за квадрат выписать все суммы а потом nth_element. Однако если имеются в виду суммы подпоследовательностей, то, наверное, нет. Их экспоненциальное количество, я сомневаюсь, что можно найти К-ую в этом случае.
Здравствуйте !!! Где ошибка на мой код!! можете говоритъ ??? Задача(http://informatics.mccme.ru/moodle/mod/statements/view3.php?id=256&chapterid=166#1) мой код (http://mirror.codeforces.com/contest/376/submission/5546624)
Продаю гараж! Обращаться в ЛС.
Ну вам же дан тест и вердикт.
Если ошибка на первом тесте (из примера), а у вас входные и выходные данные совпадают с теми, что в условии, то проблема не в решении. А, например, в вводе-выводе. Обычно это проблемы с именами файлов (или тому, что надо или не надо читать из файла). У вас именно такая проблема.
Кажется, стоило ему на английском отвечать. Тут явно GT :)
Интересно было бы узнать, как находить k-ю сумму хотя-бы на всем массиве, не говоря уже о подотрезках.
имея возможность находить k-ю сумму за полиномиальное время, мы могли бы бинпоиском по k отвечать на вопросы вида "существует ли в множестве подмножество с заданной суммой" также за полиномиальное время. Но это известная NP-полная задача.
Но это не значит, что такую задачу давать нельзя. Для всего массива k-ую сумму можно найти за O(N * SUM), где SUM — сумма всех элементов. Сначала предподсчитываем сколько существует подмножеств сумма элементов в которых равна ровно х, где
. Потом находим значение k-ой суммы и восстанавливаем ответ.
В ограничениях 1 ≤ N ≤ 50, 0 ≤ Ai ≤ 100 вполне можно давать.
Подпоследовательности, а не подстроки. Надо мне читать внимательнее.
В первой правке я серьезно погорячился.
Да вы, сударь, вообще офигели? Грамотным русским языком человек спрашивает как решить весьма чётко поставленную задачу (найти k-ую по величине среди сумм подпоследовательностей на отрезке от l до r в массиве), а вы ещё выделываться изволите?А я ещё думал, не слишком ли я резкий комментарий написал в вашем предыдущем посте...UPD: Говорят, текст поста исходно был другим, тогда прошу прощения за наезд. Надо бы добавить функционал истории правок постов, а то действительно могут случаться недоразумения.
Тут должна быть картинка — Узбагойся), но у меня не получилось
Лучше бы не говорил, что там должно быть :\
В том то и дело, что автор поста изначально написал непонятно, что имелось в виду под k-ой минимальной суммой, и после того как ему указали на баг, он быстренько дописал без палева.
Тогда другое дело. Закапываю топор =) Как-то это неправильно, что править посты можно, а смотреть историю для них — нельзя.
Может быть, меня вообще стоит за мои ошибки казнить, чтобы впредь такого не было? В чем смысл нападать на человека, без Вашего участия признавшего свою неправоту?
Ну после нашей предыдущей дискуссии подобное замечание из ваших уст было для меня как красная тряпка для быка, простите за каламбур. Казнить нельзя, помиловать =)
То чувство когда коммент набрало больше лайков чем пост)
Хм... Довольно таки похоже на недавнюю задачу (https://mirror.codeforces.com/contest/1196/problem/F).
Прошу поделиться мыслями насчет решения, интересно).