Блог пользователя al13n

Автор al13n, 11 лет назад, По-русски

Нам (viral team: al13n, eik0u, Alex_KPR) нужен третий участник, чтобы съездить на онсайт challenge24. Мы туда прошли, но Alex_KPR не сможет поехать. Может быть, у кого-нибудь нет команды/не прошел/проспал отборочный раунд, и он(а) хочет присоединиться к нам?

С решением придется поторопиться: до мероприятия меньше месяца, и нужно успеть сделать визу и купить билеты.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +28
  • Проголосовать: не нравится

Автор al13n, 13 лет назад, По-русски

UPD: Ок, видимо, это бесполезный способ: то же самое, но проще, может сделать #pragma hdrstop.

Нашел способ ускорить компиляцию в Visual Studio примерно на 6 секунд, используя precompiled headers. При этом не требуется изменение кода перед отправкой на тестирование. Это достигнуто грязным хаком, о котором ниже :). Вот инструкция:


1) Создаем в проекте файл с названием "stdio.h" (да, обязательно с названием какого-нибудь стандартного хедера). Туда выносим весь шаблон, который не изменяется от программы к программе, в основном инклюды.
2) В Project - Properties - Configuration Properties - C/C++ - Precompiled Headers  выбираем Precompiled Header: Create, Precompiled Header File: stdio.h.
3) Программу начинаем со строк
#include "stdio.h"
#ifdef ONLINE_JUDGE
(тут все содержимое нашего stdio.h)
#endif

Почему нельзя было назвать свой хедер по-человечески и окружить его инклюд в #ifdef? Потому что студия требует, чтобы файл с кодом начинался с инклюда precompiled header, инклюдить в ифдефе не дает.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +10
  • Проголосовать: не нравится

Автор al13n, 14 лет назад, По-русски
Заметим, что правильная система порталов всегда либо связна, либо содержит две компоненты связности, в каждой по одному входу. Доказательство этого внизу. Кстати,  первый вариант всегда невыгоден, потому что из него можно удалить одно ребро, чтобы получить второй вариант дешевле. Построим минимальный остов графа возможных порталов. Если он содержит больше двух компонент связности, на все запросы отвечаем -1. Если содержит две, то отвечаем -1 на запросы, у которых обе вершины в одной компоненте, и вес остова на все остальные запросы. Если компонента одна, нужно уметь разбивать дерево на два так, чтобы две указанные вершины остались в разных. Это делается удалением самого тяжелого ребра в дереве на пути между этими вершинами. Находить вес этого ребра можно, если заранее подвесить дерево и найти для каждой вершины прыжки вверх по степеням двойки (как для LCA) и для каждого прыжка еще вес самого тяжелого ребра на этом пути. Тогда нетрудно расширить алгоритм посика LCA вычислением максимального веса ребра на пути между вершинами.
Доказательство первого утверждения:
Во-первых, понятно, что такая система порталов допустима: мы можем зайти через любой вход, обойти все тоннели в его компоненте связности (связности по порталам), перейти в другую компоненту (между ними есть ребро, ведь граф тоннелей связен), обойти все там, обойти оставшиеся тоннели между компонентами и выйти в одном из выходов. Теперь представим, что помимо этих двух компонент A и B есть еще какая-то C; тогда если количество ребер между A и C четно, а между B и C - нечетно, невозможно обойти все тоннели по разу и вернуться в A или B. Если выходы в одной компоненте связности, и есть еще одна компонента, то все плохо, когда тоннелей между этими компонентами нечетное количество. Доказано.

Полный текст и комментарии »

Разбор задач Codeforces Beta Round 41
  • Проголосовать: нравится
  • +15
  • Проголосовать: не нравится