Hi everybody,

As you've probably already guessed, I am looking for teammates for Deadline 24. I have no experience in participating in such kind of contests, but I've taken part in algorithmic competitions since 2009. I speak Ukrainian, Russian and English. We may communicate via Skype/Hangouts/etc during the qualification round.

So if you are interested — do not hesitate to PM me.

Hi everybody,

It's been exactly a year since MemSQL Start[c]UP 2.0 — Round 2, but I still have not received my T-shirt. Am I the only one with this problem?

Наконец-то обьявлены даты алгоритмической части TopCoder Open 2015. В этом году организаторы решили сделать несколько изменений, среди которых я заметил такие

1) Никакой специальной регистрации на TCO.

2) Соответственно, 250 людей, которым не надо писать первый, раунд определяются среди всех активных участников (написавших хотя бы 1 матч в 2015 году и хотя бы 3 всего)

3) Обьявлены региональные онсайт этапы, которые совпадут со вторым раундом. Вторых раундов теперь 4 а не 3.

4) Не нашел никакой информации про футболочки :(

5) Будет всего лишь 12 финалистов; правила проведения онсайт-раунда также изменены (спасибо ffao и cgy4ever за дополнение)

Ссылка на правила

Никогда ранее не писавшим — советую поучаствовать, соревнование обычно крутое

GL&HF!

Let's discuss problems here.

Here is very-very short explanation of my solutions.

Die Hard 3

Use dfs/bfs on a graph, where vertice is represented by a pair of integers, each of which denotes the amount of water in a jug.

Chocolate in Box

This problem requires very basic knowledge about game theory and nim game. It is also important to notice, that we can do exactly 0 or 1 optimal moves in one heap.

String Function Calculation

Let's build suffix array and calculate LCP array. Now we can calculate maximum of occurrences of a substring with some fixed length using some sets/multisets

Savita And Friends

Have no idea how to solve this problem. I tried ternary search, but obviously it won't give the correct answer. I'll be very grateful if someone posts his solution to this problem

The crazy helix

One can use treap to answer all the queries. However, i used treap to answer the queries of type 1 and 2. For the third type of query I used sqrt-decomposition on the queries.

Всем привет.

В субботу в Виннице и Бухаресте завершился SEERC 2013. Я участвовал в винницкой части контеста и постараюсь рассказать сообществу об этом событии с точки зрения участника. Так как я живу в Виннице, то про особенности быта, к сожалению, рассказать ничего не смогу. Возможно, это сделают другие участники в комментариях.

И так, контест официально начался в пятницу. На регистрации участников, кроме, собственно говоря, организаторов олимпиады, ожидали также стенды Яндекс, Facebook и SysIQ (это более-менее известная в Украине фирма, офис которой есть в Виннице). Отдельное спасибо Яндексу, который порадовал прикольными сувенирами с надписью «Яндекс. Наш лось» и, соответственно, рисунками лося :)

Далее была довольно стандартная церемония открытия, единственной изюминкой которой стал переводчик, переводивший для гостей из Турции и Молдовы вовсе не то, что должен был переводить :)

Вдохновившись бодрым примером команды Samara SAU Teddy Bears, мы решили выиграть пробный тур. Задачки на пробном были стандартные для SEERC. Более того, кодить их можно было до старта контеста. Несмотря на то, что в 4-ой задаче я сделал две ошибки (одну в понимании условия, вторую – в коде), мы все сдали с плюса и выиграли пробный тур :)

На вечер были запланированы технические семинары от Яндекса и Facebook. Michael в презентации от Яндекса рассказал о том, как они зарабатывают на рекламе, а Остап Коркуна из Facebook рассказал про новую фейсбуковскую фичу — Facebook Graph Search. Было довольно-таки интересно, к тому же рассказы на отвлеченные темы помогли убрать волнение накануне контеста.

