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

Автор NBAH, история, 6 лет назад, По-русски

895A - Деление пиццы

Заметим, что если один из секторов непрерывен, то все оставшиеся куски также образуют непрерывный сектор. Для каждого непрерывного сектора найдем его угол, то есть сумму углов кусков входящих в него. Если угол одного сектора равен x, то разница углов секторов равна |x - (360 - x)| = |2 * x - 360| = 2 * |x - 180|. Переберем сектор, зная его угол x обновим ответ.

Асимптотика O(n2) или O(n).

Решение

895B - XK Отрезки

Для начала узнаем, как посчитать количество чисел на отрезке делящихся на x. Пусть левая граница отрезка это l, а правая r. Тогда количество чисел делящихся нацело на x и принадлежащих [l, r] равно r/x – (l-1)/x. Отсортируем массив a по возрастанию. Переберем левую границу отрезка, пусть это a[i]. Тогда на роль правой границы подходят все числа a[j] такие, что a[j] / x–(a[i] - 1) / x = k. Значение (a[i] - 1) / x мы знаем, а a[j] / x монотонно возрастает при возрастающем a[j]. То есть можно сделать бинарный поиск по отсортированному массиву, который найдет индексы минимального и максимального подходящего a[j], а значит и их количество.

Асимптотика O(n * log(n)).

Решение

895C - Квадратные подмножества

Заметим, что число x является квадратом некоторого натурального числа <=> в разложение x на простые множители каждое простое число входит четное количество раз. Простых чисел меньших 70 всего 19. Посчитаем битмаску для каждого из чисел от 1 до 70 по следующему принципу: В битовом представлении маски в разряде k стоит 1, если k-ое простое число входит в разложение этого числа нечетное количество раз. Иначе 0. Для каждого различного значения a[i] нас на самом деле интересует только войдет оно четное количество раз в произведение или нечетное. Пусть f1[i], f0[i] это количество способов взять из a нечетное и четное количество чисел i соответственно. Будем считать динамику по битмаскам. Обозначим за dp[i][j] количество способов выбрать некоторые элементы массива <= i таким образом, чтобы в их произведении в нечетных степенях содержались только те простые числа, на месте порядкового номера которых в битовом представлении j стоит 1. Изначально dp[0][0] = 1. Переходы следующие:

dp[i + 1][j] +  = dp[i][j] * f0[i + 1]

Тогда ответ это dp[70][0].

Асимптотика O(max*2^cnt(max)), где max максимальное значение a[i], а cnt(max) количество простых чисел не больших max.

Решение

895D - Оценочная строка

Пусть мы умеем вычислять функцию f(s) равную количеству перестановок строки a строго меньших s. Тогда ответ равен f(b) - f(a)–1. Теперь надо научиться находить значение f(s). Посчитаем количество вхождений каждой буквы в строку acnt[26]. Будем перебирать позицию первого различного символа в перестановке a и строке s и обновлять количество оставшихся символов cnt[26]. Для каждой такой позиции переберем символ в перестановке a который будет стоять на этой позиции. Он должен быть меньше символа на этой позиции в строке s. Для каждой такой ситуации надо вычислить и прибавить к ответу количество различных перестановок которые можно получить используя не задействованные на данный момент символы. Их количество хранится в cnt[26]. В простейшем виде это решение работает за O(n * k2), где k размер алфавита. Такое решение не проходит тесты, но его можно оптимизировать до O(n * k), что уже проходит по времени.

Асимптотика O(n * k), где k размер алфавита.

Решение

Еще одно решение

895E - С закрытыми глазами

Будем поддерживать для каждой позиции математическое ожидание значения на ней. Изначально для позиции i оно равно a[i]. Пусть надо обработать запрос первого типа. Каждое число из отрезка [l1, r1] останется на своем месте с вероятностью (r1–l1) / (r1–l1 + 1). Вероятность того, что оно будет заменено числом из [l2, r2] равна 1 / (r1 - l1 + 1). Математическое ожидание числа, на которое оно будет заменено есть среднее арифметическое математических ожидании чисел в [l2, r2], обозначим его за x. Тогда чтобы обновить матожидание числа из [l1, r1] надо умножить его на (r1–l1) / (r1–l1 + 1) и прибавить x / (r1–l1 + 1). То есть запрос первого типа сводится к запросу домножить все числа на отрезке и прибавить к ним число. Чтобы обработать второй запрос надо находить сумму чисел на отрезке. Все эти запросы можно обрабатывать деревом отрезков.

Асимптотика O(n + q * log(n)).

Решение

Еще одно решение

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

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

Автор NBAH, история, 6 лет назад, По-русски

Всем привет!

26 ноября в 19:05 MSK состоится рейтинговый раунд Codeforces #448 для участников из второго дивизиона. Традиционно, участники из первого дивизиона приглашаются поучаствовать в соревновании вне конкурса.

