Всем привет!
Я добавил в Тренировки два контеста из летних сборов в Петрозаводске 2010 и 2011 годов.
Первый контест готовили студенты Киевского национального университета: Владислав Симоненко, Роман Ризванов и я (Ярослав Твердохлеб). Второй контест совместно готовили студенты Киевского и Харьковского национальных университетов: Андрей Коротков (КНУ), Степан Паламарчук (КНУ), Владислав Симоненко (КНУ), Дмитрий Соболев (ХНУ), Евгений Соболев (ХНУ) и я (Ярослав Твердохлеб — КНУ).
Надеюсь, контесты вам понравятся. Удачи!
Представляю разбор задач Codeforces Beta Round #97. Если есть какие-то вопросы или пожелания --- пишите в комментариях.
136A - Подарки (A Div 2)
В этой задаче нужно было просто считать перестановку и вывести обратную к ней. Для этого просто при считывании i-го по счету числа, которое равно a поместим i в ячейку массива с номером a. После этого выведем полученный массив.
Сложность решения O(N).
Всем привет!
В пятницу, 9 декабря в 19:00 MSK состоится Codeforces Beta Round #97, автором которого являюсь я. Это мой второй полноценный раунд на Codeforces и надеюсь, что не последний :)
Спасибо maksay, Shtrix, it4.kp, RAD и Delinur за помощь в подготовке раунда, тестировании задач и переводе условий.
Удачи на раунде!
UPD: По техническим причинам раунд переносится на 5 минут вперед.
UPD 2: По причине большого числа участников и большого количества тестов, результаты появятся не скоро.
UPD 3: Тестирование завершено, результаты известны. Всем спасибо за участие! Приношу свои извинения за настолько длительное тестирование.
Победители:
Div 1
1. Romka
2. vepifanov
3.
4. Shef
6. shangjingbo
7. ania
8. Ra16bit
9. NALP
10. enot.1.10
Div 2
UPD 4: Опубликован разбор.
Завтра (01.05.2011) состоится личный этап кубка Векуа. На snarknews.info сказано, что он будет проходить по системе TCM/Time. Может кто-то знает, это то же самое что и TCM/SE или же что-то новое?
UPD: правила есть на сайте кубка Векуа.
Теперь разбор завершен.
Задача A: Подарок (Роман Едемский)
Предположим, что оптимальным решением является пара (A, B), где A - количество золотых монет в подарке, а B - количество серебряных монет. Нетрудно заметить, что существуют такие 2 индекса i и j (возможно совпадающих), что gi = A и sj = B, так как в противном случае мы бы могли уменьшить A или B, не нарушив связность графа.
Обозначим через R(A,B) граф, в котором для всех i выполняется gi ≤ A и si ≤ B.
Обозначим через T(A) взвешенный граф, в котором для всех ребер выполняется ограничение gi ≤ A, а весами ребер будут si. Найдем в этом графе остовное дерево, у которого максимальное ребро - минимальное возможное. Можно показать, что для данного фиксированного A наименьшим значением B, при котором граф R(A, B) все еще связный, как раз будет это значение максимального ребра.
Утверждение. Минимальный остов графа одновременно является остовом, у которого максимальное ребро - минимальное возможное.
Доказательство. Рассмотрим любой минимальный остов L. Если существует остов P, у которого все ребра имеют строго меньший вес, чем вес максимального ребра у L. Тогда мы могли бы удалить из L макс. ребро и заменить его каким-то ребром из P, тем самым уменьшив его вес. Поскольку L - минимальный остов, мы не можем уменьшить его вес, следовательно такого P не существует.
Отсортируем все ребра исходного графа по возрастанию gi. Переберем все возможные значения A среди gi. Тогда ребрами графа T(A) для фиксированного i будут все ребра с индексами j ≤ i. Осталось научиться быстро находить мин. остов в этом графе.
Предположим, что мы для какого-то i нашли мин. остов в графе T(gi) (в случае, если граф несвязный, то в каждой его компоненте связности найден мин. остов). Добавим в него i + 1-е ребро. Если это ребро соединяет разные компоненты связности, просто добавим его, в противном случае в дереве образуется ровно один цикл. Найдем в нем максимальное ребро и удалим его из графа, получив таким образом новый минимальный остов в компоненте, куда добавилось ребро (доказательство опускается).
Поиск максимального ребра в цикле на дереве можно осуществить за O(N), а весь алгоритм будет работать за O(NM + MlogM).
Задача B: Мыши и сыр (Роман Ризванов)
Легко заметить, что количество ближайших кусков сыра для каждой мыши не превышает 2.
Найдем для каждой мыши ближайший сыр слева и справа. Из двух направлений выберем то, которое дает более короткий путь или оба, если длины путей одинаковы. Если на выбранном пути между мышью и сыром есть другая мышь, то мы это направление изымаем из рассмотрения, так как другая мышь быстрее съест тот сыр. Теперь все направления мышей непосредственно ведут к сыру и к каждому куску сыра ведет не более одного направления с каждой стороны.
Будем обрабатывать мышей слева направо. Если очередная мышь может двигаться влево и сыр слева не выбрала никакая из уже рассмотреных мышей или этот сыр выбрала мышь с таким же расстоянием до сыра, то текущая мышь двигаясь влево успеет поесть сыр, не мешая остальным мышам. Так как к сыру ведет не более одного направления, то этот выбор не повлияет на следующих мышей, а поэтому и не может в дальнейшем ухудшить ответ. В остальных случаях, двигаясь влево мы не сможем улучшить ответ, поэтому если мышь может двигаться вправо, то это единственная возможность для этой мыши поесть сыра, поэтому она выбирает движение вправо. Если мышь не может двигаться вправо, то она никак не сможит улучшить ответ.
Сложность решения O(N + M).
Также существует решение этой задачи при помощи динамического программирования.
Задача C: Мутация (Ярослав Твердохлеб)
В разборе вместо терминов "риск", "геном" и "ген" будут использоваться термины "стоимость", "строка" и "символ". Обозначим начальную строку через S.
Обозначим через M битовую маску символов, которые будут удалены. Переберем все возможные M. Для фиксированного M найдем стоимость строки, которая получилась и если она не превышает T - увеличим ответ на 1. Реализация этого алгоритма "в лоб" работает за O(2KN).
Избавиться от перебора нам не удастся, поэтому будем улучшать нахождение стоимости строки для фиксированного M.
Рассмотрим некоторую пару индексов символов из начальной строки l и r. Обозначим через M' битовую маску всех символов, которые лежат строго между ними. Если 
или 
, то, очевидно, эти позиции рядом никогда не будут. Отсюда можно сделать вывод, что для фиксированного l возможных положений для r может быть не больше, чем K. Значит, всего таких пар O(NK). Определим, какой вид должно иметь множество M, чтобы после его удаления эти позиции оказались рядом? Нетрудно заметить, что для этого должны выполняться такие 2 условия:
или , то, очевидно, эти позиции рядом никогда не будут. Отсюда можно сделать вывод, что для фиксированного l возможных положений для r может быть не больше, чем K. Значит, всего таких пар O(NK). Определим, какой вид должно иметь множество M, чтобы после его удаления эти позиции оказались рядом? Нетрудно заметить, что для этого должны выполняться такие 2 условия:1. 
2. 
Переберем все допустимые пары l и r, для каждой найдем M'. Попутно для каждой тройки (a,b,P) будем хранить сумму стоимостей соседства всех пар l и r, для которых Sl = a, Sr = b, M' = P. После этого для фиксированного M переберем все пары символов (a, b), а так же подмножества P и просуммируем стоимости, которые мы сохранили. Прибавим к этому стоимость выбрасывания символов из M и получим конечную стоимость строки. Сложность решения O(3K * K2 + NK).
Попробуем улучшить предыдущее решение, засчет уменьшения множителя при 3K. Рассмотрим такой (неправильный) алгоритм:
Переберем все допустимые пары l и r и для каждой найдем M'. Заведем массив v, в котором для каждой маски P будем хранить сумму стоимостей соседства для всех пар l и r, для которых M' = P. Для фиксированного M найдем сумму значений из v по всем подмаскам M, прибавим к ней стоимость удаления M и получим конечную стоимость строки.
Этот алгоритм не является правильным, так как некоторые стоимости соседства мы прибавим к суммарной стоимости, но на самом деле позиции не будут соседями, т.к. один из концов (или оба сразу) будут принадлежать M, т.е. будут удалены. Воспользуемся формулой включения-исключения и при заполнении массива v сделаем следующие действия:
v[M'] + = cost
При таком заполнении v описанный выше алгоритм будет работать правильно и сложность станет O(3K + NK).
Этого все еще недостаточно, но мы уже почти у цели. Осталось научиться быстро считать сумму в массиве v по всем подмаскам M. Для этого рассмотрим следующий итеративный алгоритм:
Пусть перед первой итерацией у нас есть массив v, в котором хранятся начальные значения. После итерации с номером i в v[mask] будет храниться сумма значений из изначального массива v по всем подмаскам mask, для которых первые K - i бит совпадают с соответствующими битами маски mask. На итерации с номером i для всех масок, в которых i-й бит (нумерация с единицы) единичный сделаем сделаем такое: v[mask] + = v[mask\{i}]. Нетрудно заметить, что после выполнения K итераций этого алгоритма в новом массиве v как раз и будут находиться суммы по всем подмаскам из изначального массива v.
Сложность алгоритма O(2KK + NK).
Задача D: Плюс и XOR (Даниил Нейтер)
Рассмотрим какой-то единичный бит в X. Если соответствующий бит в Y равен 0, то мы можем их поменять местами, уменьшив X и увеличив Y. При этом их сумма и xor не изменятся. Отсюда можно сделать вывод, что если какой-то бит равен единице в X то он будет равен единице и в Y. Отсюда Y = X + B. Учитывая, что X + Y = X + X + B = A, получаем следующие формулы для нахождения X и Y:
X = (A - B) / 2
Y = X + B
Следует также учесть, что если выполняется хотя бы один из следующих пунктов:
- A < B
- A и B имеют разную четность
- X and (A - X) ≠ X, где and - побитовое "и"
то ответа не существует и следует вывести -1.
Задача E: Точки (Даниил Нейтер)
Если перегруппировать слагаемые, то можно разбить сумму на две:
Рассмотрим подсчет суммы по иксам:
Полученная формула позволяет посчитать ответ за 1 проход. Сложность решения O(N).
Задача F: Турист (Илья Порублев)
Из события i можно попасть в событие j, если выполняются условия:
- ti ≤ tj
- |xi - xj| ≤ |ti - tj|· V
Если события представлять в виде точек на координатной плоскости с координатами (xi, ti), то предыдущие 2 условия можно представить графически, а именно:
Из события i можно попасть в событие j, если точка (xj, tj) лежит внутри угла направленного вверх с вершиной в (xi, ti), а стороны которого образуют угол arctg(V) с вертикалью. Сделаем преобразование координат, при котором точка с координатами (xi, ti) переходит в точку (pi, qi), где
pi = - xi + ti * V
qi = xi + ti * V
Тогда условие того что из события i можно попасть в событие j принимает вид: pi ≤ pj и qi ≤ qj. Отсортируем все точки по возрастанию координаты p, а при равном p - по возрастанию q. Задача (та часть, где можно самому выбирать стартовую точку) сводится к тому, чтобы в получившемся массиве найти самую длинную возрастающую подпоследовательность по q. Это можно сделать за O(NlogN).
Чтобы решить часть, в которой турист стартует из точки (0, 0) можно создать фиктивное событие со временем 0 и абсциссой 0 (если такого еще небыло) и потребовать чтобы мы обязательно посетили его первым.
Суммарная сложность решения O(NlogN).
Добрый день!
Я хотел бы анонсировать неофициальную трансляцию всеукраинской олимпиады школьников по информатике, которая будет проведена на Codeforces во вторник, 12 апреля в 16:00 по московскому времени. Контест пройдет на задачах недавно завершившейся всеукраинской олимпиады по информатике - UOI2011. Правила будут ACM-ICPC. К участию будут допускаться как команды, так и индивидуальные участники. Рейтинг за контест начисляться не будет.
Убедительная просьба не обсуждать задачи этой олимпиады до ее проведения, а так же не участвовать в контесте тех, кто знаком с условиями или решениями задач. Целью проведения, в первую очередь, является тренировка.
Авторами задач являются: Даниил Нейтер, Роман Едемский, Роман Ризванов, Илья Порублев и я (Ярослав Твердохлеб).
После начала контеста задачи будут доступны в PDF по ссылкам:
Я давно собирался написать некоторые свои мысли о системе взломов, которую мы имеем на данный момент, и раунд 60 стал своеобразным толчком к этому.
Что мы имеем на данный момент: взломы можно делать на протяжении всего раунда, каждый успешный взлом приносит 100 очков, каждый неудачный взлом отнимает 50 очков, участники из обоих дивизионов перемешаны и каждый может взламывать каждого в своей комнате.
Мне всегда казалось, что на олимпиадах по программированию вроде Codeforces или Topcoder в первую очередь нужно уметь решать задачи, а уже потом взламывать чужие решения. Кто-то скажет что все заранее знают правила и у всех свои стратегии. Я согласен с этим, но тем не менее не считаю правильным иметь возможность за счет вариации стратегии будучи с 2-мя задчами обойти человека который решил 4, причем не очень медленно.
Для статистики я взял последние 10 раундов для обоих дивизионов и для каждого выписал максимальный процент баллов, набранных за счет взломов от общего количества баллов набранных участником, взятый среди первой пятерки по результатам контеста.
Раунд Максимальный процент Средний процент
Codeforces Beta Round #39 12.1% 4.8%
Codeforces Beta Round #41 10.3% 7.0%
Codeforces Beta Round #47 15.4% 5.2%
Codeforces Beta Round #48 30.8% 15.9%
Codeforces Beta Round #50 10.8% 5.4%
Codeforces Beta Round #51 11.6% 2.8%
Codeforces Beta Round #53 20.8% 10.8%
Codeforces Beta Round #56 12.2% 2.4%
Codeforces Beta Round #58 27.3% 6.5%
Codeforces Beta Round #60 70.5% 53.0%
Итак, в каждом из последних 10 контестов для обоих дивизионов был хотя бы один участник из первой пятерки, набравший более 10% своих баллов на взломах. В 4 из 10 контестов был хотя бы один участник из топ-5, набравший более 20% своих баллов на взломах. В одном контесте был участник, набравший более 70% своих баллов на взломах, причем в среднем на этом контесте первая пятрка набрала более 50% баллов на взломах.
Хоть ситуации подобные последнему раунду - редкость (хотя, в раунде 58 было бы то же самое, не будь там проблемы с условием задачи А), но все же они встречаются. Далее я постараюсь провести анализ ситуации со взломами на последнем раунде.
Итак, победитель раунда реализовал 39 успешных взломов, причем в его комнате другими участниками была сделана всего одна успешная попытка взлома. Теперь возьмем комнату 3. Во взломах в этой комнате принимали участие 4 человека, из них двое сделали более одного успешного взлома, поэтому далее будем учитывать только их. В сумме они реализовали 28 успешных взломов по задаче А, причем в этой комнате было всего 3 решения по этой задаче, которые не прошли финальное тестирование. Учитывая что в комнате победителя было 5 решений задачи А, которые не прошли финальное тестирование, то можно проигнорировать эти 3 решения из комнаты 3. Получаем, что даже если сильнейший участник попадет в комнату 3 и реализует эти 28 взломов с 1 попытки, он максимум сможет получить 2800 очков на взломах против 3800 реально полученных очков из комнаты 7.
Из-за распределения по комнатам очки за взломы могут варьироваться даже на +-1000 и даже сильнейшие участники попав в неудачную комнату не имеют шансов выиграть контест. Рассматривая эту ситуацию с комнатами 3 и 7 я не учитываю то что взламывать могут несколько человек в одной комнате, что тоже сильно снижает суммарные очки по взломам. Например, в комнате 6 два участника примерно в одно и то же время (на 11 и 13 минутах) начали взламывать задачи А, позже к ним присоединился еще один. Каждый из первых двух начавших взламывать реализовал по 12 взломов. Сильнейший участник попав в эту комнату не имеет шансов реализовать все взломы в этой комнате, даже если он очень быстро сдаст и заблокирует А и сразу начнет взламывать чужие решения. Даже если предположить что у него отберут 12 взломов, реализовав все остальные взломы с 1 раза он сможет набрать 2000 очков на взломах, что на 1800 меньше чем у победителя раунда. Опять же, шансов победить в этом раунде у него нет.
Я считаю что текущая система должна быть подвергнута изменениям. Есть 2 способа стабилизировать взломы, причем лучше всего их объединить.
1. Разделить участников из 1 и 2 дивизиона в разные комнаты. В среднем первые 5 участников по турнирной таблице последнего раунда набрали +300 очков на взломах фиолетовых, оранжевых и красных, остальные очки были набраны на серых, зеленых и синих. Разделив дивизионы, красные уже не смогут так беспощадно взламывать серых, тем самым уменьшится суммарное количество очков по взломам.
2. Изменить количество очков за взломы. Я уже не помню кем и где высказывалась мысль о том, что можно насчитывать баллы за взлом в зависимости от разности рейтинга взломщика и взламываемого. Например, если красный взламывает серого, прибавлять 20 баллов, если же серый взламывает красного, прибавлять 100 баллов. Количество баллов за взломы у победителя не будет заоблачным, в то же время вряд ли серые смогут навзламывать много красных и выбиться в топ турнирной таблицы за счет этого, не решив при этому большую часть задач.
Это сугубо мое мнение и оно может отличаться от мнения общественности. Критика и комментарии приветствуются.
Предположим, что верхняя и нижняя стороны прямоугольника фиксированы и нам осталось только выбрать левую и правую стороны. Тогда мы за О(К) можем найти список всех прямоугольников, которые попадают в нашу полосу, а так же список всех прямоугольников, у которых только часть попадает в полосу. Тогда мы можем представить это в виде отсортированного набора отрезков [l,r], где l и r - икс координаты левой и правой сторон прямоугольника.
Если какие-то отрезки в нашем наборе имеют общую точку - склеим их в один большой отрезок и запомним что теперь в нем на самом деле два отрезка. Таким образом, после того как мы склеили все отрезки, у нас получится какой-то набор отрезков, для каждого из которых известно количество прямоугольников, которые им покрываются (если в нем есть прямоугольник, который не лежит полностью в нашей полосе, то будем считать что такой отрезок содержит бесконечное количество прямоугольников). Теперь мы можем пройти по всем свободным отрезкам (находящимся между соседними отрезками из нашего набора) и посчитать количество способов покрыть их отрезком в котором лежит не более трех объектов (для этого будем помнить только те свободные отрезки, которые отделены от текущего не более чем тремя объектами).
Таким образом, мы уже имеем решение за O(N2K): перебрать все возможные горизонтальные полосы и в каждой за О(К) посчитать количество прямоугольников, которые покрывают от 1 до 3 объектов. Заметим, что если, например, верхняя сторона полосы не прилегает ни к какому из объектов, то мы можем ее сдвинуть вверх либо вниз и ответ для полосы не изменится. Следовательно, можно перебирать в качестве границ полосы только те строки, в которых есть хотя бы одна клетка, принадлежащая объекту, а затем домножать полученный ответ на расстояния до ближайших "не пустых" строк снизу и сверху.
Таким образом, мы получили решение работающее за O(K3) и не зависящее ни от размеров поля, ни от ограничения на максимальное количество покрываемых объектов.
На топкодере регулярно проходит shortest code competition по задачам срмов (обычно простым). Иногда довольно интересно посмотреть, как можно сжать код, казалось бы простой задачи, до совершенно непонятного, но в то же время работающего. Предлагаю проводить такие соревнования и здесь, на Codeforces.
Я начну с задачи C из Codeforces Beta Round #24. Правила простые: каждый следующий код должен быть короче предыдущего. Побеждает тот, кого никто не смог перебить. Длина кода - количество символов в нем, не считая пустых (пробелов, табов, переводов строки и т.д.). Само собой, код должен быть АС хотя бы на одном из доступных компиляторов. Насколько я знаю, на топкодере дефайны в С++ не используют в таких соревнованиях, поэтому предлагаю и здесь их не использовать.
Учитывая возможности некоторых языков, предлагаю проводить отдельный зачет по разным языкам, т.к. вряд ли C++ или Pascal смогут соревноваться с Haskell или Python.
214:
#include <iostream>
__int64 n,k,x,y,a[' '],b[' '],d;
int main()
{
std::cin>>n>>k>>x>>y;
for(k%=2*n;d<n;d++) std::cin>>a[d]>>b[d],d<k?x=2*a[d]-x,y=2*b[d]-y:0;
for (d=0,k-=n;k>0;--k,++d) x=2*a[d]-x,y=2*b[d]-y;
std::cout<<x<<" "<<y;
}
Представляю разбор Codeforces Beta Round #13. Если будут какие-то вопросы или замечания - прошу писать в комментариях.
Приветствую всех на Codeforces Beta Round #13, который состоится в четверг, 6 мая в 18:00 по московскому времени. Автором задач этого контеста буду я.
Хочется сказать отдельное спасибо Михаилу Мирзаянову, который сделал проведение контеста возможным, Роману Едемскому и Андрею Максаю за помощь в тестировании авторских решений, а так же Дмитрию Матову за перевод условий на английский язык. Надеюсь, задачи вам понравятся.
Желаю чтобы число 13 оказалось для вас счастливым!
UPD: Поздравляю Ивана Метельского, который стал победителем решив все 5 задач!
Задачи можно посмотреть тут.
Полные результаты можно посмотреть тут.
UPD2: добавлен разбор.