А на следующий день был контест. Комплект задач разыгрывался на воскресном этапе Открытого Кубка, поэтому, полагаю, все знакомы с условиями. Я расскажу, как это проблемсет решала моя команда (VNTU [wRabbits]) На старте OutSide дал мне задачу I, сказав, что это простая динамику по DAG-у. В процессе написания я осознал, что не все так просто и отдал компьютер Igel_SK, который сел писать задачу G. Сабмит – ВА. Я читаю задачу J и решаю проверить сабмитом очевидную гипотезу. Аксепт! Вот и наш первый шарик за решенную задачу. Igel_SK находит баги в G, исправляет их и приносит нашей команде второй ОК. Хух, уже чуть лучше. Возвращаемся к задаче I. Внезапно, я слышу возглас озарения от OutSide, который говорит, что к тупому решению по ней надо докрутить битсет и все будет хорошо. И действительно, на 1:22 мы получаем третий ОК. Смотрим на монитор – сдают задачу C. С алгоритмической точки зрения она совсем простая, нужно только научиться считывать из бинарного файла. Через некоторое время Igel_SK научился это делать, я дописал алгоритмическую часть и мы сдали задачу. С этого момента начинается наш затуп длиной 2 часа и 14 минут за который мы не сдали ничего. Сналача Igel_SK придумал как решать А максимальным потоком минимальной стоимости. Пишем, отсылаем, тайм лимит эксидед. Меняем Беллмана-Форда на Левита (вдруг авторы не знают контртеста) – все еще TL. Igel_SK добавляет какую-то эвристику – программа начинает летать на макстесте, но WA. В это время я и OutSide думаем про задачу B. Придумываем, как ее решить. Я пишу решение – WA. Да что ж такое. Печатаю код, ищу баги. Igel_SK пишет жадность на А и сам же придумывает к ней контртест. Я перечитываю условие по В – да нет, все я правильно в нем понял. В конце-концов я понимаю, что допустил идейный баг, исправляю – АС. Igel_SK пишет еще одну жадность на А. Сабмит. АС! Я начал было радоваться, но мои сокомандники говорят, что у многих команд до заморозки было 7, у нас же пока что 6. Мы начинаем засылать всякий бред по задаче H, пытаясь найти закономерность и с 5-ой попытки таки верно угадываем ее. Ну что же, у нас тоже 7. В лучшем случае мы на 7-м месте. До конца контеста 38 минут. Мы начинаем писать задачу Е, хотя особой уверенности в решении нет. Мы дошли до диофантового уравнения, Igel_SK сказал, что корни должны быть взаимнопростыми, однако верное решение мы так и не придумали. Контест закончился.

Разморозка показала, что победила команда Sobolev Team, сдав победную 9-ую задачу за 2 минуты до конца. На втором месте BZFlags, на третьем – Phantom Menace. Мы же закончили 7-ыми (6-ыми по украинскому сайту). Награждались все команды, решившие 7 и более задач, а топ 6 команд, писавших в Виннице получили медальки и кубки – они стали призерами параллельно проходившего открытого чемпионата Украины. Также какие-то призы получили иностранные команды – просто за то, что они иностранные :)

Стоит отметить, что закрытие происходило в одном из винницких ресторанчиков, где, помимо награждения, также прошли лотереи от спонсоров и, наверное что-нибудь еще, однако про это я рассказать, к сожалению не могу, так как ушел с закрытия довольно рано.

Вот таким вот был этот SEERC. Спасибо читающим это друзьям за поддержку, авторам — за задачи, волонтерам и организорам — за организацию. Мы впервые стали призерами чемпионата Украины, однако на финал не прошли. Впрочем, попытки еще есть, так что все впереди, надеюсь.

Ссылка на результаты

Ссылки на фотографии на сайте ВНТУ с его кривой фотогалереей: 1 2

UPD Мы в финале!

Здравствуйте.

Добавил в тренировки контест, который проводился в моем университете в октябре 2012 года и считался вступительным в сезон тренировок.

Авторы задач — OutSide, Igel_SK, Sammax и я.

Внимание! Тренировка делалась с учетом того, что ее будут писать люди, уровень которых сопоставим с уровнем второго дивизиона. Участники первого дивизиона вряд ли найдут там что-то интересное.

По возникшим вопросам просьба отписываться здесь в комментах или мне в личку.

A. Проблемные обеды

Для нахожения ответа переберем все возможные рестораны, в которых могли пообедать три Кролика. Посчитаем ответ для каждого ресторана. Из всех ответов выберем максимальный. Ответ для ресторана i считается по формуле, описанной в условии. Сложность решения O(N).

Код на С++

Код на Java

B. Девочка и игра

