Как находить лучший способ решение задачи на олимпиадном программировании?

Question

[kvell2]

Решаю задачи на codeforces. Некоторые задачи даются легко. Но на многих задач я не понимаю че вообще делать. Думаю несколько часов, анализирую входные данные и выходные данные, пытаюсь придумать какую ни будь формулу. Но ничего не получается. Но когда смотрю на чужие решения, всё кажется простым. Не подскажете как подходить к олимпиадным задачам и как вообще думать на таких задач

Answer 1

[Wataru]

Нарешаете много задач, научитесь в голове перебирать известные алгоритмы.

А так - на до сначала построить математическую модель задачи. Понять, на что эта модель похожа. Может, тут граф нарисовать можно? Какие алгоритмы на графы вы вообще знаете? Применимы ли они тут? Или это строка. Какие есть алгоритмы на строки? Смотрите еще ограничения. По ним обчно понятно, что тут нужно что-то за O(n), или за O(n log n) написать. Множество применымых алгоритмов еще больше уменьшается.

В задачах на оптимальность чего-то помогает рассуждение "рассмотрим ответ. Какие у него можно заметить свойства. Можно ли какой-то ответ немного поменять, не ухудшая его?" Так вы получите какое-то свойство, которое можно уже применять для построения ответа. Например в задачах на жадность так можно понять, что надо отсрортировать что-то.

Потом, очень частая тема - ДП. Попробуйте параметризировать задачу. Свести ее к подзадачам. Формализуйте ДП (считаем вот такую вот функцию от вот этих вот параметров вот с таким вот физическим смыслом).