Competitive Programming Guide

CP Handbook - это единственное место для всех любителей конкурентного программирования, поскольку оно содержит все алгоритмы и структуры данных. Также каждая тема содержит примеры и нерешенные проблемы для практики.

Конкурсное программирование - это спорт, я имею в виду буквально. Возьми любой вид спорта, давай рассмотрим крикет на этот счет, ты впервые идешь к летучей мыши. Качайте и промахнитесь, сделайте это пару раз, и в конечном итоге вы попадете по канату. Теперь рассмотрим конкурс программирования как игру в крикет, в переносном смысле. Скомпилируйте код и отправьте, вы можете получить WA (неправильный ответ).

Внесите изменения в код, и в итоге вы получите свой первый AC (Принятый / Правильный ответ). Позвольте мне кратко взглянуть, около 20% вопросов в конкурсе по программированию - это простое преобразование простого английского языка в код вашего любимого языка программирования.

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

 И поверьте мне, вам не нужно знать какой-либо алгоритм «причудливого имени» или структуру данных, чтобы начать. Вы когда-нибудь слышали о «Waft Shot», но вы лучший игрок с битой на вашей улице, верно?

Хорошо, давайте победим первые 20% проблем программирования.

Ты должен знать:

Средний уровень владения любым языком программирования

Английский! Конвертировать английский в код!

Давайте рассмотрим примерную проблему этого уровня: ужасный чанду

Все, что вам нужно сделать, это прочитать строку ввода из STDIN и распечатать обратную строку в STDOUT. Давай, сделай представление. Ищите свой первый кондиционер. Хочу больше? У нас есть грузы в нашем разделе практики. Ищите те с тысячами правильных представлений.

Хорошо, теперь вы готовы принять настоящий вызов. Держись крепче, мы погружаемся глубже.

Ты должен знать:

1. Алгоритмы сортировки и поиска

2. Хеширование

3. Теория чисел

4. Жадная техника

Что еще более важно, вы должны выяснить, что, когда и где их применять. Это становится действительно сложно, и, следовательно, чтобы помочь новичкам обрести чувство уверенности, мы проводим серию конкурсов под именем Code Monk. Перед каждым конкурсом мы выпускаем учебник по определенной теме, а позже в конкурсе проблемы нацелены только на эту конкретную тему. Я бы порекомендовал вам пройтись по учебникам и решить один или два вопроса по каждой теме.

К настоящему времени вы поняли, что вопросы сформулированы так, чтобы обмануть наше мышление. Иногда, если вы конвертируете простой английский в код, вы в итоге получите вердикт TLE (Time Limit Exceeded). Вам необходимо изучить набор новых методов и алгоритмов, чтобы справиться с ограничениями по времени. В некоторых случаях на помощь приходит динамическое программирование (DP). Infact, вы, возможно, уже интуитивно использовали эту технику. В любом конкурсе всегда есть хотя бы один вопрос, который может быть решен DP.

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

1. Теория графов

2. Разъединить множество Союза (Union-find)

3. Минимальное остовное дерево

Этот набор структур данных поможет вам достаточно далеко. Более того, вы бы подумали, что настоящее искусство заключается в изменении техник, которые вы знаете, для решения вопроса. Все вопросы Easy-Medium и Medium уровня могут быть решены таким образом.

Вы все готовы занять лидирующие позиции в соревнованиях по короткому программированию, просто сохраняйте постоянство. Как я уже упоминал, это спорт, вы не овладеете им, пока не начнете заниматься этим. Примите участие в коротком конкурсе, узнайте свои сильные и слабые стороны и узнайте, как вы справляетесь с режимом адреналина, когда тикают часы.

Придерживайтесь своей собственной логики как можно дольше, в конечном итоге вы найдете нечто похожее на алгоритм, необходимый для решения вопроса. Вам просто нужно почистить это. Некоторые из этих методов помогут вам решить некоторые из самых сложных проблем.

1. Сегментное дерево

2. Строковые алгоритмы

3. Трисы, Суффикс-дерево, Суффикс-массив.

4. Тяжелое Легкое Разложение

5. График раскраски, сетевой поток

6. Sqrt Разложение.

Так что загрузите это руководство по CP и наслаждайтесь изучением новых вещей, также не забывайте кодировать их с меньшей сложностью времени.