Посчитаем количество букв, которые встречаются в строке s нечетное количество раз. Пусть это количество равно k.

Заметим, что если k = 0, то первый игрок сразу же побеждает — он легко может составить палиндром, поставив одинаковые буквы в разные концы строки (так как общее количество всех букв четное, он сможет это сделать).

В случае k = 1 первый игрок опять-таки сразу же побеждает — сначала он строит палиндром из букв, которые встречаются четное количество раз, а потом вставляет в середину полученной строки те символы, количество вхождений которых в строку s нечетно. Утверждается, при k > 1 задача имеет следующее решение: если k четное – победил второй игрок, иначе победил первый игрок.

Докажем это утверждение. Пусть k = 2. Первый игрок своим ходом может сделать ходы двух типов. Ход первого типа состоит в том, чтобы уменьшить k до 1, удалив одно вхождение буквы, которая встречалась нечетное количество раз. Однако такой ход ведет к поражению, ведь после него второй игрок может составить палиндром.

Ход второго типа состоит в том, чтобы удалить букву, которая встречается четное количество раз, таким образом увеличив k до 3. В таком случае, второй игрок может ответить аналогичным ходом, удалив такую же букву. Так как количество ходов этого типа конечно, то рано или поздно первый игрок вынужден будет сделать ход первого типа, а значит — перейти в проигрышную для себя позицию.

В случае k = 3 первый игрок первым же ходом может уменьшить k до 2, убрав букву, встречающуюся нечетное количество раз. Если второй игрок попробует увеличить k до 3, то первый игрок аналогичным ходом сможет опять уменьшить k до 2. Легко увидеть, что последним в этой цепочке ходов будет ход первого игрока, а значит – он переводит игру в состояние с k = 2, которое является выигрышным для него и проигрышным для его соперника. Аналогичными размышлениями, применяя математическую индукцию, утверждение доказывается для произвольного k.

Получается достаточно простое решение за О(|S|)

Код на С++

Код на Java

C. Девочка и максимальная сумма

Для каждой ячейки массива посчитаем количество запросов, которые ее покрывают. Утверждается, что ячейке, которую покрывает большее количество запросов, нужно ставить в соответствие большее число. Более формально: пусть b — массив, в i-ой ячейке которого записано количество запросов, покрывающих эту ячейку, а – входной массив. Отсортируем эти массивы. Утверждается, что ответ в таком случае равен

Докажем это утверждение. Рассмотрим какие-то индексы i < j, а так же соответсвующие им элементы a[i], a[j] , b[i], b[j] (a[i] ≤ a[j], b[i] ≤ b[j]). Эти элементы вносят в ответ следующую величину: a[i]·b[i] + a[j]·b[j]. Поменяем элементы a[i] и a$[j]$ местами. Теперь эти элементы вносят в ответ величину a[i]·b[j] + a[j]·b[i]. Рассмотрим разницу между полученными значениями:

a[i]·b[j] + a[j]·b[i] - a[i]·b[i] - a[j]·b[j] = b[j]·(a[i] - a[j]) + b[i]·(a[j] - a[i]) = (b[j] - b[i])·(a[i] - a[j]) ≤ 0.

Таким образом, перестановка двух любых элементов приводит к неувеличению суммарного результата, а значит — начальный порядок является оптимальным.

Теперь нам нужно быстро научиться считать массив b.

Для этого можно использовать разные структуры данных, поддерживающие модификацию на отрезке (дерево отрезков, декартово дерево и т.д). Однако, существует гораздо более простой метод.

Создадим некоторый массив d. При поступлении запроса l_i, r_i увеличим элементы массива d[l_i] на 1, и уменьшим значение элемента d[r_i + 1] на 1. Таким хитрым образом мы добавляем 1 всем ячейкам от l_i до r_i включительно. После этого необходимо пробежаться по массиву d, накапливая соответствующий результат для b[i].

Теперь, зная массив b, можно легко узнать ответ. Сложность авторского решения — O(NlogN + Q)

Код на С++

Код на Java

D. Девочка и максимальный XOR

Честно говоря, удивлен тем, что с задачей справилось так много участников. Я предполагал решение использующее динамическое программирование, его и опишу.

