Некто на форуме запостил задачку — в строке из нулей и единиц найти максимальную подстроку с равным количеством того и другого.
http://javatalks.ru/topics/37905
Кто-нибудь знает откуда эта задача в оригинале? Я нашёл только несколько обсуждений на буржуйских форумах, ещё вот такую бумажку http://arxiv.org/pdf/0910.3503.pdf ну и до кучи кросс-пост этого же чела на другом форуме.
Есть ли она где-нибудь на online judge каком-нибудь? Хочется мысль проверить... %)
Посмотри задачу H с последнего NEERC
Это совершенно другая задача
Думаю в качестве автора задачи можно смело называть фольклор. Ну она простая, по сути упражнение на мапы (или даже массивы).
Чем искать на онлайн джаджах, быстрее наверное написать стресс тест с тупым решением за квадрат или даже куб.
Спасибо! Да я и хотел тестом за N^2 проверять, но опасался что упущу какой-нибудь контр-пример. А всё потому что под вечер какой-то бред явно выдумывал, который не мог доказать.
А с утра за чаем понял что это действительно простое "упражнение" — и смешно и стыдно как-то... %)
Здесь вопрос в том, сколько способов выбрать подстроку с равным количеством одного и другого.
Спасибо... Сдалось практически сразу... Правда действительно с мэпой на двух тестах ТЛ, и на массив быстренько переделать пришлось.
Забавно что в этой постановке само ограничение уже толсто намекает что не нужно пытаться искать решение сложнее линейного — а в оригинальном варианте я сначала мудрил (тупил) пытаясь NlogN найти. :)
Все-таки, на эту задачу существует O(N * log N) решение, заходящее за 269мс на Java :).
Его еще можно легко улучшить до 192 мс, правда это уже O(N).
Такое решение было для меня очевидно с самого начала. Я просто хотел показать, что ограничения 10^6 при нынешней производительности компьютеров — совсем не повод отказываться от O(N * log N).
Да-да, тут же весь прикол в том что при ясном линейном решении можно оказывается не только выдумать эн-логарифмическое, но ещё и пропихнуть его! Это надо в коллекцию анекдотов от спортивных программистов. :)
нет ли какого-нибудь более-менее разумного решения с логарифмом. всмысле бинпоиск чего-нибудь или еще что...?
Я же уже дал ссылку на более-менее разумное решение с логарифмом...
Я к сожалению не знаю первоисточник, но знаю, что это задача T из текущего контеста Летней школы МФТИ. Если вам надо, могу скинуть условие с этого контеста.
По крайней мере, туда она копировалась из архива олимпиады в Салавате для школьников 5-9 классов.
На ACMP есть похожая задача, и в ее обсуждении I_love_Tanya_Romanova пишет, что она с РОИ.
Да, с РОИ.
Задача близка по тематике, только это на подсчет количества таких подпоследовательностей. http://informatics.mccme.ru/moodle/mod/statements/view3.php?chapterid=1216
upd: не увидел ссылку сверху, такая же задача.
http://www.spoj.com/problems/ZQUERY/
На ту же тему. Прошу прощения за ворошение былого :)