Приветствую всех участников раунда!
Давайте проведем разбор задач в примерном порядке их сложности
182B - Календарь Васи
Обратим внимание, что Вася должен вручную прибавлять номер дня только тогда, когда заканчивается один месяц, и начинается следующий. Значит, пусть у нас в текущем месяце было x дней, а в следующем уже y. Тогда в первый день следующего месяца часы будут показывать день x + 1 (не забываем про модуль d), а должен показывать номер 1.
Очевидно, что Вася должен вручную прибавить d - x дней, чтобы часы показывали то, что нужно.
Значит, ответ — это сумма всех чисел d - ai, где 1 ≤ i < n.
182D - Общие делители
Эта задача решается многими способами, но самый простой подход следующий: найдем все делители строки s1, все делители s2 и найдем пересечение этих двух множеств.
Как же найти все делители строки? Пусть t — это делитель строки s. Тогда очевидно, что |s| = 0(mod|t|), а также t является префиксом строки s. Эти соображения и позволяют найти все делители строки, а именно переберем длину префикса, проверим делимость, а потом проверим, что префикс записанный подряд нужное количество раз совпадает с s.
Всего подходящих префиксов не более 
, проверка каждого работает за O(|s|), значит, итоговое решение за 
, где n = max(|s|, |t|).
Найти пересечение двух множеств строк несложно, можно воспользоваться стандартными структурами данных
182E - Деревянный забор
Условие задачи было сформулировано неверно, что привело к несоответствию решений, правильный вариант условия появится совсем скоро, приносим участникам свои извинения.
Основа решения этой задачи — это динамическое программирование.
Состояние — (last, type, l), где last — номер последней доски, type характеризует поворот последней доски, а l — длина оставшейся части забора.
Пересчитывать эту динамику тоже очень просто: переберем номер следующей доски, ее поворот, проверим подходит ли она в текущее состояние, и прибавим нужную величину.
Асимпотика решения — O(n2·len).
182C - Оптимальная сумма
Представим мысленно задачу в виде движения слева направо некоторого окошка длины len по исходному массиву. То есть нам нужно найти способ достичь максимума в выбранном окошке, а потом сместить его на одну ячейку вправо.
Пусть мы зафиксировали положения окошка, теперь посчитаем ответ. Для этого отдельно запишем все положительные и все отрицательные числа в окошке. Если положительных не больше, чем k, или отрицательных не больше k, то мы можем все числа сделать одинакового знака, и ответ — это сумма модулей чисел в подмассиве. Это простой случай.
Несложно понять, что невыгодно некоторые отрицательные числа делать положительными и одновременно некоторые положительные — отрицательными. То есть мы обязательно выберем знак «+» или «-» и k чисел этого знака сделаем противоположными. Также несложно понять, что всегда при смене знака у некоторых чисел выгодно брать ровно k максимальных по модулю чисел этого знака.
Для того, чтобы поддерживать движение окошка будем использовать два отдельных дерева отрезков: одно для отрицательных, другое для положительных чисел.
Если в вершине дерева хранить пару (количество чисел в поддереве, сумма этих чисел), то такая структура умеет возвращать сумму k максимальных чисел, что нам и требуется.
Асимптотика решения — O(n·log(n)).
182A - Поле битвы
В этой задаче есть два главных момента:
длина любой траншеи в метрах численно не превосходит b
траншеи не пересекаются
Первый пункт означает, что если Вася забегает в траншею чтобы переждать, пока лазер работает, то за это время он может придти в любую его точку.
Второй пункт означает, что пока лазер работает, Вася обязан находиться в той траншее, в которой он на данный момент сидит.
Значит, путь Васи — это перебежки от одной траншеи к другой, где он пережидает лазерную атаку. Таким образом все решение задачи — это найти кратчайший по времени путь по траншеям от стартовой точки до конечной (их мы тоже будем считать траншеями, просто нулевой длины), для этого нужно всего лишь предподсчитать матрицу расстояний между отрезками траншей и запустить алгоритм, например, Дейкстры.
Два тонких момента:
мы не можем перебегать между траншеями, если между ними расстояние больше a
пусть Вася прибежал в момент времени t, теперь нам нужно найти момент, когда он сможет убежать дальше. Для этого нужно найти следующий момент времени, когда лазер будет перезаряжаться. Эта величина T несложно ищется по формуле:
Асимптотика решения — O(n2).
Dear friends!
The next competition — Codeforces Round 112 for participants Div. 2 will take place through a pair of hours, but the others can traditionally participate out of competition. It has been prepared by a small command of authors: me (NALP), Artem Rakhov (RAD) and Pavel Holkin (HolkinPV). There were Gerald Agapov (Gerald), Maria Belova (Delinur) and Michael Mirzayanov (MikeMirzayanov) with us as always.
Especially I would like to wish good luck to my teammates Artem Rakhov and Max Ivanov (e-maxx) who recently flew to the U.S. to participate in Onsite Round Facebook HackerCup.
We hope that this problems will be pleasant to all participants and everyone will take the deserved high place in the standings :)
UPD: The contest is over, thanks to all for taking part :) We hope you have fun.
UPD: You can find the tutorial here http://codeforces.ru/blog/entry/4124
UPD: Congratulations to the winners!
You can see the full standings here: http://codeforces.ru/contest/165/standings
160A - Близнецы
В этой задаче требовалось найти подмножество наименьшего размера, сумма чисел в котором строго больше, чем половина суммы всех чисел. Несложно понять, что выгоднее брать наибольшие числа в массиве, так мы быстрее наберем нужную сумму. Тогда решение выглядит следующим образом: отсортируем числа по невозрастанию и переберем сколько первых чисел заберем мы, а сколько – наш близнец, Как только у нас строго больше, чем осталось для близнеца – выведем ответ.
160B - Несчастливый билет
Запишем в массив a первые n цифр, а в массив b — последние n цифр, и отсортируем эти массивы. Нетрудно понять, что если для всех i выполняется a[i] < b[i], или для всех i выполняется a[i] > b[i], то билет точно является несчастливым. Но также нетрудно понять, что для любого несчастливого билета выполняется или первое условие, или второе. Таким образом, мы придумали критерий несчастливости, можно реализовать за время O(n· log(n)).
160C - Найти пару
Для начала, мы, авторы раунда, хотим отметить, что эта задача вызвала множество вопросов, хотя в условии было совершенно четко и недвусмысленно написано, что нужно делать. Более того, на почти все вопросы по условию этой задачи мы отвечали скопированным из текста предложением – и у большинства участников больше вопросов не возникало.
Пусть число k и массив a заданы в 0-нумерации, а сам массив отсортируем. Тогда если все числа различны, то очевидный ответ – это пара (a[k / n], a[k % n]), где операция % означает остаток по модулю. Однако, если в массиве есть повторяющиеся числа, то ситуация становится немного хитрее, рассмотрим пример: пусть дан массив (1, 1, 2, 2), тогда пары записаны следующим образом: (1, 1), (1, 1), (1, 1), (1, 1), (1, 2), (1, 2), (1, 2), (1, 2), (2, 1), (2, 1), (2, 1), (2, 1), (2, 2), (2, 2), (2, 2), (2, 2), каждая пара учитывается и никуда не девается, всегда рассматриваются ровно n2 пар чисел.
По-прежнему верно, что первое число – это a[k / n]. А второе число – это a[(k–n·cnt) / num], где cnt – количество чисел в массиве строго меньших, чем a[k / n], а num – количество чисел в массиве, которые равны a[k / n].
В этой формуле несложно убедиться, рассмотрев пару примеров с повторяющимися элементами. В крайнем случае, можно написать тривиальное решение за O(n2· log(n)) и убедиться, что вы правильно придумали формулу.
P. S. Претест 3 имеет вид: в массиве (1, 1, 2) нужно найти 3-ю по лексикографичности пару. Она равна (1, 1).
160D - Ребра в MST
Во-первых, разберем случай, когда все веса одинаковы. Тогда очевидно, что любое ребро может быть в дереве, но в случае, если ребро – мост, то оно является единственным способом соединить две компоненты, а значит, оно принадлежит любому MST. Итак, для мостов ответ равен «any», а для всех остальных – «at least one».
Рассмотрим алгоритм Краскала (или Крускала – кто как привык). В нем в MST пытаются добавляться ребра в порядке возрастания их весов. Но если у двух ребер вес одинаковый, то их порядок добавления может быть любым, а значит, одно ребро может зависить от того, добавилось раньше другое ребро того же веса, или оно добавится позже.
А значит, мы можем решать задачу по слоям: на каждом слое мы рассматриваем одновременно все ребра с данным весом, а сами слои – в порядке возрастания веса.
Построим на каждом слое отдельный граф, причем вершинами будут являться уже сформированные на данный момент компоненты связности, а ребра добавляются между соответствующими компонентами. Если ребро – петля, то значит, что существует способ связать два конца этого ребра за меньшую стоимость, и это ребро никогда нам не нужно, ответ для него – «none».
Если ребро в построенном графе – мост, то по ранее разобранному случаю, ответ для него «any», а для всех остальных – ответ «at least one». При разборе этих случаев нужно быть аккуратным, потому что при сжатии графа появляются мультиребра, ответ для них всегда «at least one», потому что ни одно из повторяющихся ребер не является мостом.
Решение это задачи можно реализовать за время O(n· log(n)).
160E - Автобусы и люди
Для начала, промасштабируем все координаты и времена, а также, так как все ti различны, то запомним для каждого ti номер автобуса, который поедет с этим временем.
Для каждого автобуса создадим событие вида «при координате si появляется автобус, который поедет в момент времени ti и уедет до точки fi». Для каждого человека создадим событие вида «при координате li появляется человек, который поедет в момент времени bi и уедет до точки $r_i$».
Эти события отсортируем в порядке возрастания координаты (si, если это автобус, и li, если это человек) и будем выполнять в этом порядке.
Будем поддерживать структуру данных, в которой для каждого времени ti будем хранить максимальное fi автобуса, который едет в этот момент. Тогда если текущее событие означает автобус, то нужно просто обновить соответствующее значение в структуре данных. А если текущее событие означает человека, который в момент времени bi поедет до остановки ri, то нужно с помощью структуры данных отвечать на запрос «найти в структуре минимальную позицию t, которая не менее bi, а соответствующее ему значение не менее ri», тогда соответствующий этому t номер автобуса и есть ответ.
Вопрос в том, какую структуру данных использовать. Проще всего это делать с помощью дерева отрезков по максимуму, тогда на этот запрос можно отвечать за время O(log(n)), но также можно было использовать и другие структуры данных, например декартово дерево с неявным ключом и др.
Таким образом авторское решение работает за время O((n + m)·log(n + m)).
Существует достаточно простое решение с двумерным деревом отрезков, работающее за O((n + m)·log2(n + m)), но не гарантировалось, что оно уложится в Time Limit.
149A - Business trip
First, it is clear that if the sum of all numbers ai is less than k, then Peter in any case will not be able to grow a flower to the desired height, and you should output «-1».
Secondly, it is easy to see that if we want to choose a one month of two, in which we watered the flower, it is better to choose one where the number of ai is more. Thus, the solution is very simple: let’s take months in descending order of numbers ai and in these months water flowers. As soon as the sum of the accumulated ai becomes greater than or equal to k — should stop the process, the answer is found.
149B - Martian Clock
In this task required only the ability to work with different numeral systems. Let’s try to go through numeral bases, each base to check whether it is permissible, as well as convert hours and minutes to the decimal system and compared with 24 and 60, respectively.
What is maximal base, that we need to check? In fact, it is enough to 60, because 60 — upper limit on the allowable number. It follows from the fact that if the number in an unknown number system consists of one digit, then its value in decimal not ever change, otherwise its value is not less than the base.
It is also worth to consider the case with the response «-1», for this example, you can check a big base, such as 100, and even if the time for him correct, then for all large, it is also correct and the answer is «-1».
149C - Division into Teams
Sort all the boys on playing skill. Then, if we send in the first team all the boys standing in a sorted array for odd places, and the second — even standing on the ground, then all requirements for division executed.
The first two requirements are obviously satisfied.
To prove the third we consider the geometric representation: Let each child designated point on the X axis with a value equal his playing skill. Connect the points with segments numbered 1 and 2, 3 and 4, and so on. If n is odd, then join the last point with the nearest the previous one.
Obviously, all these segments don’t intersect in pairs, except at the points, and their total length is equal to the difference amounts to play boys’ skills contained into the first team and second team. It is also clear that all of these segments completely contained in the interval [0, max(ai)], as well as the pairs are a length of zero crossing, the third requirement is satisfied, which we proved.
149D - Coloring Brackets
We introduce the notation of colors: 0 — black, 1 — red, 2 — blue. Note that a single pair of brackets has 4 different coloring: 0-1, 1-0, 0-2, 2-0.
Consider the dynamic programming, where the state is (l, r, cl, cr), where the pair (l, r) defines a pair of brackets, and cl and cr denote a fixed color for them. The value of the dynamic is a number of ways to paint all the parenthesis brackets inside the interval (l, r) in compliance with all conditions.
We write down all the pairs of brackets that are directly placed into a pair of (l, r), let k of their pieces. Moreover, we consider only the first level of nesting, it is directly attached.
In order to calculate the value of the dynamics for the state, within this state shall calculate the another dynamic, where the state is a pair (i, c) which means the number of correct colorings of the first i directly nested parentheses, and all inside them, if the latter closing bracket has a color c. Calcing the values of this dynamic is very simple, let’s try to paint a (i + 1)-th parenthesis in one of four variants, but you should keep in mind possible conflicts. In such dynamics the initial state is a pair (0, cl), and the final result is sum over the states of the form (k, c), where c must not conflict with the cr.
The answer to the whole problem may be calced as the internal dynamic. Time of solution — O(n2) by a factor of about 12.
149E - Martian Strings
We will solve the problem separately for each m strings. Thus, suppose we have a string p, its length is l, and we need to check whether the Martian be seen.
We introduce additional arrays: let pref[i] is minimal position in the s of the begin of occurrence p with length exactly i, and let suff[j] is the maximum position in the s of the end of occurrence p with length exactly j
It is easy to understand that a Martian could see the p, if there exists an i, that suff[l - i] ≥ pref[i] + l - 1.
How to calculate the arrays? For pref array is sufficient to find Z-function p#s, but for an array of suff — Z-function r(p)#r(s), where r(t) means the reversed string t. Using an array of Z-functions calcing of arrays suff and pref is trivial.
Dear friends!
The next competition - Codeforces Round 101 for participants Div2 will take place through a pair of hours, but the others can traditionally participate out of competition. It has been prepared by a small command of authors: me (NALP), Polina Bondarenko (Polichka) and Gerald Agapov (Gerald). There were Artem Rahov (RAD), Maria Belova (Delinur) and Michael Mirzayanov (MikeMirzayanov) with us as always.
It is a little bit about authors: all of us study at the Saratov State University at faculty of Computer Sciences and Information technology on 4th course. Now in free time from competitions and problems we pass the exams :) I’m a 1/3 part from command Saratov SU#2, and Gerald with Polina - 2/3 from Saratov SU#1. We would like our rounds became kind tradition on Codeforces and you have seen us among authors soon again.
We hope that this problems will be pleasant to all participants and everyone will take the deserved high place in the total table. Today you will help Santa Claus, Elf, Vasya and the other characters. All the similarities to real people are casual :)
The points on problems are distributed today in this way: 500-1000-2000-2000-2500
UPD: You can read the tutorial here.
Registration to SRM 523 is open! See time on your timezone here
Задача А (Div-2). Игрушечные армии
Задача E (Div-1). Две последовательности
Теперь придумаем окончательное решение. В силу постановки нашей задачи, можно задачу свести к другой динамике - D(i, s), где состояние означает, что одна из последовательностей заканчивается на строку номер i, а вторая - на саму строку s, причем, заметим, что под строкой s будем подразумевать не только строки из входных данных, но и все их суффиксы длиной от 0 до l. Вспомним, что строки у нас бинарные длиной не более 20 символов, а это значит, что строки можно закодировать двоичными числами, в этом случае строка кодируется парой - длиной и самим числом (это строка, если ее интерпретировать как двоичную запись; эта тонкость нужна, т.к. в строках, возможно, присутствуют лидирующие нули, в этом случае разные строки будут переводится в одно и то же число), причем, общее количество пар будет не более 221.
Task A. Double Cola
Task B. Sets
Task C. General Mobilization
Task D. Two out of Three
Task E. Corridor
I'm glad to welcome all fans of programming!
The second qualifying round Yandex.Algorithm will take place today, and it was prepared for you by Artem Rakhov, Michael Mirzayanov and me.
Please pay attention that as well as during the previous qualifying round Codeforces's functionality will be a little cut down for the period of the competition. Don't worry, all will return into place after the round termination.
I remind the best 500 participants pass in Yandex. Algorithm 2011 Round 1 which will take place on May, 20th at 19.00
Good luck!
UPD: the contest is over, congratulations to the winner - tourist!
I recall this competition was a qualifying round, and the best 500 will take part in Yandex.Algorithm Round 1!
Today two participants were the most lucky - Hossein_Hima and ss.nurboolean, - they have taken 499-500 places together with result 978 scores.
Задача F. "Умный мальчик"
Эта задача решается методом динамического программирования, где состояние - это текущая записанная на доске строка, а хранимое значение - это тройка
, где result - это результат игры для игрока, который в данный момент ходит (проиграл он, или выиграл), a - это максимальное количество очков у него, и b - минимальное количество очков у соперника. Тогда мы перебираем букву, перебираем куда мы ее поставим, и пытаемся улучшить текущий ответ. Для этого мы используем следующий критерий: наше состояние выигрышное тогда и только тогда, когда существует ход в проигрышное состояние. Из всех ходов, гарантирующих наш выигрыш, вы выберем такое, чтобы наши очки были максимальны, а при равенстве - очки соперника минимальны. Если наше состояние - проигрышное, то выбирать по этому критерию надо вообще из всех переходов.
Количество очков, которое получает игрок при записи новой строки, можно было считать, используя, например, префикс-функцию, но замечу, что решения, которые использовали встроенные в языки функции проверки вхождения одной строки в другую, тоже проходили по времени.
Хранить все состояния было проще всего в структуре данных map (или HashMap, TreeMap и подобные), но вполне адекватным решением было хранить результаты в массиве d[][][], где первое измерение - номер строки из алфавита, второе и третье измерение - начало и конец вхождения текущей строки в эту строку из алфавита.
Задача E. "Ну-ка, покатились!"
Рассмотрим решение с помощью метода динамического программирования.Пусть Di - минимальный штраф, который мы заплатим, если будем решать задачу для шариков с номерами от i до n, причем шарик номер i будет обязательно приколот.
Тогда
где
Если числа S(i, j) не считать каждый раз, а пересчитывать, используя формулу S(i, j) = S(i, j - 1) + xj - xi, то решение требует всего O(n) памяти и O(n2) времени на решение.
Важное замечание: в приведенных рассуждениях, шарики нужно рассматривать в порядке увеличения их координат.
Задача C. "Жалюзи"
Нетрудно понять, что для некоторой фиксированной длины полос жалюзи x, максимальное количество полос, которые можно получить, равно:
тогда переберем это значение x ≥ l, и найдем максимум выражения x· f(x). Это число и надо вывести.
Задача D. "Архитектор Вася"
Эта задача вызвала большие затруднения.В этой задаче достаточно было всего лишь вспомнить физическую статику. Для тех, кто затрудняется припомнить школьную программу, могу порекомендовать Википедию.
Как известно, существует 2 условия равновесия тела (здесь и далее будем считать устойчивое и неустойчивое равновесие неразличимыми, и называть общим словом "равновесие" или "устойчивость", так как в данной задаче нет никакого внешнего воздействия на конструкцию, кроме естесственной силы тяжести и силы взаимодействия кубиков с друг другом), но нам в этой задаче надо будет рассмотреть второй закон равновесия, который мы переформулируем в критерий устойчивости для нашей задачи:
Система кубиков устойчива тогда и только тогда, когда для любой ее точки сумма моментов всех сил, приложенных к этой точке равна нулю. Несложно понять, что это утверждение эквивалентно тому, что система кубиков устойчива тогда и только тогда, когда проекция центра масс этой системы лежит внутри или на границе проекции опоры, на которой расположена эта система кубиков.
Значит, используя этот критерий, будем решать задачу следующим образом: будем в текущую башенку добавлять по одному кубику и проверять, устойчива ли она. Для этого, мы должны проверить, является любой суффикс текущей башенки устойчивым, для этого найдем его центр масс, и проверим критерий. Если он не выполняется, то башенка разрушится, и выведем ее высоту минус один, а если она вся целиком устойчива, то надо вывести число n.
Приведем формулы для координат центра масс некоторых n кубиков:
где:
, 
mi = |xi, 1 - xi, 2|3 = |yi, 1 - yi, 2|3
Задача G. "Очередь"
Данная задача имеет несколько возможных решений, но я расскажу 2 возможных подхода:1. Декартово дерево (дуча, treap или дерамида)
Будем считать, что читатели знакомы с этой структурой (если это не так, то советую почитать тут). Самое простой по логике подход использует неявное декартово дерево, и этот алгоритм действует так: будем добавлять людей по очереди, в порядке их прихода. В вершине дерева, кроме служебной информации, будем поддерживать число maxValue, равное максимальному значению из чисел ai в этом дереве.Бинарным поиском переберем возможную позицию нового человека, пусть он имеет номер k, pos от 0 до ck (для удобства нумерацию введем с конца очереди). Человек достигнет этой позиции тогда и только тогда, когда среди чисел ai, 0 ≤ i < pos не существует ни одного, большего числа ak. Это можно проверить, отщепив от декартова дерева поддерево размера pos, и проверив у него число maxValue. Таким образом мы найдем значение pos, и в эту позицию вставим нового человека. Построив полную очередь, нужно вывести ответ. Но это очень простая операция, не будем ее обсуждать. Асимптотика такого решения
. Замечу, что это решения является неоптимальным, и вполне возможно, что оно не всегда пройдет по времени, поэтому модифицируем его:избавимся от бинарного поиска. Для этого можно сразу отщепить от дерева поддерево размера ck с начала дерева, и найти в нем такую максимальную позицию pos, что все числа ai (0 ≤ i < pos) меньше ak. Это делается с помощью одного обхода вниз по дереву, где на каждой вершине мы смотрим, надо ли закончить спуск, или надо выбрать одного из сыновей и продолжить. В процессе такого пути накапливаем количество вершин, оставляемых слева от текущей. Потом вставляем нового человека в найденную позицию, и восстанавливаем дерево обратно. Подумайте сами, как это реализовать, это не очень сложно. Асимптотика нового решения уже составляет
. 2. Использование метода 
-декомпозиции.
Пусть 
. Тогда мы заведем s двусвязных списков, которые и будут представлять очередь, только разбитую на части. Так же, как и в предыдущем решении, будем добавлять по одному человеку в очередь в порядке их прихода.Будем хранить для каждого списка также число maxValue, равное максимальному значению из чисел ai в этом списке. Тогда добавление происходит так: будем искать подходящее место для нового человека, для этого пропустим все списки, суммарной длиной, меньшей ck, причем во всех этих списках числа maxValue должны быть меньше, чем ak. Если мы возьмем первый такой список, где это условие не выполняется, или ck стало меньше, чем длина пропущенных список плюс длина текущего, то мы по такому списку пробежимся "в лоб", то есть по каждому элементу от начала до конца, проверим выполнение условий, и добавим нового человека на найденное место.
Давайте оценим, сколько времени требует текущее решение. В худшем случае, оно будем всех людей добавлять в один и тот же список, и при добавлении нового "в лоб" пробегаться от его начала до конца, таким образом в неудачном случае, время работы составит O(n2), что нам не очень годится.
Тогда применим следующую хитрость: в момент, когда какой-либо список станет больше, чем 2 * s элементов, то сделаем перераспределение людей в очереди. Из списков, которые содержат более s элементов, будем проталкивать их в следующую очередь. Таким образом мы нормируем списки, и они станут достаточно короткие - всего не более s элементов в каждом.
Оценим время работы в новом случае. Теперь добавление нового человека требует
времени. Нормализация требует O(n) времени, но выполняется она не чаще, чем раз в операций добавления, что в сумме даст 
операций.Значит, наше решение работает за
.Задача B. "Ладья, Конь... и снова Конь"
Данная задача так же, как и задача А, не должна была вызвать затруднения. В силу очень небольших ограничений и простой модели, можно было перебрать позицию, куда мы поставим, нового коня, и аккуратно проверить все условия в формулировке задачи.
Задача А. "Армия"
Эта задача была утешительной и самой простой на этом контесте. Ответ считается по формуле:
Никаких "подводных камней" и хитростей эта задача не содержит.
I would like to invite you to participate in a new competition, that will be held on the 30th of October at 16:00 MSK. It will be a part of the series of winter programming school olympiads, but it will be only a standart Codeforces round for adult participants.
Teams aren't invited, only single members. The official rules will be ACM-ICPC.
Jury has decided to increase the duration of the competition, which will be 4 hours long.
Attention: People, who are considered out of competition, are participants of Codeforces Round #38, others are participants of School Personal Contest #1. But we will use merged result table for updating rating.
The authors are me, Mike Mirzayanov and Artem Rakhov. Also I'm expressing gratitude to Maria Belova, Max Ivanov and Natalia Bondarenko for help.
P.S. Please, don't forget to register to the competition!
A. Extra-terrestrial Intelligence
This task is very easy, and I hope all of you have solved it. But let's talk about it.Let input sequence is named as a, and its length is n. Then let's save sequence x1, ..., xk is increasing order - all of positions, where axi = '1'.
We must check if this sequence x1, ..., xk is a arithmetic progression. We save variable d = x2 - x1 and check:
for all 1 ≤ i < k, is "d = xi + 1 - xi" correct.
If it's correct, output "YES", else "NO".
Разбор задачи "C. Тир"
Во-первых, нужно сказать, что в данной задаче элементы теории вероятностей не играют существенной роли. То есть можно считать, что у i-ой мишени всего лишь есть некоторый "вес", который равен как раз вероятности попадания в нее, а именно pi. Достаточно просто понять, почему это так:
Математическое ожидание количества попадания в i-ую мишень равно Mi = 0 * (1 - pi) + 1 * pi = pi, а математическое ожидание попадания в несколько мишеней по очереди равно сумме математических ожиданий, а значит, по уже сказанному, равно сумме вероятностей попадания в эти мишени.
Поэтому нами (авторами этой задачи) предлагается решение динамическим программированием, а именно:
Di равно максимальному математическому ожиданию попаданий, если у нас на данный момент прицел направлен в мишень номер i, причем, текущее время (которое, однако, не является параметром и явно нигде не учитывается) меньше или равно ti.
Тогда Di = pi + max(Dj), где j-ая мишень обозначает следующую мишешь, куда мы переместим прицел. Соответственно, для нее должно выполняться условие: ti + dist(i, j) ≤ tj, для того, чтобы такой переход имел место быть. Очевидно, что граф переходов ацикличен, а это значит, что такое решение верно.
Ответом является максимальное Di по всем 1 ≤ i ≤ n. Асимптотика данного решение O(n2).
и вообще, расскажи, пожалуйста, что это и с чем едят =)
UPD: в раунде 1 даже не обратил внимания на эту штуку, потому что не до того было
"tco 2010"
Authors of today's contest are Artem Rakhov and me. Thanks to Mike Mirzayanov, Edvard Davtyan and Julia Satushina for help in the organisation.
I hope, you will have fun.
Good luck!
P.S. After start of the contest, you can download the statements:
UPD. The contest has finished and you can see the standings and tasks. The winner and only participant who has solved all the problems is kalinov. Congratulations!
Интересно, а как вычисляется вклад (см. пару сантиметров правее на табличку)? что он означает по своей сути? Вот у меня вклад = +5... откуда? 0_о
Также пожелание - сделать или RSS, или просто табличку прямого эфира поболее, а то можно не успеть за последними новостями и сообщениями ;-)
Замечу, что интересно взглянуть на первый контест на данном ресурсе, потому что и правила, и время соревнований, и все ньюансы - пока покрыты мглой =) ждем-с
UPD: фича: иногда бросает в разные языки. специально повторить не сумел, но пару раз ловил такой момент.
UPD2: хотелось бы, что бы в полной табличке лидеров http://codeforces.ru/top-contributed были не имена пользователей, а ссылки на профили - например, чтобы проще у них читать блог