Трета тренировъчна сесия

Third Training Session

?	<+kritical> christin: you need to learn how to figure out stuff yourself.. <+Christin1> how do i do that?

Вече познавате най-основните програмистски техники, алгоритми и структури данни, като сте решили поне по няколко задачи за всяка от тях (или поне е трябвало да го направите). На истинско състезание, обаче, няма да ви е казано "тази задача е за намиране на минимално покриващо дърво в граф" или "тук се иска динамично". Вие сами ще трябва да разпознавате нужния алгоритъм или структура данни.

Цел

Да свикнете да решавате цели състезателни теми от по няколко задачи, с различна сложност и тематика. Да отработите основните алгоритми в графи, както и по-лесни динамични задачи.

Задачи

Този път задачите ще са от две места, като и двете са предвидени за ученици. Първото от тях, което ще ви тренира най-вече на бърза имплементация, динамично оптимиране и графи, е TopCoder High School (TCHS). Второто от тях е USACO training-ът. Той си идва с теория за отделните теми, която до голяма степен е покрита от темите преди тази тренировка, но все пак ви съветваме да четете (там е значително по-кратко предствена). И двете места ви дават информация за тестовете, които бъркате, като също така има и анализ на задачите. Голяма част от по-опитните състезатели са правили и двете тренировки, така че те също могат да ви помогнат.

Аудитория

Тази тренировка е подходяща за почти всички състезатели в групите A, B и C. Също така ако имате рейтинг в TopCoder то тя би била подходяща за хора с по-малко от 1800 (около средата на жълтото).

Изисквания

Трябва да се регистрирате в TopCoder и USACO, ако все още не сте. Откъм теория би ви било полезно да погледнете първата половина от Динамично Оптимиране, Част II за част от 1000-рките в TCHS (най-вече итеративно динамично и динамично по битова маска), както и Максимални потоци, като стигнете темата за Network Flows в USACO.

Начин на трениране

TCHS

Отваряте тема и я правите все едно сте на истинско състезание. Полезно е да си засичате колко време ви отнема. Нормалните състезания са 75 минути, но някои от темите ще ви отнемат значително по-малко от това, а някои повече. След като решите и трите задачи правилно (с евентуално известен брой ресъбмити), отворете едиториала и вижте дадените идеи там.

!	Тук е особено полезно да разгледате едиториалите след всеки practice room. Има много готини трикове и идеи, които ще са ви полезни по-нататък.

Отворете и разгледайте набързо две-три решения на high-rated състезатели от practice room-а. Може да помислите дали да не пренапишете отначало 1000-рката с някоя от новите идеи (или от едиториала или от отворените кодове), особено ако сте я направили бавно/грешно. Няма нужда да пренаписвате 250 и 500.

Евентуално ще има 1000-рки, които не можете да измислите. Ако не успеете да я измислите и напишете за два-три часа, вижте едиториала и няколко чужди решения. След това задължително я направете сами. Задачите, които не можете да решите, са именно задачите, които трябва да тренирате!

USACO

Тъй като самото USACO е тренировъчна система, начинът за тренировка е ясно очертан. Има няколко задачи, които са значително по-сложни от останалите и могат да ви забавят доста. Тези, за които се сещам, са: Checker Challenge, Shaping Regions, Fence Rails, Canada Tour, TwoFive, A Rectangular Barn. Като стигнете до някоя от тях се опитайте да я решите, но ако не я минете след няколко дни опити, поискайте помощ от някого или погледнете в интернет за хинтове.

Продължителност

Тази тренировка е по-дълга от предходната. TCHS темите са около 90, като от вас се очаква да правите между 5 и 10 цели практиса на седмица (в зависимост от това колко време ви отнемат и колко време на седмица отделяте, разбира се). Като цяло (особено ако сте направили първата тренировка) първа и втора задача ще ви отнемат около 10-15 минути, като основно ще губите време в правенето на трета. Някои цели практис руумове ще ви отнемат под половин час, докато други може по няколко часа. Към края на тренировката ще се справяте значително по-бързо, отколкото в началото (понякога ще можете да правите 4-5 теми в рамките на няколко часа). Очаква се да можете да решите всички теми за около 2-3 месеца.

USACO е значително по-времеотнемащо (или поне на мен ми беше), главно заради по-evil задачите. То ще ви отнеме поне няколко месеца, затова е по-добре да го правите паралелно с разглеждането на следващите теми.

Резултат

След тази тренировка ще сте достатъчно подготвени да влезете в разширения национален отбор (първите 12 в А група), както и да постигнете жълт рейтинг в TopCoder.