Post #120

Разбор задач с чемпионатов: от идеи до кода. Анализируем задачу с финала ICPC 2024: "Оптимальное размещение серверов". Сложность: 2500+ rating. Условие (упрощенно): Есть граф из N городов и M дорог. Нужно разместить K серверов так, чтобы максимальное расстояние от любого города до ближайшего сервера было минимальным. Первые мысли участников: ❌ "Переберем все сочетания из K серверов" — O(C(N,K)) = TLE ❌"Жадно ставим серверы" — не всегда оптимально ✅ "Бинарный поиск по ответу!" Ключевая идея: Если можем разместить K серверов с максимальным расстоянием ≤ D, то можем и с расстоянием ≤ D+1. Монотонность → бинарный поиск! Алгоритм пошагово: cpp bool canPlace(int maxDist, int servers) { // Жадно размещаем серверы // BFS от каждого размещенного сервера // Проверяем, покрыли ли все города } int left = 0, right = N; while (left < right) { int mid = (left + right) / 2; if (canPlace(mid, K)) right = mid; else left = mid + 1; } Функция проверки: 1. Помечаем все города как "непокрытые" 2. Жадно: берем любой непокрытый город 3. Ставим сервер так, чтобы покрывать максимум городов 4. BFS для определения покрытых областей 5. Повторяем, пока есть серверы Типичные ошибки: • Неправильная функция проверки (не жадная стратегия) • Забыли учесть случай K ≥ N • Ошибка в BFS (неправильные условия остановки) • Переполнение при больших расстояниях Альтернативный подход (DP): cpp dp[mask][last] = минимальное расстояние для размещения серверов по маске с последним в last Работает для N ≤ 20, сложность O(2^N * N²) Оптимизации: • Предподсчет всех расстояний (Floyd-Warshall) • Использование битовых операций для множеств городов • Эвристики для отсечения неперспективных вариантов 📊 Статистика по задаче: • Решили: 12 из 140 команд • Время первого AC: 3ч 42мин • Средние попытки до AC: 4.2 Почему задача сложная: 1. Неочевидность бинарного поиска по ответу 2. Сложная функция проверки с жадным размещением 3. Много граничных случаев 4. Требует знания графовых алгоритмов ➡️Урок для участников: Видите формулировку "минимизировать максимум" → думайте о бинарном поиске! Часто решение состоит из классических алгоритмов в необычной комбинации. @fsprussia #ФСП#СпортивноеПрограммирование