Разворот битов
Смею заявить, что на еолимпе этот контест ещё большая жесть, чем у автора (а в Харькове он был самым гробовым). Связано это, я так понимаю, с тем, что в Харькове машины посильнее. По крайней мере, на харьковском сервере мои решения проходят. А здесь ТЛЕ. Надо бы протестить авторские решения - если они ТЛЕ, то наверно стоит поднять тайм лимит чуть-чуть.
Наглядна демонстрація (Це авторський розвязок):
Решение #256095 = АС
Максимальное время выполнения: 1.359 секунды из 2 секунды
Відповідно значить все Ок. Допускаю, що обмеження (у порівнянні з авторським) для інших були у Харкові більш поблажливі, але ж там було змагання, а тут вже тренувальний контест і потрібно не просто здати, а знайти ефективний алгоритм, на підставі знань, отриманих у Харкові. Так що ретесту, відповідно, не буде. Удачі!!!
Тогда будем оптимизировать.
1.359 секунды из 2 секунды в авторском решении, вряд ли очень хороший выбор Лимита времени. Логично, что нужно побольше запаса от того времени, сколько работает авторское. Ведь автор, как никто другой знает, как решать эту задачу эффективно. Часами пытаться делать неасимптотические оптимизации, это часто выводит из себя. Придумываешь асимптотически правильный алгоритм, реализовываешь, а потом еще приходится код до неузнаваемости изменить, чтобы он начал в 1.2 раза быстрее работать. Я, конечно, не говорю, что константа не важна, я считаю, что нужно хорошо знать, как именно писать, чтобы работало эффективно, но если это портит код, то это не очень хорошо.
Код за O(s*k), который мы всей командой пропихивали в Харькове, получил здесь ТЛЕ. Тогда я сделал ещё один неслабый пропих с типами и получил АС за 1.984. Желаю всем удачи в этом нелёгком деле :)
Решение, которое получает АС по задачам на FFT, использует нерекурсивное FFT?
Рекомендуется всегда смотреть в первую очердь на ограничения в задаче. Ведь не серет, что чем больше глубина погружения рекурсивного решения, тем медленее оно работает. Кроме того, следует всегда помнить теорему о том, что рекурсивное решение всегда можно переписать нерекурсивно. Рекурсивное решение иногде легче в понимании, а вот в быстродействии нерекурсивное решение в большинстве случаев оказыватеся быстрее.
Для FFT глубина погружения не больше 20. С этим показателем как раз всё в порядке. Мне просто интересно: можно ли дожать рекурсивное решение (если да, то это будет хороший опыт в оптимизации), или нужно писать нерекурсивное (тоже хороший опыт, но в другом направлении).
Прошу прощения за оффтоп, т.к. FFT отностися не к этой задаче, но раз уж зашла речь...