895A - Pizza Separation

We can notice that if one of the sectors is continuous then all the remaining pieces also form a continuous sector.If angle of first sector is equal to x then difference between angles of first and second sectors is |x - (360 - x)| = |2 * x - 360| = 2 * |x - 180|. So for each possible contnuous sector we can count it's angle and update answer.

Time complexity O(n²) or O(n).

895B - XK Segments

First, we need to understand how to find the number of integers in [l, r] segment which are divisible by x. It is r / x–(l - 1) / x. After that we should sort array in ascending order. For each left boundary of the segment l = a[i] we need to find minimal and maximal index of good right boundaries. All right boundaries r = a[j] should satisfy the following condition a[j] / x–(a[i] - 1) / x = k. We already know (a[i] - 1) / x, a[j] / x is increasing while a[j] increases. So we can do binary search on sorted array to find minimal/maximal index of good right boundaries and that mean we can find the number of good right boundaries.

Time complexity O(n * log(n)).

895C - Square Subsets

We can notice that x is a perfect square of some integer if and only if each prime number enters decomposition of x into prime factors even times. There are only 19 prime numbers less than 70. Now we should find the bitmask for each integer in [1, 70] by the following way: There is 1 in bit representation of mask in k-th place if k-th prime number enters decomposition of that numbrer odd times. Else there is 0. For each integer between 1 and 70 we need to find the number of ways we can take odd and even amount of it from a. Let f1[i], f0[i] be that number of ways relatively. Let dp[i][j] be the number of ways to choose some elements which are <= i from a, and their product has only those prime numbers in odd degree on whose index number j has 1 in binary representation. Initially dp[0][0] = 1.

dp[i + 1][jxormask[i + 1]] +  = dp[i][j] * f1[i + 1]

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

The answer is dp[70][0].

Time complexity is O(max*2^cnt(max)), where max is maximal integer a[i], and cnt(max) is the number of prime numbers less than max.

895D - String Mark

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

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

895E - Eyes Closed

Будем поддерживать для каждой позиции математическое ожидание значения на ней. Изначально для позиции 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)).