Автором всех 5 задач являюсь я. Это мой второй раунд на Codeforces! Советую участникам ознакомиться с условиями всех задач. Надеюсь каждый найдет себе задачу по вкусу.

Хочется выразить благодарность координатору раунда vintage_Vlad_Makeev за помощь в подготовке контеста и igdor99 за помощь в разработке задач, а также MikeMirzayanov за замечательные платформы Codeforces и Polygon. Ну и, конечно, Tommyr7, Arpa, 300iq за прорешивание раунда.

Разбалловка: 500-1000-1750-2000-2250

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

UPD: Соревнование завершено! Скоро будет опубликован разбор.

UPD: Разбор

Поздравляем победителей!!!

Div1

  1. uwi

  2. Benq

  3. irkstepanov

  4. dreamoon_love_AA

  5. JustasK

  6. eddy1021

  7. yancouto

  8. chemthan

  9. Nephren_Ruq_Insania

  10. KrK

Div2

  1. Nephren_Ruq_Insania

  2. Mahan_sh

  3. lsrothy

  4. ngfam

  5. georgerapeanu

  6. ZalBinHassan

  7. mtkaya

  8. Bodo

  9. szhouan

  10. fchirica

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

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

Автор NBAH, история, 8 лет назад, По-русски

A

Научимся определять расстояние между точками. Далее, зная, что время — это расстояние делить на скорость, будем определять время для каждого таксиста, за которое он сможет доехать до Василия. Ответ это минимальное из времен.Не забудем про double.

Асимптотика O(n).

Решение

B

Пусть c[x] — количество магазинов в которых цена за напиток равна x. Посчитаем для этого массива префиксные суммы. Далее возможные следующие варианты:

1)Если текущее количество денег у Василия больше, чем размер массива с префиксными суммами то выводим n.

2)Иначе выводим префиксную сумму для количества денег, которое сейчас у Василия.

Асимптотика O(q+n).

Решение

C

Будем решать задачу динамическим программированием. dp[i][j] это минимальное количество энергии, которое надо потратить чтобы расположить первые i строк в алфавитном порядке и i-ая из них будет перевернута если j=1 и не перевернута если j=0. dp[i][j] обновляем через dp[i - 1][0] и dp[i - 1][1]. Остается проверить, что i-ая строка лексикографически больше (i - 1)-ой(если j=1 то проверяем перевернутую i-ую строку, аналогично для (i - 1)-ой). После чего обновляем dp[i][j]=min(dp[i][j],dp[i - 1][0]+c[i]*j), dp[i][j]=min(dp[i][j],dp[i - 1][1]+j*c[i]). Ответ это минимум из dp[n][0] и dp[n][1].

Асимптотика O(n+sum_length).

Решение

D

Каждое число из множества будем хранить в двоичной системе счисления(каждое число будет состоять из 32-х 0 или 1) в такой структуре данных как бор(рёбра — это будут биты 1 или 0, а вершины будут отвечать за то, можно ли пройти по текущему ребру). Чтобы ответить на запрос типа "? x" будем спускаться по бору от старших битов к младшим и смотреть можем ли мы сейчас ксором в i-м бите получить единицу, если можем, то переходим, иначе идём туда, куда можем идти.

Асимптотика O(q*log(10^9)).

Решение

E

Обнесем матрицу рамкой из фиктивных элементов. В каждом элементе матрицы и рамки храним значение элемента номер элемента соседнего справа и номер элемента соседнего снизу. Когда приходит запрос поменять местами прямоугольники надо поменять значения элементов только по периметру прямоугольников.

Асимптотика O(q*(n+m)).

Решение

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

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

Автор NBAH, история, 8 лет назад, По-русски

Всем привет!

11 августа в 19:35 MSK состоится рейтинговый раунд Codeforces #367 для участников из второго дивизиона. Традиционно, участники из первого дивизиона приглашаются поучаствовать в соревновании вне конкурса.

Автором задач являюсь я. Это мой первый раунд на Codeforces! Советую ознакомиться с условиями всех задач. Надеюсь каждый найдет себе задачу по вкусу.

Хочется выразить благодарность координатору раунда GlebsHP за помощь в подготовке контеста, Yury_Bandarchuk и IvanVan за помощь в подготовке задач и прорешивание раунда, а также MikeMirzayanov за замечательные платформы Codeforces и Polygon.

UPD: Разбалловка 500-1000-1500-2000-2500

UPD: Разбор

UPD: Соревнование завершено. Поздравляем победителей!

Div.1 winners:

1.anta

2.W4yneb0t

3.sugim48

4.uwi

5.Kmcode

Div.2 winners:

1.jiangzixiao

2.Shining

3.BurningHuie

4.AwD

5.stjepanp

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

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