Для начала, переведем числа L и R в двоичную систему счисления. Теперь заведем такую динамику: d[p][fl1][fr1][fl2][fr2], где p – текущая позиция в двоичной записи чисел a и b (от 0 до количества бит в числе R), fl (от 0 до 1) — переменная, показывающая, что набранное число а строго больше L, fr1 (от 0 до 1) — переменная, показывающая, что набранное число а строго меньше R, fl2, fr2 — переменные, означающие аналогичное значение для числа b.

Напишем динамику в виде рекурсии с запоминанием.

Определим базу рекурсии. Если мы рассмотрели все биты — просто вернем 0.

Определим рекурсивный переход. Узнаем, какой бит может стоять у числа а на позиции p. Мы можем поставить там 0 при одном из двух условий: или у числа L на этой позиции стоит 0, или у числа L на этой позиции стоит 1, а переменная fl1 показывает, что когда-то был выбран бит, который больше соответствующего бита в числе L. Аналогично, мы можем использовать там 1 при одном из двух условий: или у числа R на этой позиции стоит 1, или у числа R на этой позиции стоит 0, а переменная fr1 показывает, что когда-то был выбран бит, который меньше соответствующего бита в числе R. Аналогично, можно узнать, какие биты мы можем ставить в число b. Переберем все возможные варианты расстановки бит, и если результат операции xor в этом бите равен 1, то добавим к ответу для данной расстановки соответствующую степень двойки. Так же необходимо аккуратно пересчитать значения переменных fl1, fr1, fl2, fr2. Среди всех возможных вариантов расстановки надо выбрать максимум.

Запускать рекурсию необходимо от параметров (P,0,0,0,0), где P — количество бит в числе R.

Надеюсь, мой код прояснит все непонятные моменты.

Стоит так же заметить, что подобный подход является в некотором смысле универсальнм и может быть применен для многих похожих задач, например, для вот этой

Сложность алгоритма O(logR)

Код на С++

Код на Java

Благодря комментариям я узнал еще одно замечательное решение, которое тоже решил включить в разбор.

Отдельно рассмотрим случай, когда L = R. Ответ в таком случае, очевидно, равен 0.

Теперь пускай L ≠ R. Пусть R_i — i-ый бит числа R, L_i — i-ый бит числа L. Пускай p — наибольшее число такое, что R_p ≠ L_p (индексируем p c 0). Рассмотрим произвольное число в отрезке [L;R]. Легко видеть, что биты, старшие чем бит с индексом p у всех этих чисел одинаковы. А значит, как бы мы не выбирали числа a и b, эти биты ничего не внесут в ответ, ведь их xor равен 0.

Теперь давайте построим числа a и b таким образом:

1) Число a — биты, старшие чем бит с индексом p совпадают с битами числа L, p-ый бит равен 0, остальные биты равны 1.

2) Число b — биты, старшие чем бит с индексом p совпадают с битами числа L, p-ый бит равен 1, остальные биты равны 0.

Легко увидеть, что оба эти числа лежат в промежутке [L;R], а также что их xor превращает в 1 все двоичные розряды, не старшие чем p-ый, то есть ответ при таком выборе максимизируется, и равен 2^p + 1 - 1

Сложность алгоритма O(logR)

Решение на Java от AlexanderBolshakov

Если подбирать значение p бинарным поиском, то можно улучшить время работы алгоритма до O(log(logR)), однако на контесте этого делать, естественно, не требовалось.

E. Девочка и задача про дерево

Заметим, что наше дерево – это совокупность некоторых цепочек, начинающихся в корне.

Для начала при помощи поиска в глубину разобьем наше дерево на цепочки. Для каждой вершины узнаем ее глубину, а также номер дерева, в которому она принадлежит. Заведем для каждой цепочки некоторую структуру данных, которая умеет быстро изменять элемент, а также быстро находить сумму на некотором отрезке. Для этих целей, например, идеально подходит дерево Фенвика. Также заведем дерево Фенвика для запросов, затрагивающих корень. Дерево, заведенное для корня в некотором смысле является глобальным — значения, которые в нем присутствуют, актуальны для всех цепочек.

