Разберу некоторые задачи.
Простые я многие не решал, так как во время тура не мог писать нормально, а на дорешивании это не очень интересно, но общая идея такая:
C кажется просто надо сделать что написано
F видимо дийкстра
G это поощрительная задача
и J - есть острое сомнение, что на Java и BigDecimal сдается моментально.
Задача B.
Решать будем для каждой отдельной компоненты связности.
Сначала избавимся от очень дурацкой вещи - вершин со степенью один. Легко доказать, что если степерь вершины равна единице, то и степень смежной ей вершины тоже единица. Отлично :о) Это мы покрасить можем.
Теперь полагаем, что степень всех вершин не единица.
Возьмем произвольную вершину, и покрасим ее в первый цвет. Возьмем любую смежную с ней вершину, и покрасим во второй. Теперь будем до победного делать очевидную вещь - если у вершины есть смежные ей двух разных цветов, красить ее в третий.
Теперь легко доказать, что это покрасит всю компоненту связности. Пусть это не так. То есть в какой-то момент времени мы остановились, и осталась хотя бы одна вершина, не покрашенная. Очевидно, что тогда есть ребро, связывающее покрашенную и не покрашенную вершину. Пусть покрашенная вершина - А, а непокрашенная - Б. Так как А покрашена, у нее есть две смежных вершины ей двух других цветов (иначе почему бы мы покрасили А?), возьмем только одну из них, другая нас не интересует. Пусть эта вершина - В. То есть мы имеем вершину А одного цвета, смежную ей вершину В другого цвета и смежную вершине А вершину Б не покрашенную. В и Б не обязательно смежны, но! между В и Б есть путь, пролегающий через вершины, смежные А (по условию того, что все вершины, смежные с А, образуют связный граф). Пусть эта цепочка В-Х1-Х2-Х3-Б. Обратите внимание, что мы можем ее покрасить. Х1 смежна с В и А, которые разных цветов, и потом красится в оставишйся, аналогично красится Х2, далее Х3, и наконец, Б. То есть Б не могла остаться не покрашенной.
В общем задача требует от нас покраски в лоб по большому счету.
Задача D
Первое наблюдение - оба дуэлянта никогда не зайдут в одну боковую аллею, так как это pointless. Если дуэлянт входит в аллею, где сейчас другой дуэлянт, это странно - они тогда точно столкнуться, в тоже время не войдя в нее мы гарантированно избежим столкновения.
Если дуэлянт входит в аллею, где был другой дуэлянт прежде, то значит они уже разошлись - это вообще не имеет смысла рассматривать :о)
То есть до момента, когда дуэлянты столкнутся или разойдутся, каждая боковая аллея будет посещена максимум одним из них. А значит решать можно так:
1. Закрепим за 2^20 в какие из боковых аллей хотя бы один дуэлянт войдет
2. Создадим четыре типа событий (первый дуэлянт вошел в аллею, второй дуэлянт вошел в аллею, первый вышел ,второй вышел) и пойдем по событиям, пока либо второй не окажется выше первого без столкновения, либо пока они не столкнутся.
Задача E.
Для каждого отрезка АВ построим прямую, перпендикулярную ему и проходящую через точку А, и другой, проходящий через точку В. Для каждой такой прямой будем хранить два списка перпендикулярных ей отрезков - те, у которых левый конец лежит на этой прямой, и те, у которых правый конец лежит на этой прямой. Для вертикальных отрезков, у которых нет левых и правых концов, соответственно будем брать нижний и верхний.
Для каждой прямой оба списка должны быть отсортированы по удалению лежащего на этой прямой конца отрезка до какой-то очень далекой точки на этой прямой.
Теперь рассматриваем каждый отрезок СД. Для скольких букв Ш, у которых торчалки идут вправо (или если лежачая палочка строго горизонтальная, то идущих вверх) она будет лежачей палочкой? Очевидно, чтобы посчитать это, надо понять
а) У скольких отрезков левый конец лежит на этой прямой, в точности в точке С
б) У скольких отрезков левый конец лежит на этой прямой в точности в точке Д
в) У скольких отрезков левый конец лежит на этой прямой между точками С и Д.
И перемножить эти три числа.
Так как мы знаем все отрезки, у которых левый конец лежит на прямой, содержащей СД, и они у нас отсортированы, ответить на все три вопроса кажется не очень сложным.
Аналогично считаем, сколько букв Ш идут в обратную сторону от закрпленного отрезка. Рассматриваем так каждый отрезок в роли лежачей палочки, суммируем ответ. Получается что-то вроде N log N.
Задача I (разбор предоставлен Сергеем Штейнером)
Нам нужно вычислить сумму весов остовных деревьев, делённую на их количество. Вычислим для каждого ребра, какой вклад оно даст туда. Понятно, что i-е ребро появится в сумме N - N_i раз, где N - количество остовных деревьев вообще, а N_i - количество остовных деревьев, не содержащих i-е ребро, то есть количество остовных деревьев в графе с удалённым i-м ребром. Заметим, что для всех рёбер, инцидентных одной и той же паре вершин N - N_i одно и то же. Итак, осталось научиться вычислять количество остовных деревьев в мультиграфе. Тут нам на помощь приходит матричная теорема Кирхгофа:
http://ru.wikipedia.org/wiki/%D0%9C%D0%B0%D1%82%D1%8...
Теперь мы перебираем все пары вершин и за O(n^3) считаем ответ для каждого ребра. Итоговая сложность O(n^5).
Задача К.
Нам нужна структура данных, позволяющая удалять один элемент, и говорить в какой позиции находится K-ый максимальны, и выполнять оба действия быстро.
Чтобы сделать это можно поддерживать два дерева, которые говорят, в каких позициях в оригинальном массиве нет уже элементов, и в каких позициях в отсортированном массиве нет элементов. Первое дерево позволяет по сдвинутой позиции получить оригинальную позицию (это надо для удаления, чтобы понять какой же элемент удалить), второе - ответить на вопрос, какое же сейчас число I-ое по величине.
Оба действия получаются log n
Задачу А более менее кажется понятным как решать - в каждый момент времени возможные позиции наших войск - это многоугольник с вырезанными дырами. С ходом времени все вершины внешнего многоугольника двигаются по диагонали в сторону расширения, а всех дыр - по диагонали в сторону уменьшения дыры. Когда происходит взрыв, надо улучшить многоугольник, вырезав из него квадрат, который взорвали, и так дальше продолжать. Это видимо самая сложная чась.
Или я не прав?
Задача H мне очень интересна after all :о)
Простые я многие не решал, так как во время тура не мог писать нормально, а на дорешивании это не очень интересно, но общая идея такая:
C кажется просто надо сделать что написано
F видимо дийкстра
G это поощрительная задача
и J - есть острое сомнение, что на Java и BigDecimal сдается моментально.
Задача B.
Решать будем для каждой отдельной компоненты связности.
Сначала избавимся от очень дурацкой вещи - вершин со степенью один. Легко доказать, что если степерь вершины равна единице, то и степень смежной ей вершины тоже единица. Отлично :о) Это мы покрасить можем.
Теперь полагаем, что степень всех вершин не единица.
Возьмем произвольную вершину, и покрасим ее в первый цвет. Возьмем любую смежную с ней вершину, и покрасим во второй. Теперь будем до победного делать очевидную вещь - если у вершины есть смежные ей двух разных цветов, красить ее в третий.
Теперь легко доказать, что это покрасит всю компоненту связности. Пусть это не так. То есть в какой-то момент времени мы остановились, и осталась хотя бы одна вершина, не покрашенная. Очевидно, что тогда есть ребро, связывающее покрашенную и не покрашенную вершину. Пусть покрашенная вершина - А, а непокрашенная - Б. Так как А покрашена, у нее есть две смежных вершины ей двух других цветов (иначе почему бы мы покрасили А?), возьмем только одну из них, другая нас не интересует. Пусть эта вершина - В. То есть мы имеем вершину А одного цвета, смежную ей вершину В другого цвета и смежную вершине А вершину Б не покрашенную. В и Б не обязательно смежны, но! между В и Б есть путь, пролегающий через вершины, смежные А (по условию того, что все вершины, смежные с А, образуют связный граф). Пусть эта цепочка В-Х1-Х2-Х3-Б. Обратите внимание, что мы можем ее покрасить. Х1 смежна с В и А, которые разных цветов, и потом красится в оставишйся, аналогично красится Х2, далее Х3, и наконец, Б. То есть Б не могла остаться не покрашенной.
В общем задача требует от нас покраски в лоб по большому счету.
Задача D
Первое наблюдение - оба дуэлянта никогда не зайдут в одну боковую аллею, так как это pointless. Если дуэлянт входит в аллею, где сейчас другой дуэлянт, это странно - они тогда точно столкнуться, в тоже время не войдя в нее мы гарантированно избежим столкновения.
Если дуэлянт входит в аллею, где был другой дуэлянт прежде, то значит они уже разошлись - это вообще не имеет смысла рассматривать :о)
То есть до момента, когда дуэлянты столкнутся или разойдутся, каждая боковая аллея будет посещена максимум одним из них. А значит решать можно так:
1. Закрепим за 2^20 в какие из боковых аллей хотя бы один дуэлянт войдет
2. Создадим четыре типа событий (первый дуэлянт вошел в аллею, второй дуэлянт вошел в аллею, первый вышел ,второй вышел) и пойдем по событиям, пока либо второй не окажется выше первого без столкновения, либо пока они не столкнутся.
Задача E.
Для каждого отрезка АВ построим прямую, перпендикулярную ему и проходящую через точку А, и другой, проходящий через точку В. Для каждой такой прямой будем хранить два списка перпендикулярных ей отрезков - те, у которых левый конец лежит на этой прямой, и те, у которых правый конец лежит на этой прямой. Для вертикальных отрезков, у которых нет левых и правых концов, соответственно будем брать нижний и верхний.
Для каждой прямой оба списка должны быть отсортированы по удалению лежащего на этой прямой конца отрезка до какой-то очень далекой точки на этой прямой.
Теперь рассматриваем каждый отрезок СД. Для скольких букв Ш, у которых торчалки идут вправо (или если лежачая палочка строго горизонтальная, то идущих вверх) она будет лежачей палочкой? Очевидно, чтобы посчитать это, надо понять
а) У скольких отрезков левый конец лежит на этой прямой, в точности в точке С
б) У скольких отрезков левый конец лежит на этой прямой в точности в точке Д
в) У скольких отрезков левый конец лежит на этой прямой между точками С и Д.
И перемножить эти три числа.
Так как мы знаем все отрезки, у которых левый конец лежит на прямой, содержащей СД, и они у нас отсортированы, ответить на все три вопроса кажется не очень сложным.
Аналогично считаем, сколько букв Ш идут в обратную сторону от закрпленного отрезка. Рассматриваем так каждый отрезок в роли лежачей палочки, суммируем ответ. Получается что-то вроде N log N.
Задача I (разбор предоставлен Сергеем Штейнером)
Нам нужно вычислить сумму весов остовных деревьев, делённую на их количество. Вычислим для каждого ребра, какой вклад оно даст туда. Понятно, что i-е ребро появится в сумме N - N_i раз, где N - количество остовных деревьев вообще, а N_i - количество остовных деревьев, не содержащих i-е ребро, то есть количество остовных деревьев в графе с удалённым i-м ребром. Заметим, что для всех рёбер, инцидентных одной и той же паре вершин N - N_i одно и то же. Итак, осталось научиться вычислять количество остовных деревьев в мультиграфе. Тут нам на помощь приходит матричная теорема Кирхгофа:
http://ru.wikipedia.org/wiki/%D0%9C%D0%B0%D1%82%D1%8...
Теперь мы перебираем все пары вершин и за O(n^3) считаем ответ для каждого ребра. Итоговая сложность O(n^5).
Задача К.
Нам нужна структура данных, позволяющая удалять один элемент, и говорить в какой позиции находится K-ый максимальны, и выполнять оба действия быстро.
Чтобы сделать это можно поддерживать два дерева, которые говорят, в каких позициях в оригинальном массиве нет уже элементов, и в каких позициях в отсортированном массиве нет элементов. Первое дерево позволяет по сдвинутой позиции получить оригинальную позицию (это надо для удаления, чтобы понять какой же элемент удалить), второе - ответить на вопрос, какое же сейчас число I-ое по величине.
Оба действия получаются log n
Задачу А более менее кажется понятным как решать - в каждый момент времени возможные позиции наших войск - это многоугольник с вырезанными дырами. С ходом времени все вершины внешнего многоугольника двигаются по диагонали в сторону расширения, а всех дыр - по диагонали в сторону уменьшения дыры. Когда происходит взрыв, надо улучшить многоугольник, вырезав из него квадрат, который взорвали, и так дальше продолжать. Это видимо самая сложная чась.
Или я не прав?
Задача H мне очень интересна after all :о)
Comments (0)
