Очень важные гости
Есть два способа решить эту задачу.
Первый заключается в том, чтобы рассаживать гостей по диагоналям, начиная от позиции (1, 1). Требуется некоторая аккуратность в реализации, чтобы верно учесть случаи n < m и m < n.
Второй способ позволяет не задумываться о том, в какую сторону вытянут прямоугольник. Просто запустим обход в ширину от места (1, 1), и будем рассаживать гостей, начиная от максимального номера, в порядке извлечения мест из очереди.
Наименьшее общее кратное
Пусть p / q нацело делится на a / b и c / d, при этом все дроби несократимые. Тогда целыми числами являются (p / q): (a / b) = (p·b) / (q·a) и (p / q): (c / d) = (p·d) / (q·c).
p·b делится на q·a. Поскольку b и a взаимно просты, p делится на a. p и q тоже взаимно просты, поэтому b делится на q. Аналогично, p делится на с и d делится на q.
Таким образом, p делится lcm(a, c), q делит gcd(b, d). Дробь lcm(a, c) / gcd(b, d) является наименьшей подходящей дробью, и она делится на a / b и c / d. Таким образом, ответ равен lcm(a, c) / gcd(b, d).
Портим порядок
В задаче требуется дополнить исходный массив до перестановки чисел от 1 до n таким образом, чтобы сортировка выбором сделала наибольшее число обменов.
Для начала допустим, что мы уже сгенерировали какую-то перестановку и хотим узнать, сколько обменов совершит сортировка выбором. Для этого будем рассматривать перестановку как набор циклов. Рассмотрим цикл, в котором содержится минимальное число, которое стоит не на своём месте. Длина этого цикла больше чем 1. Нетрудно заметить, что при одном обмене длина соответствующего цикла уменьшается на один и появляется новый цикл длины 1. Теперь заметим, что цикл длины L уменьшит свою длину ровно L - 1 раз в процессе сортировки, из чего следует, что суммарно длины циклов уменьшатся ровно на n - c, где c — количество циклов.
Красно-черное дерево
Заметив тонкий намек в первом предложении условия, легко доказать (или проверить в любой книге по структурам данных), что в любом красно-черном дереве с n вершинами, на пути от корня до листьев O(logn) черных вершин. Воспользуемся этим фактом в решении.
Назовем почти красно-черным дерево, в котором выполняются все свойства красно-черного дерева, но корень дерева покрашен в красный цвет.
С помощью динамического программирования посчитаем для каждого поддерева количество способов покрасить вершины в нем так, чтобы поддерево было красно-черным, и количество черных вершин на пути от корня до листьев равнялось h, или чтобы дерево было почти красно-черным, и количество черных вершин на пути от корня до листьев равнялось h.
Значит, необходимо всего O(nlog(n)) состояний, из каждого из которых идет O(1) переходов. Следовательно решение будет работать за O(nlog(n)).
Изучение массива
Поскольку ограничения на n и q совпадают, будем использовать в n вместо max(n, q). Сделаем несколько наблюдений.
Второе наблюдение: prefi — довольно маленькие ( - n ≤ prefi ≤ n).
Задача А. Сгибание ленточки.
Идея: Владимир Смыкалов. Реализация: Дмитрий Филиппов. Разбор: Дмитрий Филиппов.
В задаче дана полоска 1×2n, которую сначала n раз сложили ровно пополам, а потом развернули обратно. Складывания возможны двух способов: левую половину наложить на правую или правую половину наложить на левую. Требуется отвечать на запросы — по номеру сгиба узнать, ориентирован он вверх или вниз.
Научимся отвечать на запрос за O(log 2n), то есть за O(n). Суммарное количество запросов не превосходит 105, поэтому этого вполне достаточно. Будем эмулировать процесс сгибания для каждого запроса. Зная текущие длину ленточки и номер сгиба, легко понять, в какой половине этот номер находится, а затем, зная, в какую сторону произойдет сгиб пополам, можно найти и новое положение сгиба в укороченной в два раза ленточке. Для ответа на запрос одновременно с положением поддерживаем, в какую сторону сейчас ориентирован сгиб. Итого, получаем решение за O(qn), где q — суммарное количество запросов.
Задача B. Сбор монет.
Идея: Виталий Аксенов. Реализация: Борис Минаев. Разбор: Борис Минаев.
В задаче дана лента, разбитая на клетки, по которой ходит игрок. Каждую секунду в каждой клетке дополнительно появляется некоторое число монет, фиксированное для каждой клетки. Игрок за секунду может перейти в соседнюю клетку или остаться в текущей. Каждый раз когда игрок находится в некоторой клетке, он собирает все монеты, которые в ней находятся. Необходимо посчитать, какое максимальное число монет может собрать игрок за t секунд.
Заметим, что для каждой клетки важно знать только последний момент, когда игрок в ней находился. Рассмотрим путь игрока с конца. В каждый момент времени про некоторый непрерывный отрезок клеток уже известен последний момент их посещения, а для остальных клеток нет. Поэтому можно воспользоваться методом динамического программирования, состоянием которого будет отрезок посещенных клеток и текущее время. Кроме того необходимо хранить текущую позицию игрока. Заметим, что можно хранить только те позиции, когда игрок стоит на одном из концов отрезка посещенных клеток. Из каждого состояния существует не более чем два перехода — игрок может посетить клетку слева или справа от уже посещенных. Таким образом, время работы алгоритма составляет O(n2t).
Задача C. Топологическая сортировка и дети.
Идея: Артем Васильев. Реализация: Виталий Аксёнов. Разбор: Виталий Аксёнов.
В задаче дан граф и его топологическая сортировка, некоторые элементы которой были стёрты. Нужно корректно её восстановить топологическую сортировку.
Рассмотрим сначала алгоритм, а потом докажем его корректность. Вершины, для которых дан порядок, будем называть помеченными, остальные — непомеченными. Мы знаем какие числа не использовались в топологической сортировке, будем выставлять их по одному от больших к меньшим в соответствие вершинам. У нас есть очередное нерасставленное число. Первым делом удалим все уже помеченные стоки. Далее для каждого непомеченного стока узнаем максимальное значение в помеченной вершине, достижимой по обратным рёбрам. Для каждой вершины это число можно предподсчитать заранее: находим какую-либо топологическую сортировку графа и решаем задачу динамического программирования. В качестве соответствующей вершины нерасставленному числу выбираем любой сток, у которого предподсчитанное число наибольшее, и удаляем его из графа.
Предподсчёт чисел выполняется за O(V+E). Каждую итерацию нужно выполнять как можно быстрее, поэтому в каждой вершине мы храним количество оставшихся из неё исходящих рёбер. Когда мы удаляем сток, у всех вершин, из которых есть в него ребро, уменьшается исходящая степень, и если эта степень становится нулём, помещаем эту вершину в сет по предподсчитанному значению. Тем самым в нашем сете хранятся все стоки, и для выбора нужного нам достаточно взять самую последнюю вершину из сета. Каждая вершина кладётся в сет и вытаскивается ровно один раз. Итого время работы алгоритма: O(V·log(V) + E).
Теперь докажем корректность нашего алгоритма. Заметим, что нам достаточно доказать правильность первого шага алгоритма, далее используем метод математической индукции. Рассмотрим корректно заполненную топологическую сортировку p, предварительно выкинув все помеченные стоки. Далее рассмотрим сток s, который мы выбрали нашим алгоритмом для максимального числа, и сток, которому оно соответствует в топологической сортировке p. Если мы все числа в перестановке большие p(s) уменьшим на единицу, а выбранному нами стоку s выдадим максимальное число, перестановка останется корректной. Операция произошла корректно: мы сохранили свойство топологической сортировки для непомеченных вершин, а для помеченных вершин значение топологической сортировки не поменялось, так как по свойству выбора вершины s p(s) больше, чем значение топологической сортировки любой помеченной вершины.
Задача D. Правильный сад.
Идея: Артем Васильев. Реализация: Артем Васильев. Разбор: Артем Васильев.
Для начала докажем эквивалентное свойство: множество точек хорошее тогда и только тогда, когда для каждого угла такого прямоугольника существует точка на смежной с этим углом стороне. Очевидно, если выполняется это свойство, то выполняется и свойство, описанное в условии задачи. Однако, верно и следствие в противоположную сторону: рассмотрим произвольный прямоугольник с углами в точках A и B. По предположению, внутри или на границе этого прямоугольника существует другая точка из множества, назовем ее C. Если эта точка уже лежит на стороне, смежной с A, то наше утверждение верно. Иначе рассмотрим прямоугольник, построенный на точках A и C. Его площадь строго меньше, чем площадь исходного прямоугольника, а точек в множестве конечное число, значит когда-нибудь мы выберем точку, лежащую на стороне, смежной с A.
Сформулированное свойство помогает дойти до решения: для точки (xi, yi) обозначим за lefti такой максимальный x < xi, что в заданном наборе существует точка (x, yi). В случае, когда это значение не определено, считаем его равным равным минус бесконечности. Аналогичным образом введем величины righti, downi и upi. Рассмотрим область (lefti, righti) × (downi, upi). Если в этой области есть другая точка из заданного набора, то можно найти две точки, для которых построенный прямоугольник нарушает свойство. Стоит заметить, что подходит не любая точка из этой области. В качестве второй точки всегда подходит, к примеру, ближайшая по евклидовому или манхэттенскому расстоянию. Когда в этой области находится только точка (xi, yi), все прямоугольники содержат другую точку на стороне, смежной с ней. Таким образом, решение свелось к проверке n прямоугольников на наличие более одной точки внутри.
Реализовать такую проверку можно с помощью любой структуры данных, которая позволяет считать количество точек в прямоугольнике на плоскости: двумерное дерево отрезков (онлайн решение) или оффлайн решение со сканирующей прямой и одномерным деревом отрезков. Такое решение можно реализовать за O(n log(n)).
Задача E. Междуречье.
Идея: Виталий Аксёнв. Реализация: Илья Збань. Разбор: Илья Збань.
В задаче даны n непересекающихся монотонных ломаных и выпуклый многоугольник. Нужно узнать, какое минимальное число раз нужно приложить многоугольник, чтобы каждая ломаная имела хотя бы одну общую точку с одним из приложенных многоугольников (на границе или внутри многоугольника).
Заметим, что поскольку многоугольник выпуклый, а ломаные монотонны и не пересекаются, верен следующий факт: если многоугольник пересекает ломаные i, k, то для любого j, что i ≤ j ≤ k, этот многоугольник пересечет и j-ю ломаную. Используя этот факт, будем решать задачу жадно: найдем максимальное i1, такое, что существует многоугольник, пересекающий все ломаные с 1-й по i1-ю, добавим его к ответу, и продолжим: найдем максимальное i2 такое, что существует многоугольник, покрывающий ломаные с i1+1-й по i2-ю, и так далее. Число многоугольников, которые пришлось использовать, и будет ответом.
Научимся для ломаной ik находить значение ik+1. Это максимальный индекс, такой, что существует многоугольник, покрывающий ik+1-ю и ik+1-ю ломаную. Решим сначала более простую задачу: есть точка A и отрезок BC, нужно проверить, существует ли многоугольник, содержащий внутри себя и данную точку, и какие-то точки отрезка. Для этого построим сумму Минковского этого многоугольника и его самого же, инвертированного относительно (0, 0) (то есть, с противоположными по знаку координатами всех точек). Это какой-то новый многоугольник, назовем его P, с O(n) вершин, содержащий внутри себя точку (0, 0). Сдвинем его так, чтобы точка (0, 0) перешла в точку A, и проверим, что отрезок BC пересекается со сдвинутым многоугольником P — несложно убедиться, что это необходимое и достаточное условие.
Научившись проверять, существует ли многоугольник, пересекающий точку и отрезок, проверить то же самое для двух ломаных совсем несложно: перебираем отрезок на одной ломаной, строим его сумму Минковского с многоугольником P, и проверяем, пересекается ли новый выпуклый многоугольник с каким-нибудь отрезком второй ломаной.
Пусть k — суммарное число вершин на всех ломаных. Найдём асимптотику используемых нами операций — O(n) на построение многоугольника P, O(n) на построение суммы Минковского P и отрезка ломаной и O(log n) на проверку пересечения выпуклого многоугольника и отрезка. Так как многоугольников нужно построить максимум k, а пересечь в худшем случае нужно каждый многоугольник с каждым отрезком, итоговая асимптотика времени работы равна O(nk + k2log n).
Задача F. Робот на дереве.
Идея: Борис Минаев. Реализация: Борис Минаев. Разбор: Борис Минаев.
В задаче дано неориентированное дерево из n ≤ 10 вершин. Про каждое ребро известна его прочность wi, которая не превышает 15. По дереву перемещается робот, который изначально находится в случайной вершине. Каждый раз робот равновероятно выбирает ребро из тех, по которым он может пройти, и перемещается по нему. Каждый раз когда робот проходит по ребру, его прочность уменьшается на единицу. Если прочность становится равна нулю, то ребро удаляется. Если у робота нет ребер, по которым он может пойти, он останавливается. Необходимо посчитать математическое ожидание длины пути робота.
Для начала решим более простую задачу. Предположим, что необходимо посчитать не математическое ожидание длины пути, а количество различных путей, по которым мог пройти робот. Представим, что мы зафиксировали вершины, в которых робот начал и закончил свой путь, а также количество раз, которые робот прошел по каждому ребру. Рассмотрим, какие существуют ограничения на эти количества. Во-первых, ребра, по которым робот прошел положительное число раз, должны образовывать связный подграф исходного дерева. Во-вторых, рассмотрим некоторую вершину и количество раз, которые робот прошел по всем ребрам, которые являются смежными с этой вершиной. Если эта вершина является концом пути, то каждое смежное с ней ребро должно использоваться ровно wi раз. Максимум два ребра смежных с вершиной должны быть использованы нечетное число раз. Причем, если эта вершина лежит на пути из стартовой в конечную, то ровно два ребра должны быть использованы нечетное число раз. Для стартовой и конечной вершины (если они не совпадают) должно быть ровно одно ребро, которое используется нечетное количество раз, либо ноль, если вершины совпадают. Для всех остальных вершин все смежные ребра должны быть использованы четное число раз.
Если все эти условия выполнены, научимся считать количество путей, которые удовлетворяют условию задачи и используют ребра фиксированное количество раз. Для каждой вершины рассмотрим все смежные с ней ребра. Мы знаем количество раз, которое робот прошел по каждому из них. Мы можем легко посчитать, сколько раз робот прошел по ребру в направлении от заданной вершины. В каком порядке робот мог проходить по этим ребрам? Во-первых, по ребру, которое лежит на пути к вершине, в которой робот закончил путешествие, робот должен пройти в последнюю очередь. По всем остальным ребрам он может идти в любом порядке. Подсчет количества таких способов является стандартной задачей. Чтобы посчитать общее количество путей, по которым может пройти робот, необходимо перемножить посчитанные значения для каждой вершины.
Заметим, что для подсчета общего количества путей можно воспользоваться методом динамического программирования. Посчитаем количество путей, которые проходят по некоторому ребру заданное число раз и каким-либо образом проходят по поддереву, которое ограничено этим ребром. При этом считается, что каждый раз, когда путь идет вверх по ребру, он сразу же возвращается назад по нему. Чтобы посчитать значение динамического программирования необходимо зафиксировать количество раз, которые робот прошел по каждому из ребер, которые идут в поддеревья, умножить на уже посчитанные значения для поддеревьев, а также на количество способов расположить переходы в поддеревья. Будем рассматривать поддеревья вершины по очереди и фиксировать количество раз, которые суммарно робот пойдет во все рассмотренные поддеревья. Рассматривая очередное поддерево переберем количество раз, которые робот перейдет в это поддерево. Домножим ответ на значение динамического программирования от поддерева, а также на количество способов расставить переходы в поддерево среди других переходов.
Всего существует O(2children∑wi) состояний в динамическом программировании для заданного ребра, и переход между ними осуществляется за O(1). Так как необходимо посчитать значение динамического программирования для каждого количества раз, в которых было использовано ребро, общее время работы алгоритма получается равным O(2n(∑wi)2).
Про соревнования по программированию от крупных компаний
Эти соревнования рассчитаны не только на школьников — обычно в них вообще нет ограничений и участвовать может кто угодно (основное исключение — это VK Cup, где участвовать можно тем, кому не больше 23 лет). Соревнования обычно направлены на широкую аудиторию, поэтому они обычно проходят в несколько раундов, и в первых раундах задачи не очень сложные, поэтому я рекомендую всем, у кого уровень хотя бы 2-3, участвовать в них. Но при это понимайте, что в финальные раунды обычно проходят несколько десятков человек со всего мира, поэтому большинству из вас будет весьма сложно туда пройти.
Имейте также в виду, что у каждого соревнования свои правила и свой формат. Когда соберетесь участвовать, заранее найдите и прочитайте правила — сколько раундов, какие условия чтобы пройти из одного раунда в другой, как устроен сам раунд и т.д.
Ниже я напишу свое мнение о конкретных соревнованиях; также при приближении очередного соревнования я буду писать про него на страничке курса. Ссылки на конкретные соревнования я тут приводить не буду, т.к. они меняются год от года, лучше просто найдите сайт поиском в интернете.
Яндекс. Алгоритм
Довольно интересное и адекватное соревнование. Раунды проводятся по правилам а-ля ACM, переход в следующий раунд проходит по довольно необычной системе. Проводится в Яндекс.Контесте, что имеет свои плюсы и минусы. Очень рекомендую участвовать.
VK Cup
Участвуют команды из двух человек. Раунды проводятся по правилам Codeforces и на платформе Codeforces. Очень рекомендую участвовать.
Google Code Jam
На мой взгляд, вообще лучшее из всех подобных соревнований, но все материалы (правила, задачи, разборы) — на английском языке. До прошлого года был довольно необычный формат соревнования, когда вы должны были скачивать тест себе на компьютер и могли решать его как угодно вообще, с этого года, похоже, будет более классический формат с отправкой решения в тестирующую систему. Очень рекомендую участвовать, если вы достаточно свободно владеете английским языком или онлайн-переводчиком.
Mail. Ru Russian Code Cup
По задумке довольно неплохое соревнование в довольно классическом формате, но по реализации почему-то у Mail.Ru год за годом возникают какие-то проблемы совершенно разного рода. Рекомендую участвовать, но если у вас стоит выбор, участвовать тут или в других соревнованиях, то участвуйте в других. Кроме RCC, Mail.Ru проводит еще ряд соревнований, в том числе Russian AI Cup, где надо программировать стратегии, но это уже не совсем алгоритмически-олимпиадный формат.
Facebook HackerCup
Большинство раундов проходят глубокой ночью, поэтому я ни разу в нем не участвовал и не могу ничего сказать кроме того, что это довольно известное мероприятие.
Социальная сеть В контакте дала шанс молодым программистам со всего мира проявить свои способности в чемпионате VK Cup. В ходе отборочных этапов соревнования молодым специалистам предлагалось решить несколько алгоритмических задач, используя несколько языков программирования. Те, кто быстрее и качественнее всех справился с этим заданием вышли в финал и там продолжили борьбу за денежный приз от соц. сети Вконтакте. Финалистам было поставлено 5 задач, самую сложную из которых не решил ни один из финалистов.
Но, не смотря на это, денежный приз в 30 тысяч $ оказался в руках 16-летнего китайца Южу Гу, который и стал первым в тройке финалистов конкурса по программированию ВК. Своей победой юный Южу Гу доказал, что именно он лучший разработчик мира. Ведь со слов генерального директора Павла Дурова, цель чемпионата VK Cup была из многих преуспевающих программистов найти лучшего разработчика. Именно поэтому не было никаких ограничений по стране проживания участников, и лучшие были щедро награждены призами. На втором месте расположился также программист из Китая – 17-летний Кинши Вангу, который получил награду в размере 20 тыс. $ за свои старания. Приз в 10 тысяч долларов достался белорусскому 17-летнему программисту Геннадию Короткевичу, который уверенно обошел российских программистов, занявших в 10-ке лучших только 5 и 10-е место.
Администрация соц. сети планировала сначала награждать победителей призами в размере 6-ти, 4-ех и 2-ух тысяч долларов, но увидев, насколько попались умные юные разработчики, они повысили ставки. По подсчетам администрации сети В контакте в соревнованиях по программированию приняла участие не одна тысяча молодых разработчиков. Но для всех обязательным условием стал возраст, который варьировался от 14 до 23 лет, и не принимались к участию в конкурсе сотрудники самого Контакта.
Конкурс VK Cup начался в марте 2012 года, отборочные туры прошли на площадке Codeforces, спонсором которой является социальная сеть Вконтакте. Финал соревнования между молодыми программистами проходил с13 по 16 июля в месте, где хотят побывать все пользователи социальной сети В Контакте, а именно в главном офисе, расположенном в Санкт-Петебурге.
Но это не единственный чемпионат, где Контакт находит себе разработчиков. Павел Дуров поддерживает связь со многими победителями всевозможных соревнований по программированию. В мае 2011 года в штате контакта было 7 самых сильных программистов мира. Кто знает, может кто-то из победителей конкурса VK Cup станет 8-ым программистом, улучшающим соц. сеть.
А вот на разработку различных мессенджеров «ВКонтакте» для платформ iOS, Android и BlackBerry социальная сеть приглашает программистов разного уровня, и для них уже выделено 10 млн. российских рублей.
Такие соревнования на звание лучшего программиста проводит не только социальная сеть Вконтакте, но и компания Mail.Ru Group. В 2012 году состоится уже второй чемпионат между юными программистами Russian Code Cup. За 2011 год в соревнованиях такого типа приняло участие более 3-ех тысяч человек. В их состав вошла Петербургская команда из государственного университета социальных технологий. Именно эта команда стала победителем 36-ой международной олимпиады по программированию ACM ICPC, прошедшей в Польше. Команде из Питера удалось оставить позади себя 111 команд из 80-ти стран со всего мира. Ей удалось сделать то, что не смогли сделать остальные команды, решить рекордное количество задач для данного конкурса, а именно 9 задач из 12.
На данный момент в контакте – это самая популярная и крупнейшая сеть в Росии. Более 120 млн. людей уже являются пользователями Контакта. Ежедневное посещение сайта составляет более 36 миллионов посетителей.