Какой по-вашему минимум алгоритмов(структур данных и пр.) стоит знать для успешного участия?
Какой по-вашему минимум алгоритмов(структур данных и пр.) стоит знать для успешного участия?
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 157 |
| 6 | maroonrk | 155 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 146 |
| 8 | orz | 146 |
| 10 | BledDest | 145 |
Для успешного участия можно не знать ни одной. Начинать надо с программирования, а не со структур данных.
Что вы подразумеваете под программированием?
Написание программ.
PS: Искренне ваш, кэп
Мне кажется я вполне ясно сформулировал вопрос. Переформулирую: Что нужно знать для решения наибольшего количества задач?
Нужен в первую очередь опыт. Алгоритмы нужно изучать по мере поступления задач, т.к. знания, не закрепленные на практике, смысла мало имеют. В общем решай задачи, сначала те, что проще, потом переходи к более сложным и постепенно изучай всё новые и новые алгоритмы.
Все-таки, ИМХО, в первую очередь нужно выработать у себя т.н. "алгоритмическое мышление". Это понятие довольно расплывчатое, но можно сказать, что в него входят такие вещи, как умение правильно разбивать задачу на подзадачи, способность извлечь из какого-либо алгоритма его идею и применить ее в совершенно другом месте, ну и т.д..
Ну и стоит набираться опыта (решать задачи) и учить уже конкретные стандартные алгоритмы по мере надобности.
Для участия в чем? Для соревнований по стрельбе с лука можете вообще не учить структуры данных.
Ну а если серьезно, то до крепкого желтого или даже до красного на ТС и СF можно добраться без особых знаний.
Специфика в том, что это не АСМ, длина контеста и его индивидуальный характер не позволяют давать сложные задачи; а если они есть, то их решают не многие.
На топкодере главное динамику решать :)
До верхнежелтого хватает и стабильной Easy, в которой ДП не часто
А как научиться решать динамику с ТопКодера? Может быть, кто-нибудь знает метод кроме прорешивания тысяч задач на динамику? :)
Если бы я знал такой стратегический секрет, я бы не делился ни с кем)
Тебе жалко, если одним человеком, умеющим решать динамику, станет больше? оО
А станет не на одного больше;)
Читай бессмертный топик.
Теоретический минимум для программиста.
Читать по порядку. Как дочитаешь, возвращайся.
А если серьёзно, отсюда к спортивному программированию имеют отношение пункты 1, 6, 7, 8, 10, 11, 12, 13, 14, 15, 20, 31, 30, что тоже немало.
Мне кажется, что нормальный человек столько знать не может. Конечно, можно рассуждать о том, что если время тратить на то, чтобы 8 часов спать, 1 час есть и 1 час отдыхать, а оставшиеся 14 часов тратить в течение 5 лет на учебу, то я верю, что можно все прочитать и понять. Но ведь знания, не закрепленные на практике, не имеют никакого смысла. А чтобы сделать даже простенькую курсовую (не копипасту из википедии, а маленькую исследовательскую работу), нужно потратить минимум неделю. Мне кажется, такой объем информации из различных областей невозможно хранить в голове одновременно.
Существует еще математический минимум — думаю, многие видели эту "программу". Что вы о ней думаете?
Вроде эпический "теоретический минимум для программиста" уже успели высмеять все кто могли — там даже не в том дело может ли человек столько знать, сколько в том что человек едва ли может за 40 лет профессиональной деятельности успеть поработать в стольки областях чтобы ему всё это пригодилось (даже если по году в каждой). Ну и до кучи там отсутствуют многие популярные нынче словечки (поищем Android или Mongo — а Java вынесена в специфику которую можно учить после этого минимума), зато некоторые зело архаичные употребляются многократно (нюансы x86 архитектуры это наше всё!).
С математическим минимумом, как мне кажется, дело ещё хуже т.к. когда мы говорим "для программиста" — мы под этим можем хотя бы представить некоего сферического околокомпьютерного инженера с широким профилем, погружённого в разуплотнённый гелий — но что представляет из себя будущий специалист которого мы собрались учить математике (по этой например программе) вообще не понятно. Встречаются математики в природе ощутимо реже, изучать их сложнее. Особенно абстрактные, которые не математики-программисты или математики-физики и т.п. Оценивать их работу обычно сложно т.к. для этого нужен другой математик а не тестировщик или пользователь. Имхо, обязательную программу нужно рассчитать до конца 2 курса, а дальше специализация, кураторы, научные работы и руководители, вебинары и сообщества математиков по интересам, благо интернет расширяет границы. %)
Ну давайте раззведём холивар на тему пригодится ли спортивное программирование на практике....
Я ожидал увидеть примерно то, что написал ниже mimirrow. Но это прямо уж совсем минимум. Может кто-нибудь дополнит список?
Для успешного выступления в СП нужны не структуры данных, а идеи и умение реализовывать эти идеи. И никто никогда вам не скажет, что в решении какой-то ключевой задачи не будет аналогии с построением +-1 RMQ за O(1) с O(N) предпросчета.
Помните: "кто лучше знает теорию" определяет места красных, но не зеленых. Уже были неоднократные наблюдения, когда фиолетовые обсуждали Укконена, а красные — наибольшую возрастающую за N*log(N) через lower_bound.
Просто решайте задачи. Если не можете решить задачу — ищите подсказки. Если в подсказке незнакомая АТД — прочитайте о ней. Все.
Очень часто попадаются задачи на написание бинарного поиска, НОД и НОК чисел, к примеру. Полезно знать некоторые сортировки, более эффективные — QSort, MergeSort и цифровую(там где элементов много, но все элементы меньше 10^5 или 10^6 по модулю). Знание дфс и бфс(очереди) намного облегчают жизнь. А из структур могу посоветовать дерево отрезков, дерево фенвика, корневую, декартово дерево. В принципе, данных алгоритмов и их умелого использования хватит на довольно успешные выступления.
What a stupid question !?
Пачиму вы миня все так нагло минусите?????
За безграмотность)
Может будет полезно: http://acm.mipt.ru/twiki/bin/view/Algorithms/OlimpiadMinimum
а что такое "Структура Румянцева"?
Тоже интересно. Гугл ничего не находит, это явно какое-то локальное название.
UPD. Неактуально