Теперь вспомним задачу С. Там для модификации на отрезке мы использовали массив d, в котором обрабатывали все запросы. Узнавать значения b[i] в той задаче нужно было после поступления всех запросов. Здесь же запросы изменения и запросы на вывод значения, записанного в вершине, выполняются в некотором смысле онлайн. Именно поэтому стоит использовать дерево Фенвика — оно позволяет за cложность O(logN) изменять элемент, и за такую же сложность находить сумму на некотором отрезке. Научимся с помощью дерева Фенвика обрабатывать запросы на добавление на отрезке массива, а так же на нахождение элемента массива. Как уже говорилось, наше дерево умеет выполнять два типа операций:

add(x, y) — добавляет элементу с индексом x значение y

find(x) – находит значение суммы на отрезке от 1 до x

Предположим что поступил запрос на добавление на отрезке l до r значения val.

Тогда просто выполним операции add(l, val) и add(r + 1,  - val).

Пусть поступил запрос на нахождения значения элемента с индексом v.

Тогда выполним операцию find(v).

Теперь мы можем вернуться к изначальной задаче.

При обработке запроса типа 0 посмотрим, затронет ли он корень. Если запрос затрагивает корень — следует аккуратно обработать запрос в нашей цепочке, а также сделать соответствующие изменения в дереве Фенвика для корня. Иначе просто обрабатываем запрос в цепочке.

При обработке запроса типа 1 просто найдем соответсвующие суммы в дереве Фенвика для корня, а так же в дереве Фенвика для соответствующей цепочки и просуммируем их.

Сложность полученного алгоритма — O(N + QlogN)

Код на C++

Код на Java

На этом все. Вопросы в комментариях очень приветсвуются.

Предлагаю здесь обсудить задачи раунда. Интересует, как решалась задача А.

Всем привет!

Мне нужна помощь по такому вопросу. Я бы хотел найти сервер, на котором есть контесты для проведения личных тренировок. Желательно, чтобы длина контестов была примерно 2-3 часа, а сложность была сопоставима с CodeForces Div1 раундами. Интересуют именно готовые проблемсеты. Возможно, вы знаете что-нибудь такое? Буду рад любой помощи.

Здравствуйте!

У меня два вопроса:

1) Кто-нибудь в Украине уже получил футболки Google Code Jam 2011?

2) Куда можно написать по поводу того, что футболка долго не приходит?

Заранее спасибо.

UPD. Только что пришло письмо из техподдержки. "We are working on distributing the shirts within Ukraine. We should have them out shortly." Так что ждем, надеемся и верим :)

На далеком-далеком острове жили два типа людей: голубоглазые и черноглазые. Стоит заметить, что все они были идеально умные. Также жители острова не могли передавать кому-либо какую-то информацию(то есть они были немые, не умели общаться на языке жестов и т.д.)  Существовало у туземцев такое правило: если житель острова узнает цвет своих глаз, он идет к высокому обрыву, прыгает оттуда и разбивается насмерть. Сброситься со скалы туземец может каждый день ровно в 17-00. Для того, чтобы узнать свой цвет глаз, туземец не может смотреть в воду, зеркало и т.д.

Всё у жителей острова было хорошо до тех пор, пока к ним не приехал иностранец. Он пожил на острове несколько месяцев. И вот, настало время ему уезжать. Иностранец сел в лодку, и перед тем, как отправиться в далекий путь, сказал лишь одну фразу:"Как здорово, что я увидел человека, такого же голубоглазого, как я". Лодка иностранца тут же покинула пределы острова. Опишите, что произошло на острове после отъезда иностранца.

З.Ы. Правильное решение задачи я пока-что не придумал.

З.З.Ы Огромное спасибо пользователю SkidanovAlex за корректировку условия и детальный разбор задачи.

Всем доброго времени суток!

Так как это моя первая запись в блоге, прежде всего хочется поблагодарить создателей Codeforces за отменную работу!

А теперь, собственно говоря, по теме. Контесты USACO писал в на этих выходных впервые. Так вот, меня немного удивила финальная таблица турнира(http://ace.delos.com/MAR10results). Как видим, таблица всех дивизионов поделена на две части. Обе части начинаются с наивысших результатов и заканчиваются наинизшими. То есть, после самого плохого результата первой части резко следует самый хороший результат второй части. Подскажите пожалуйста, чем это вызвано?  И еще: что означает в таблице таинственная колонка GRAD?