Competitive Programming Guide

VOCODE Labs

Утрымлівае аб’явы

Пра гэту праграму

CP Handbook - гэта адно месца для ўсіх аматараў канкурэнтнага праграмавання, бо ён утрымлівае ўсе алгарытмы і структуры дадзеных. Таксама кожная тэма змяшчае прыклады і нявырашаныя праблемы на практыцы.

Канкурэнтнае праграмаванне - гэта спорт, я маю на ўвазе літаральна. Займайцеся любым відам спорту, давайце разгледзім крыкет, калі вы ўпершыню наведваеце біту. Размахніцеся і прапусціце, зрабіце гэта некалькі разоў, і вы ў рэшце рэшт націснеце адзін на тросы. Зараз разгледзім конкурс праграмавання як метафарычную гульню ў крыкет. Складзіце код і адпраўце, вы можаце атрымаць WA (няправільны адказ).
Унясіце змены ў код і, у рэшце рэшт, вы атрымаеце свой першы пераменны ток (прыняты / правільны адказ). Дазвольце мне падгледзець, каля 20% пытанняў у конкурсе праграмавання - гэта простае пераўтварэнне звычайнай англійскай мовы ў код вашай любімай мовы праграмавання.
Калі ўваходзіць у яго, вы даведаецеся няпісаныя правілы гульні, калі будзеце гуляць усё мацней і лепш.
 І паверце мне, каб пачаць, вам не трэба ведаць алгарытм альбо структуру дадзеных "фантазія". Вы калі-небудзь чулі пра "Вафт-стрэл", але вы лепшы качан на вуліцы, так?

Давайце, пераможам першыя 20% праблем з праграмаваннем.
Вам трэба ведаць:
Прамежкавае ўтрыманне на любой мове праграмавання
Англійская! Пераўтварэнне англійскай мовы ў код!
Возьмем для прыкладу праблему такога ўзроўню: Страшны Чанду

Усё, што вам трэба зрабіць, гэта прачытаць радок уводу з STDIN і раздрукаваць адваротны бок гэтага радка ў STDOUT. Ідзіце наперад, зрабіце ўяўленне. Знайдзіце свой першы пераменны ток. Хачу больш? У нашым раздзеле практыкі ёсць нагрузкі. Шукайце тыя, з тысячамі правільных матэрыялаў.

Добра, зараз вы гатовыя прыняць нейкую сапраўдную задачу. Трымайцеся, мы ныраем глыбей.

Вам трэба ведаць:

1. Сартаванне і пошук алгарытмаў
2. Хешинг
3. Тэорыя лікаў
4. Прагная тэхніка

Што яшчэ больш важна, вы павінны высветліць, што, калі і дзе іх ужыць. Гэта становіцца вельмі складана, і таму, каб дапамагчы пачаткоўцам здабыць пачуццё ўпэўненасці, мы праводзім шэраг конкурсаў як Code Monk. Перад кожным конкурсам мы выпускаем падручнік па пэўнай тэме, а пазней у конкурсе праблемы накіраваны толькі на гэтую канкрэтную тэму. Я б рэкамендаваў вам прайсці падручнікі і вырашыць пытанне-два па кожнай тэме.

Вы ўжо зразумелі, што пытанні пастаўлены так, каб падмануць так, як мы думаем. Часам, калі вы канвертуеце звычайны англійскі ў код, вы атрымаеце версію TLE (перавышаны ліміт часу). Вам трэба асвоіць набор новых метадаў і алгарытмаў, каб справіцца з часовымі абмежаваннямі. У некаторых выпадках на дапамогу прыходзіць дынамічнае праграмаванне (DP). Infact, вы маглі б ужо інтуітыўна выкарыстаць гэтую тэхніку. У любым конкурсе заўсёды ёсць па меншай меры адно пытанне, якое можа вырашыць DP.

Акрамя таго, вы заўважылі, што ёсць пытанні, якія проста не могуць вырашыць структуры дадзеных лінейных масіваў.

1. Тэорыя графаў
2. Нязгодны саюз (знайсці саюз)
3. Мінімальнае разгалістае дрэва

Гэты набор набораў дадзеных атрымае вас дастаткова далёка. Больш за тое, вы б зразумелі, што сапраўднае мастацтва - гэта змяніць тэхніку, якую вы ведаеце, каб вырашыць пытанне. Усе пытанні Easy-сярэдняга і сярэдняга ўзроўню вырашаюцца такім чынам.

У вас усё ў парадку лідэраў кароткіх задач праграмавання, проста захоўвайце ўстойлівасць. Як я ўжо згадваў, гэта спорт, вы не будзеце асвойваць яго, пакуль на самой справе не займаецеся гэтым. Ідзіце наперад, удзельнічайце ў кароткім конкурсе, ведаеце свае моцныя, слабыя бакі і паглядзіце, як вы спраўляецеся з рэжымам адрэналіну, калі пазначае гадзіннік.

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

1. Сегментнае дрэва
2. Радкавыя алгарытмы
3. Спрабуе, суфіксавае дрэва, масіў суфіксаў.
4. Цяжкае лёгкае раскладанне
5. Размалёўка графіка, сеткавы паток
6. Расклад Sqrt.

Так што запампуйце гэты даведнік па CP і атрымлівайце асалоду ад вывучэння новых рэчаў, таксама не забудзьцеся расшыфроўваць іх з меншай складанасцю часу.

Што новага

** Algorithms enhanced