Стендап Сьогодні 📢 Канал в Telegram @stendap_sogodni

🤖🚫 AI-free content. This post is 100% written by a human, as is everything on my blog. Enjoy!

28.09.2024

Олімпіадне програмування

Мій шлях програмування почався в школі з двох речей. Перша - ігри для DOS. Друга — олімпіадне програмування.

Олімпіадне програмування не схоже на 99.99% моєї карʼєри (А чи є галузі, де це не так? Пишіть, якщо знаєте.) Більшість задач хоч і можна розвʼязати прямолінійно (але не всі) - проте абсолютно завжди тривіальне рішення (той самий brute force, або “повний перебір”) не впорається за поставлені рамки часу або памʼяті. Тестові приклади міститимуть достатню кількість даних, щоб це перевірити.

Тому справжня задача в пошуці кращого розвʼязку. Майже завжди він не має нічого спільного з тривіальним рішенням (хоча є й оптимізації, як відтинання гілок). Тут треба знати базові алгоритми, наприклад, динамічне програмування. Або цілі родини алгоритмів, як роботу над графами чи обчислення з надвеликими числами. Хоча, звісно, тільки знаннями задачі не розвʼязуються — в першу чергу треба вміти побачити у вхідних умовах аспекти того чи іншого алгоритму, а також його адаптувати.

Я олімпіадні роботи писав на Паскалі. Це досить зручна мова для алгоритмічних задач: в міру низькорівнева, але з красивим синтаксисом, що нагадує псевдокод. Високорівнева мова, гадаю, не дуже спростила б рішення, зате було б складніше передбачати витрати.

В інженерній практиці ми рідко стикаємося з задачами, де повний перебір не дає прийнятного рішення. Наприклад, пошук елементу в невпорядкованому масиві — це повний перебір — ну й добре. А інші задачі декомпоновані та абстраговані. Наприклад, пошук елементу в словнику — то вже один з різновидів обходу дерева, але ми про це й не думаємо. Та й взагалі програмна інженерія значно більше піклується складністю когнітивною, а не обчислювальною.

Якщо хочете спробувати, пропоную сервіс USACO Training. Якимсь чином він залишився живим ще з початку 2000-х. Там гарна драбинка задач та посилання на інші ресурси, а писати розвʼязки можна навіть на Python та Java.