Блог пользователя Polichka

Codeforces Round #108 (Div. 2)
Автор Polichka, 13 лет назад, По-русски

Добрый день!

Мы успешно пережили уже две недели нового семестра и рады поприветствовать вас на очередном рейтинговом раунде Codeforces для участников Div. 2. В нем как всегда могут принять участие все желающие.

Этот раунд подготовлен командой из трех человек: Gerald, NALP и Polichka. Мы благодарим за помощь в подготовке раунда и переводе задач Артема Рахова (RAD), Михаила Мирзаянова (MikeMirzayanov) и Марию Белову (Delinur).

Сегодня Петя запутался в таблицах:-( И вы можете помочь ему! Это же так просто!

Распределение баллов по задачам следующее: 500-1000-1500-2500-2500

Всем легких решений и высокого рейтинга!

UPD:

Всем спасибо за участие!

Разбор задач доступен по ссылке: Разбор задач

Полный текст и комментарии »

  • Проголосовать: нравится
  • +95
  • Проголосовать: не нравится

Codeforces Round #106 (Div. 2)
Автор Polichka, 13 лет назад, По-русски

Привет всем!

Сегодня состоится 106-й рейтинговый раунд Codeforces для участников Div 2. В нем могут принять участие все желающие. Вам представится возможность вместе с Петей отдохнуть от родителей, узнать несколько интересных фактов о марсианах и конечно порешать, как мы надеемся, интересные задачи для вас.

Этот раунд подготовлен командой из трех человек: Gerald, NALP и Polichka. Мы выражаем огромную благодарность за помощь в подготовке раунда и переводе задач Артему Рахову (RAD), Михаилу Мирзаянову (MikeMirzayanov) и Марии Беловой (Delinur).

Распределение баллов за задачи: 500-1000-1500-2500-2500.

Всем удачи и высокого рейтинга!

UPD: Разбор задач

Полный текст и комментарии »

  • Проголосовать: нравится
  • +129
  • Проголосовать: не нравится

Codeforces Round #103 (Div. 2) Разбор Задач.
Автор Polichka, 13 лет назад, По-русски
Задача A

Так как на первом месте должен стоять солдат с максимальным ростом, то логично поставить на первое место самого левого солдата с максимальным ростом, чтобы минимизировать время (число обменов). Исходя из таких же соображений на последнее место поставим самого правого солдата с минимальным ростом. Таким образом количество обменов это номер самого левого солдата с максимальным ростом  - 1 + n -  номер самого правого солдата с минимальным ростом. И если самый левый солдат с максимальным ростом стоит правее самого правого с минимальным ростом, то из этой суммы нужно вычесть один.

Задача B

Переберем все точки, в которых сидят генералы, и посчитаем количество не покрываемых никакой окружностью. Пусть xa < xb и ya < yb, если это не так, то просто поменяем xa и xb, ya и yb местами. Тогда генералы сидят в точках: (xa, y), (xb, y), (x, ya), (x, yb), где xa ≤ x ≤ xb и ya ≤ y ≤ yb. При подсчете ответа нужно аккуратно посчитать генералов, которые сидят в точках (xa, ya), (xa, yb), (xb, ya), (xb, yb), чтобы не учесть их дважды.

Задача C

Посчитаем количество каждой из букв во второй строке и сохраним это, например, в массив a[1..26]. Для первой строки для префикса длины, равной длине второй строке, (это первая подстрока) посчитаем в массив b[1..26] количество каждой из букв. Знаки вопроса в массиве b не будем учитывать. Если для всех i выполняется b[i] ≤ a[i], то значит это хорошая подстрока. Далее перейдем ко второй подстроке: вычтем из массива b первый символ: b[s[1] - 'a' + 1] –  и прибавим n + 1 символ, если n --- длина строки p: b[s[n + 1] - 'a' + 1] +  + . Если какой-либо из этих символов вопрос, то для него прибавление или вычитание делать не нужно. Далее повторяем выше рассмотренную проверку и переходим к следующей подстроке. Повторяем эти действия, пока не переберем все подстроки строки s длины n.

Задача D

d[i] --- минимальные расстояния от вершины s до вершины i, посчитанные с помощью алгоритма Дейкстры. 
Далее переберем все ребра графа, и для каждого из них посчитаем количество точек, не совпадающих с вершинами, лежащих на них, находящихся на расстоянии l от вершины s (причем l - минимальное расстояние от этих точек). 

Рассмотрим ребро (u, v):

если d[u] < l и l - d[u] < w(u, v) и w(u, v) - (l - d[u]) + d[v] > l, то прибавим к ответу точку, лежащую на этом ребре на расстоянии l - d[u] от вершины u;

если d[v] < l и l - d[v] < w(u, v) и w(u, v) - (l - d[v]) + d[u] > l, то прибавим к ответу точку, лежащую на этом ребре на расстоянии l - d[v] от вершины v;

если d[v] < l и d[u] < l и d[u] + d[v] + w(u, v) = 2 * l, то прибавим к ответу точку, лежащую на этом ребере на расстоянии l - d[u] от вершины u и l - d[v] от вершины v.

Также если d[i] = l, то прибавим к ответу вершины.

Задача E

Рассмотрим каждого спортсмена в отдельности. Очевидно, что мы можем по координатам спортсмена понять: какие клетки на побочной диагонали являются ближайшими к нему, они образуют "отрезок" на побочной диагонали. Выпишем для каждого спортсмена эти отрезки.

Выберем спортсменов так, чтобы каждому из них мы могли сопоставить ровно одну клетку на побочной диагонали из его "отрезка", и каждой клетке на побочной диагонали соответствовал не более, чем один спортсмен. Понятно, что спортсмены смогут дойти до "своих" клеток, не побывав с кем-либо на одной клетке. Осталось максимизировать количество выбранных спортсменов. Таким образом переформулированная задача решиется жадно.

Полный текст и комментарии »

Разбор задач Codeforces Round 103 (Div. 2)
  • Проголосовать: нравится
  • +51
  • Проголосовать: не нравится

Codeforces Beta Round #28 (Разбор задач A и B)
Автор Polichka, 14 лет назад, По-русски

А. Задача Бендера.

 

Будем говорить, что мы крепим j-ый прут к i-ому гвоздю, если мы крепим j-ый прут местом сгиба к i -ому гвоздю.

 

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

Если задача имеет решение, то нам надо выбрать к каким по четности гвоздям мы будем крепить прутья, а также поднабор из n / 2 прутьев, который и будет считаться ответом.

Если мы крепим j-ый прут к i-ому гвоздю, то len[j] = dist(i, i - 1) + dist(i, i + 1), где len[j] - длина j-ого прута, а dist(i, k) - расстояние между гвоздями с номерами i и k.

Ограничения задачи позволяли решать ее за O(nm).  Проходим внешним циклом по гвоздям, к которым будут крепиться пруты(сначала по гвоздям с четными номерами, потом по гвоздям с нечетными номерами), проходим внутренним циклом по прутьям и проверяем: можем ли мы прикрепить хотя бы один из оставшихся прутьев к текущему гвоздю. Если можем, то помечаем этот прут и далее его не рассматриваем, если нет, то проделываем то же самое для гвоздей с нечетными номерами, но при этом нужно снять все пометки с прутьев, сделанные при рассмотрении гвоздей с четными номерами. Если же и для нечетного случая мы не нашли ответ, то искомого поднабора не существует.

 

B. pSort.

 

Понятно, что мы можем поменять содержимое ячеек i и j, если |i - j| = di или |i - j| = dj.

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

Построим граф, вершинами в котором являются ячейки массива, а ребро существует между вершинами i и j, если возможен обмен между ними. Граф получаем неориентированный. То есть, если из вершины i в полученном графе достижима вершина j, то возможна такая серия обменов, что содержимое ячейки i поменяется с содержимым ячейки j.

Перестановку возможно отсортировать, если для всех i верно, что из вершины i достижима вершина p[i], где p - исходная перестановка.

 

Полный текст и комментарии »

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

Codeforces Beta Round #28 (Codeforces format)
Автор Polichka, 14 лет назад, По-русски
Внимание-внимание!!!

Сегодня команда Saratov SU #1 (Gerald, Polichka, Fefer) приглашает всех желающих на  Codeforces Beta Round #28. Олимпиадным программированием мы начали заниматься еще в школе, а потом продолжили в университете. Мы прошли нелегкий путь от команды SU #7 до Saratov SU #1, и теперь стараемся оправдывать этот номер. 

Мы предлагаем вам 5 занимательных задач. Вам предстоит помочь нескольким хорошим людям разобраться со своими проблемами, решить некоторые задачи администрации, поиграть в интересные игры, а также спасти мир.

Спасибо всем, кто помогал нам готовить этот раунд.

Желаем всем удачных взломов и быстрых accepted-ов!
    
UPD: Рейтинги обновлены

UPD:

Полный текст и комментарии »

  • Проголосовать: нравится
  • +75
  • Проголосовать: не нравится