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

Fourth Training Session

В тренировките до сега имаше лесен начин да намерите грешката си, ако решението ви е грешно. Както USACO, така и TopCoder тренировките дават точния тест, на който програмата ви бърка. Това обаче съвсем не е така на истински състезания. Много полезно е да тествате решението си добре, преди да го предадете (или преди да предадете финалната версия в IOI-style състезания). Тази тренировка е предимно за това, като допълнително ще ви сблъска с по-сложни задачи, понякога съдържащи неочевидни частни случаи.

Цел

Да се научите как да тествате решенията си и да свикнете сами да намирате грешките си. Да срещнете няколко по-математическо насочени задачи. Да се запознаете с ACM-style начина на тестване.

Задачи

За целта ще ползваме руския сайт Timus, най-вече защото:

• Руските задачи често имат много tricky тестове
• Руските задачи често съдържат в себе си математика и/или геометрия
• Задачите в Timus са ACM стил, тоест няма да ви бъде казано къде грешите и ще трябва да намирате грешките си сами

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

Аудитория

Добрите състезатели от C и B група, както и тези от А. Ако участвате в TopCoder се очаква да сте син или жълт.

Изисквания

Да имате регистрация на сайта на Timus, но освен това нищо специално. Системата в Timus е една от най-лесните за ползване, които сме срещали, така че не мислим, че ще имате проблеми с нея.

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

От вас се иска да решите 90 задачи от Chapter 1 (които и да е 90, стига да са само от него!). Няма голямо значение в какъв ред ги решавате, даже често ако "забиете" на някоя задача може да минете на някоя друга. Помъчете се сами да решите задачата и сами да откриете защо решението ви е грешно (WA%d). За целта може да се наложи да си правите генератор на тестове, бавно (но вярно) решение или подобни техники, които са полезни и на IOI състезания. Готиното е, че може да изберете 90-те задачи, които на вас са ви най-лесни (тоест вие избирате кои 10 задачи да "оставите" и да не решавате).

Както има много прости задачи (A+B Problem), така има и много сложни такива. Ако наистина от много време сте забили на дадена задача и не можете да я измислите, или "тоя 7-ми тест не минава и не минава", погледнете discussion board-а за съответната задача. Но прибягвайте за него само ако наистина не можете да направите нищо повече по нея.

Огромна грешка е да прочетете задачата, да отидете в discussion board-а и да видите как става, без да сте помислили задълбочено или да сте пробвали да я направите сами. Също така не помага много да я напишете, получите WA7 и веднага да отидете в discussion board-а за да видите какъв е теста (за някои от задачите има хинтове или самите по-трики тестове).

Ако получите WA или TL на някой тест, преди да прибегнете до discussion board-а, пробвайте да намерите проблема сами. Погледнете кода си за имплементационни грешки. Направете си малко по-сложен (от примерните) тест на ръка. Вижте дали програмата ви вади правилен отговор за него. Помислете какви са частните случаи на задачата. Помислете какво би било гаден тест (това е по-скоро за time limit отколкото за wrong answer). Помислете защо Greedy би било грешно, ако сте писали такова. Ако имате TL помислете дали сложността на решението ви е достатъчно добра за дадените ограничения. Помислете дали тя наистина е такава (тоест няма много специфичен тест, при който подходът ви да не се държи толкова добре). Ако има такъв тест, то най-вероятно руснаците са го намерили :) Направете си генератор и бавно решение, пуснете го на няколко стотин/хиляди теста. В голяма част от случаите това ще е достатъчно да си намерите грешка.

Разбира се, има и задачи с много хитри тестове. Ако горните методи за откриване на проблема не дадат резултат, не остава какво друго да направите, освен да погледнете в discussion board-а или да питате някого, който я е решил.

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

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

Резултат

След тази тренировка ще сте подготвени за (или поне ще очаквате xD) задачи с трики тестове. Ще обръщате много повече внимание на частните случаи. Също така ще сте по-запознати със ACM-стил задачите. Ще подобрите challenge skill-овете си в TopCoder. След нея се очаква да станете във високите нива на жълтото, доближавайки се до червеното в TopCoder.

предишна тема

версия за печат

следваща тема