Blog entries - Codeforces

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.

Firstly the optimal way is to insert letter with maximal w_i. Let $\text{[math]}$ {w_i}. If we insert this character into the k'th position, the extra value we could get is equal to $\text{[math]}$ . Because of w_{s_i} ≤ 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 - l_i + 1} < a_{i - l_i + 2} < ... < a_i, which l_i is maximal.

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

Update the answer $\text{[math]}$ , 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, $\text{[math]}$

Fortunately, we find that $\text{[math]}$

So, $\text{[math]}$

With multiplicative inverse, we find,

$\text{[math]}$

Now, $\text{[math]}$

As you see, we can just maintain the sum of a Geometric progression $\text{[math]}$

This is a simple problem which can be solved with segment tree in $\text{[math]}$ .

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 $\text{[math]}$ . So we can calculate ans in $\text{[math]}$ (a is equal to the number of important rooms) by matrix multiplication.

So we can solve the problem in $\text{[math]}$ . 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 $\text{[math]}$

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 $\text{[math]}$ , and matrix $\text{[math]}$ , where b_ii = 1, $\text{[math]}$ . The answer is row vector $\text{[math]}$ .

Since n can be up to 3 × 10⁷, we need a more efficient way to calculate. Let $\text{[math]}$ denote the matrix $\text{[math]}$ when m = k. For example, $\text{[math]}$

Define $\text{[math]}$ , then we can easily find that

$\text{[math]}$

where $\text{[math]}$ denotes the identity matrix.

For an n × n matrix $\text{[math]}$ and a constant r, we can prove by induction that $\text{[math]}$

Let α₁, α₂ be two 1 × n vectors, then we have $\text{[math]}$

This result seems useful. Suppose we want to find $\text{[math]}$ , where $\text{[math]}$ , we have

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