Як стати чемпіоном Уралу з програмування - Книжкова полиця
Минули роки. Змінилися покоління; в УрДУ, як і в інших вузах, зовсім інші люди грають уже в ACM-програмування. Наші погляди на спортивне програмування пройшли шліфування часом та нескінченними баталіями. Максималізм поступився місцем зрілому досвіду. Не писатимемо про те, в чому ми не можемо вважати себе експертами — залишимо це Андрію Лопатіну та Миколі Дурову. Найкраще напишемо про те, що кожному з нас вдавалося тричі: як стати чемпіоном Уралу з програмування.
Ми тепер, на жаль, працюємо у різних містах і статтю довелося збирати із різних фрагментів, написаних від першої особи. При остаточному зведенні тексту спочатку хотілося кожне “я” ми спочатку хотіли замінити “я” (Н.Ш.) чи “я” (Л.В.). Але за роки гри в одній команді у нас склався досить загальний погляд на ті речі, про які йтиметься нижче, і тому ми вирішили залишити все "я" в тексті без змін. Вважатимемо, що це наше колективне "я", таке собі розподілене Санкт-Єкатеринбурзьке "я" розповідає про свій досвід виступів у перших п'яти чемпіонатах Уралу з програмування.
ЩО ТАКЕ - "БУТИ КРАЩЕ"
Правилами чітко визначено умови перемоги на олімпіаді з програмування за регламентом ACM. Команда має вирішити більше завдань, ніж інші команди, а за рівності кількості вирішених завдань — заробити менше штрафного часу. Отже, для того, щоб вигравати на олімпіаді з програмування, потрібно бути краще за інших. І це "найкраще" складається з багатьох факторів. Для перемоги у змаганні на комплекті різних завдань, необхідно знайти рішення по можливості більшої кількості завдань, і якісно, чисто, швидко запрограмувати кожну з вирішених.
ЯК ВИРІШУВАТИ ЗАВДАННЯ
Я не знаю,як розв'язувати задачі. Я знаю тільки, що після того, як вирішиш їх багато, починаєш робити це краще, починаєш краще бачити можливі підходи до вирішення завдань, починаєш краще їх відчувати. І все одно не останню роль тут відіграє фактор "здібностей", "таланту". Те, що словами не визначити, і жодним аршином не виміряти. Чинник невизначеності, який у підсумку ранжує абсолютно рівні з підготовки команди. Тому надалі ми вважатимемо, що всі команди, які виходять на старт чергового контесту, абсолютно рівні за своїми здібностями. Постараємося показати тепер, як можна максимізувати решту параметрів, що визначають успіх команди. Адже вирішити завдання — це півсправи, треба ще й запрограмувати рішення.
МАШИНА ДЛЯ УКЛАДАННЯ ЦЕГЛ
Реалізація — це в певному сенсі не така творча справа, як вирішення завдання. Говорячи так, ми анітрохи не хочемо образити талановитих кодерів, які справжню насолоду знаходять у віртуозному використанні ресурсів мови для оптимальної реалізації начебто банальних речей. Ми лише хочемо підкреслити, що вміння якісно реалізовувати рішення набагато більшою мірою піддається тренуванню та поліпшенню порівняно з умінням вирішувати завдання.
Єдиний шлях перемогти в якісній реалізації - це виховати в собі машину, яка за програмування дуже рідко звертається до голови. Голова при кодуванні може підключатися до процесу лише в критичні моменти, і, обов'язково, не в той момент, коли кодувальник знаходиться за комп'ютером. Здебільшого кодувальник повинен уміти збирати програму із заготовленої цегли. Чим більше під рукою готових шаблонів, тим швидше та надійніше збереться програма. Якщо вам доведеться вигадувати як зробити той чи інший блок, людина, у якоївін уже є - сидить у пальцях, як кажуть - безперечно обжене вас у реалізації.
Тут на допомогу можуть прийти така практична рекомендація: збирають завдання з цегли до того, як сядуть за машину. Нормою має стати таке правило: всі завдання, починаючи з другої, повинні кодуватися шляхом передруку з папірця. Таким чином, отримуємо, що першим завданням має бути деяке технічно очевидне завдання — при цьому воно необов'язково має бути найлегшим.
Сила підходу, що ґрунтується на програмуванні з готових шаблонів, полягає в тому, що реалізація готових алгоритмів доводиться до автоматизму, і в цьому випадку великі та складні ділянки коду стають одразу налагодженими. Тоді налагоджувати необхідно лише з'єднувальні ділянки коду — вони майже завжди менші і, до того ж, логічно простіше.
КЛОН САМОГО СЕБЕ
Для формування більш ясного уявлення про те, що таке добре, а що таке погано, потрібно вирішувати безліч завдань на judge і timus. Бажано списуватися з іншими учасниками та просити їх надіслати рішення тих завдань, код яких вас не задовольняє. Ще корисніше завантажувати рішення журі півфінальних змагань. Особливо хороші завдання традиційно у Пітері, Чехословаччині, Канаді та Німеччині. Після вирішення цих завдань порівняйте ваші рішення з рішеннями журі. Якщо ваші рішення кращі (коротше, витонченіші, зрозуміліші) — вітаю. Якщо ні — зрозумійте, чим ваші рішення гірші та перевчитеся. Аналіз коду - це не копання в брудній білизні, а дуже гідне заняття, яке може багато чого навчити. Постарайтеся писати однакові речі Абсолютно однаково. Це необхідно, щоб не помилятися у простих випадках. Проте, якщо знаходите найкращий спосіб реалізації, перевчитися. Я особисто почерпнув від канадців багатоідей.
Якщо у вас вже щось сидить у пальцях – не забувайте регулярно це освіжати та повторювати. Повертайтесь знову до завдань, які ви вирішували колись давно. Якщо коли-небудь ви зможете написати рішення, що повторює торішнє байт у байт, це привід для радості.
Наступний етап, якого необхідно прагнути — це стандартизація уявлень усередині команди. Відступи, правила використання функцій, введення та висновок, іменування змінних та функцій – все має бути уніфіковано. Тоді й перехресне налагодження буде швидшим, адже менше треба один одному пояснювати. Дуже корисно брати програму і пояснювати іншій людині, як вона працює. Загальний стиль - це те, чого треба прагнути постійно.
Я дуже добре пам'ятаю момент, коли ми паралеліли в Пітері завдання про доміно і, не змовляючись, однаково назвали функцію, якою стикувалися наші модулі. Саме в цей момент за 25 хвилин до кінця контесту я повірив, що ми будемо у фіналі.
ТЕХМІНІМУМ
Щодо того, які конкретно алгоритми треба знати: необхідно знати все! Щоправда краще вивчати їх у порядку зростання складності. Що користь від того, що ви знаєте як програмувати угорський алгоритм, якщо ви не вмієте розкладати число на прості множники. Друге завдання зустрінеться у сто разів частіше. Дуже корисно у цьому плані вирішувати завдання з книги Матюхіна, Пономарьова.
Однак, не можна осягнути неосяжне. І тому досить давно в нашій команді було вироблено практику, яку я вважаю дуже корисною. А саме, окреслено деяке коло завдань, яке ми визнали техмінімумом, обов'язковим для кожного. Інші типи завдань були поділені між учасниками команди для спеціального вивчення. У техмінімум були включені базові, загальновідомі алгоритми і, що важливо,цеглини, які неминуче виникають під час програмування алгоритмів будь-якої складності.
ТРЕНУВАННЯ
Намагайтеся урізноманітнити ваші тренування. Не обмежуйтесь моделюванням типового контесту. Досить легко вигадати різні види тренувань, особистих, командних та особисто-командних, які допомагають відточувати ті чи інші аспекти майстерності.
Ось, наприклад, після робочого дня рідко залишаються сили на повноцінне тренування. Та й сенсу в такому тренуванні буде небагато. У цій ситуації корисно взяти 2-3 важкі завдання на 1.5-2 години, причому це можуть бути завдання, над якими раніше ви вже думали. Таким чином, відмінно моделюється ситуація фінішу (і робочий день позаду додає природності), який так часто є каменем спотикання для багатьох команд.
Відмінним тренуванням є придумування завдань, підготовка змагань школярів, придумування тестів до завдань. Нарешті, корисно вирішувати дослідницькі завдання, які потребують занурення у спеціальну літературу та кілька днів роздумів.
ОТРИМУЙТЕ ЗАДОВОЛЕННЯ
Дуже важливим є і психологічний аспект; я пам'ятаю безліч прикладів, коли сильна команда “перегорала” у відповідальних змаганнях через психологічний тягар на її плечах. Чудово, коли команда є колективом однодумців. Якщо ні – працюйте над моральним кліматом у команді. Не дуже добре, коли у команді є яскраво виражений лідер, на якому лежить відповідальність за всі рішення; набагато краще - але важче - випестити командне "я", яке вміє приймати правильні рішення навіть у найважчих ситуаціях.
Намагайтеся отримувати задоволення від процесу гри - це дуже важливо. Будьте азартними, будьте впевнені в собі. Якщо ви навчилися отримувати задоволення від гри, тоне слід тренуватися в останні дні перед важливим змаганням: тоді ви не відчуватимете пересичення, а зможете рватись у бій.
Якщо хочеш навчитися програмувати – програмуй. Постійно дивіться на всі боки, як люди програмують, це не дасть вам збитися з дороги.
Вони містить величезна кількість ідей. Доводьте до автоматизму реалізації цих алгоритмів.
Добивайтеся однакового погляду на якісний код своєї команди.
Професіонал завжди кращий за любителя. Робіть із себе професіоналів.
Головне перемога, але участь теж непогано.
Відпочивайте. Приїжджайте на контест як на свято. Намагайтеся розслабитися та отримати максимум задоволення.
P.S. На одному поверсі з моїм кабінетом немає кабінету Дону Кнута. Я не їм креветок з видом на Тихий океан. Але я тричі виграв чемпіонат Уралу і взяв бронзу на чемпіонаті світу, хоча ніколи нічого особливого не показував у шкільних олімпіадах і не можу похвалитися визначними здібностями. Колись мені важко було навіть зрозуміти – чому це сталося. Але заднім розумом усі сильні. Тепер я розумію: я просто намагався дотримуватися тих принципів, які описані вище.
чемпіон Уралу 1998-2000,
програміст Transas Software House, світовий лідер ІТ рішень для морської індустрії, Санкт-Петербург.
чемпіон Уралу 1999-2001,
керівник лабораторії Інтернет-технологій компанії "СКБ Контур", Єкатеринбург,