The editorial is updated.

447A - DZY Loves Hash

We just need an array to store the numbers inserted and check whether a conflict happens. It's easy.

447B - DZY Loves Strings

Firstly the optimal way is to insert letter with maximal w_i. Let {w_i}. If we insert this character into the k'th position, the extra value we could get is equal to . Because of w_si ≤ num, when k = n + 1, we can get the largest extra value.

So if we insert the k letters at the end of S, we will get the largest possible value.

446A - DZY Loves Sequences

We can first calculate l_i for each 1 ≤ i ≤ n, satisfying a_{i - li + 1} < a_{i - li + 2} < ... < a_i, which l_i is maximal.

Then calculate r_i, satisfying a_i < a_i + 1 < ... < a_{i + ri - 1}, which r_i is also maximal.

Update the answer , when a_i - 1 + 1 < a_i + 1.

It's easy to solve this problem in O(n).

446B - DZY Loves Modification

If p = 0, apperently the best choice is choosing the row or column which can give greatest pleasure value each time.

Ignore p first,then we can get a greatest number ans. Then if we choose rows for i times, choose columns for k - i times, ans should subtract (k - i) × i × p.

So we could enumerate i form 0 to k and calculate ans_i - (k - i) * i * p each time, max {ans_i - (k - i) * i * p} is the maximum possible pleasure value DZY could get.

Let a_i be the maximum pleasure value we can get after choosing i rows and b_i be the maximum pleasure value we can get after choosing i columns. Then ans_i = a_i + b_k - i. We can use two priority queues to calculate a_i and b_i quickly.

446C - DZY Loves Fibonacci Numbers

As we know,

Fortunately, we find that

So,

With multiplicative inverse, we find,

Now,

As you see, we can just maintain the sum of a Geometric progression

This is a simple problem which can be solved with segment tree in .

446D - DZY Loves Games

Define important room as the trap room. Let w(u, v) be equal to the probability that DZY starts at u (u is a important room or u=1) and v is the next important room DZY arrived. For each u, we can calculate w(u, v) in O(n³) by gauss elimination.

Let A_i be equal to the i'th important room DZY arrived. So A_k - 1 = n, specially A₀ = 1. Let ans be the probability for DZY to open the bonus round. Easily we can know . So we can calculate ans in (a is equal to the number of important rooms) by matrix multiplication.

So we can solve the problem in . we should optimize this algorithm.

We can find that each time we do gauss elimination, the variable matrix is unchanged. So we can do gauss elimination once to do preprocessing in O(n³). Then for each time calculating w(u, v), the only thing to do is substitute the constants. In this way we can calculate w(u, v) in O(n³).

In this way, we can solve this problem in

446E - DZY Loves Bridges

Let n = 2^m. For convenience, we use indices 0, 1, ..., n - 1 here instead of 1, 2, ..., n, so we define a₀ = a_n.

Obviously this problem requires matrix multiplication. We define row vector , and matrix , where b_ii = 1, . The answer is row vector .

Since n can be up to 3 × 10⁷, we need a more efficient way to calculate. Let denote the matrix when m = k. For example,

Define , then we can easily find that

where denotes the identity matrix.

For an n × n matrix and a constant r, we can prove by induction that

Let α₁, α₂ be two 1 × n vectors, then we have

This result seems useful. Suppose we want to find , where , we have

so we just need to find , which is a self-similar problem. By recursion, it can be solved in time T(n) = T(n / 2) + O(n) = O(n).

Всем привет! Codeforces Round #FF(255) начнется совсем скоро! Раунд будет проходить в обоих дивизионах, приглашаем всех принять участие!

Главным героем задач этого раунда снова становится DZY! Вы все уже знаете, что DZY интересуется очень многими вещами. В этот раз у DZY есть много интересных задач. Задачи будут проще, чем в прошлый раз, тем не менее ваша помощь потребуется. В награду за помощь DZY подарит вам рейтинг.

Спасибо Gerald, который помогал нам в подготовке раунда. Также спасибо MikeMirzayanov, благодаря которому существуют существует Codeforces.

Задачи раунда готовили: jcvb, jiry_2 и я. Это наш первый раунд Codeforces :)

Ждем вас на контесте, DZY очень нужна ваша помощь!

Желаем удачи и удовольствия от решения задач! :)

UPD

Разбалловка для первого дивизиона: 500-1500-1500-2000-2500.

Разбалловка для второго дивизиона: 500-1000-1500-2500-2500.