Output-only / оптимизационни задачи — материали

Тези задачи нямат едно "вярно" решение — точкува се колко добър е изходът ви.
Печелившите подходи почти винаги стъпват на едни и същи техники:

- greedy конструкция за бърз валиден baseline;
- добре подбрана objective function (оценъчна функция), която да виждате локално;
- hill climbing — малки промени, оценяваш, приемаш ако е по-добре;
- при нужда simulated annealing, random restarts и portfolio от евристики
  (различен метод за различните тестове/компоненти).

Целта е инженерен цикъл, не един магически алгоритъм:
валиден baseline → локален evaluator → проста евристика → декомпозиция →
локално подобряване → measure everything → пази най-добрия изход.

Друго нещо, което често се оказва важно, е да отделите време да проучите тестовете,
които са ви дадени. Някои от тях обикновено могат да се решат по по-лесен начин от
останалите, а можете и да имате различни стратегии за различни тестове.

Материали онлайн

- HKOI — Interactive / Output-only / Communication tasks (слайдове 12–24):
  https://assets.hkoi.org/training2017/nbt.pdf
- OI-Wiki — Hill Climbing:
  https://en.oi-wiki.org/misc/hill-climbing/
- Aerobatics — официален разбор (на японски), JOI 2021 Spring Camp:
  https://www2.ioi-jp.org/camp/2021/2021-sp-tasks/day1/aerobatics-review.pdf

Задачи

- Azul (контрола 2026): https://infos.infosbg.com/files/Contests/K/2026/A/K/statements/azul.pdf
- Aerobatics (JOI 2021): https://oj.uz/problem/view/JOI21_aerobatics
- Nowruz (IOI 2017): https://oj.uz/problem/view/IOI17_nowruz
- Broken Line (IOI 2019): https://oj.uz/problem/view/IOI19_line
- Router (CEOI 2016): https://oj.uz/problem/view/CEOI16_router
- Interference (APIO 2013): https://oj.uz/problem/view/APIO13_interference
- Legendary Dango Maker (JOI 2020): https://oj.uz/problem/view/JOI20_dango2
- Maze (IOI 2010): https://oj.uz/problem/view/IOI10_maze

За допълнителна тренировка с heuristic/optimization задачи:

- AtCoder — Introduction to Heuristics Contest:
  https://atcoder.jp/contests/intro-heuristics
- AtCoder Heuristic Contest (AHC) — редовни състезания точно в този стил:
  https://atcoder.jp/contests/archive?category=50