我們發現中文有一些顯示問題，之後會再處理。 The Chinese version has some display issue with latex for now.

A. Numbers

If D > 0, then there are at most D - 1 integers between the X-th largest integer and the X-smallest integer. So the answer would be 2X + D - 1. If D = 0, then the X-th largest integer is the exactly same integer as the X-smallest integer. So the answer is 2X - 1. If D < 0, then the case with the largest number of integers would be: the X-smallest integer is the very next integer larger than the X-largest integer if sorted ascendingly. So the answer would be 2X - 2.

Overall, the answer can be expressed as 2X + max(D - 1,  - 2). Time complexity is O(1).

如果 D > 0，則第 X 大的數跟第 X 小的數之間最多有 D - 1 個數字。所以答案為 $2X + D — 1$。 如果 D = 0，則第 X 大的數跟第 X 小的數其實是同一個數字。所以答案為 $2X — 1$。 如果 D < 0，則最多數字的情況為：如果由小到大排序後，第 X 小的數恰好排在第 X 大的數之後。所以答案為 $2X — 2$。

整體而言，答案可以寫成 $2X + \max(D — 1, -2)$。時間複雜度為 $O(1)$。

B. Power

There are at most 10⁶ discrete time in the logs so if we can find out how many computers are in use at each time, we can calculate the final answer by summing the cost at each time in O(10⁶) time. In order to find out that number, we could scan through the log and accumulate the number of on events and off events at each time which takes O(n) time. After that, just simulate those events time by time to get the number of computers in use at each time.

Time complexity is O(n + max(t)).

時間的最大值為 10⁶，也就是說如果我們可以對每個時間點找出有幾台電腦正在運作中，就可以把每個時間點的花費加總起來而得到最終答案。找出每個時間點有幾台電腦正在運作中的方法為，用 O(n) 的時間掃描一次紀錄檔，並且統計每個時間點開機了幾次跟關機了幾次。之後就可以按照時間模擬這些開關機的事件以求出對於毎個時間有多少台電腦正在運作。

時間複雜度為 $O(n + max(t))$。

C. Robot and Maze

In a word, depth first search. But watch out for stepping into visited blocks to avoid looping. Moreover, you need to issue a command to go back to the previous block in the calling stack. You can use no more than answer × 4 moving commands to solve this task.

Time complexity is O(answer).

簡而言之，深度優先搜尋(DFS)。必須注意的點是，避免重複踏入相同的格子內造成迴圈。另外，在返回上一層函式的同時必須命令機器人移動一次回到上一層的位置。你可以只使用 answer × 4 次移動命令來解這一題。

時間複雜度為 $(answer)$。

D. Combination

Firstly, you have to use inverse modular to deal with the division in the calculations. The combination function is straight forward but there are cases that the C(a + k, b + k) would become 0 for some intermediate values of k because of the modular operation. One way to handle this is to maintain the current C(a + k, b + k) using the form p^x × r where x is the largest possible integer. If x = 0 we know C(a + k, b + k) = r mod p, otherwise we know C(a + k, b + k) = 0 mod p.

Let's consider a scenario to illustrate the meaning of x. The task is to maintain the value n mod 3 with multiple and division operations. Initially n = 2 and the operations are 1.) multiply by 3 then 2.) divide by 3. If we just simulate each step, we would have n = 0 when the first operation is applied and never recover the true value after the second operation. So, with x, we would have x = 0, n = 2 initially. After the first operation we would have x = 1, n = 2. Since x ≠ 0 so we would know the answer is 0 now. After the second operation, we would have x = 0, n = 2 which preserves the truth that the answer is 2.

When maintaining C(a + k, b + k). There are two operations: multiple and division. To multiple by v, first we find x', r' such that v = p^x' × r', then do x = x + x', r = r × r'. To divide by v, first we find x', r' such that v = p^x' × r', then do x = x - x', r = r × modular_inverse(r').

Time complexity is .

首先，你必須使用 inverse modular 去處理除法的問題。計算組合的方法很直覺，但是這題中會有一些情況下，$C(a + k, b + k)

Unable to parse markup [type=CF_TEX]

時間複雜度為 $O((b + n) \times [\log_p(a+n) + \log(p)])$。

E. Disk Raid

The key is to use matrix operations inside a segment tree (or similar data structures). In a segment tree, each node will be associated with a range [L, R]. In each node, we store a vector V of size 1 × (n + 1) where the element at position i for 0 ≤ i < n is the sum of the disk values in the range (i.e. ) and the last element is the size of the range (i.e. R - L + 1). Each operation can be applied to such vector by a matrix multiplication V' = V × M_op. We'll describe how to construct such matrix for each operation below. Here we take n = 2 as example.

這題的關鍵為在 segment tree (或類似的結構裡) 使用矩陣運算。在 segment tree 中，毎一個 node 代表一個範圍 [L, R]。在每一個 node 裡面，我們存一個 1 × (n + 1) 的 vector V，V 中位置 i (0 ≤ i < n) 的元素為範圍內硬碟 i 的值的總和 (也就是 ))，而最後一個元素的值為範圍的大小 (也就是 R - L + 1)。毎一個操作都可以看作為一次矩陣乘法 V' = V × M_op。下面我們會描述要如何構造這些矩陣，以 n = 2 為例。

Copy operation from disk 0 to disk 1: Copy 操作，從硬碟 0 到硬碟 $1$：
1 1 0
0 0 0
0 0 1

Modify operation for disk 0: Modify 操作，對於硬碟 $0$：
p1 0 0
0 1 0
p2 0 1

AdvancedModify operation reading from disk 0 and writing to disk 1: AdvancedModify 操作，從硬碟 0 中讀取，寫入硬碟 $1$：
1 p 0
0 1 0
0 0 1

Swap operation for disk 0 and disk 1: Swap 操作，交換硬碟 0 跟硬碟 $1$：
0 1 0
1 0 0
0 0 1

Using the 32-bit unsigned integer data type would solve the modular issue natively. Time complexity is .

使用 32 位元的無號整數資料結構可以解決取餘數的問題。時間複雜度為 $O(n^3q\log w)$。

Sorry for the delay but here is the (partial) editorial of 23rd weekly training farm.

I set up 3 problems (B, E, F) in this contest.

Here is the link to the contest: http://mirror.codeforces.com/group/gRkn7bDfsN/contest/211543

===================================================================================================

B. cut down

The idea of the problem is from this deep learning paper: Martins, André FT, and Ramón Fernandez Astudillo. "From softmax to sparsemax: A sparse model of attention and multi-label classification." CoRR, abs/1602.02068 (2016). You can read the paper here: https://arxiv.org/abs/1602.02068

You can use binary search to find the answer in time. But what if I ask you to output the exact answer (in the form of division of two integers p / q) instead of a floating point number? That problem can be solved in time, too! Actually, if the input is sorted, O(N) time is sufficient for the problem!

Let's consider a simplified problem first, can you check if there is a valid T satisfying T < A_i for all i? The solution is to assume that such T exists which implies , then verify if T is less than the smallest A_i.

To solve the original problem, we need one more observation: After sorting A in descending order, we have where k is the largest number that the above simplified problem is true. So we can maintain a partial sum to find the value of k and the answer in O(N) time after sorting.

Furthermore, the original problem can be solved in O(N) time overall (even with unsorted input) using linear selection algorithm!

E. tree split

This problem is equivalent to: Is there a way to remove some edges in a tree so that the remaining forest is consists of 3 vertices trees?

Removing an edge in the given tree splits all vertices into two trees. Let's denote the number of the vertices in the two resulting trees as N₁ and N₂. The key observation is that if both N₁ and N₂ is a multiple of 3 for an edge, then this edge needs to be removed. Moreover, if N₁ is a multiple of 3 then N₂ must be a multiple of 3! So a dfs on the vertices maintaining the number of visited vertices can count the number of edges to remove in O(N) time.

Finally, we just need to check if removing those edges will result in a forest of exactly N trees. This can be assured if the number of edges removed is equal to N - 1.

F. Strings

The key observation is that although we allow indirect comparison, direct comparisons is still required for every pair of vocabularies to ensure a unique order. In addition, to compare two strings we just need to define the order of the first different character of the two strings. So we can brute force every pair of vocabularies and find out the set of the characters need to be defined in O(N²) time. The size of such set would be the answer since any permutation of this set of characters would work.

Update Editorial of PF is published.

PA

This is a relatively simple problem. We only need to check if the sum of the lengths is larger than m times 60.

簡單題。判斷所有的歌曲長度加起來有沒有大於 m 的 60 倍。

PB

This problem is asking the index of the very next Fibonacci number. The takeaway point is that there is only a small amount of Fibonacci numbers in the range of 32-bits integer. Also, overflow needs to be considered if you choose to use 32-bits integer instead of 64-bits data types.

這題是在問下一個費波那契數列中數字是第幾個。一個小重點是 32 位元整數範圍內的費波那契數列很稀少。另外如果使用 32 位元非 64 位元資料型態的話，那必須考慮溢位的問題。

PC

https://en.wikipedia.org/wiki/Great-circle_distance

https://zh.wikipedia.org/wiki/大圓距離

PD

We binary search the answer. To check if time T is sufficient, we check the maximum flow of the following new constructed graph:

Firstly, we split every vertex v in the original graph into 2 × t vertices in the new graph (v, dir, t) where and t is the time index starting from 1. Then, we construct the following capacity 1 directional edges:

• (v, in, t) → (v, out, t) for all v and 1 ≤ t ≤ T.
• source to all (v, in, 1) for all v which has an airplane initially.
• (v, out, t) to sink for all v which is a runway and all 1 ≤ t ≤ T.
• (v_i, out, t - 1) → (v_j, in, t) and (v_j, out, t - 1) → (v_i, in, t) for all 2 ≤ t ≤ T and all (v_i, v_j) pairs having an edge in the original graph.

The time complexity of each flow using dinic is O(TE) where E is the number of edges since we have at most T units of flow. We have O(E) = O(nm) and O(T) = O(n), along with the complexity of binary search the overall complexity is .

我們可以用二分搜尋來找答案。對於每個可能的答案 $T$，我們可以用以下的方法建立一個新的圖並檢查它的最大流：

首先，對於每個原始圖裡面的點 v，我們在新圖裡建立 2 × t 個點 (v, dir, t)， 以及 t 代表從 1 開始的時間點。 接下來，我們用以下的方法建邊：

• 對於所有的 v 以及 1 ≤ t ≤ T 建立 (v, in, t) → (v, out, t) 的邊。
• 對於所有一開始有飛機的 v 建立 source 到 (v, in, 1) 的邊。
• 對於所有代表跑到的 v 以及所有 1 ≤ t ≤ T 建立 (v, out, t) 到 sink 的邊。
• 對於所有 2 ≤ t ≤ T 以及所有原始圖中的邊 (v_i, v_j) 建立 (v_i, out, t - 1) → (v_j, in, t) 以及 (v_j, out, t - 1) → (v_i, in, t) 的邊。

用 dinic 做最大流的話，因為我們最多只有 T 單位的流，所以時間複雜度是 O(TE)，這裡的 E 是邊的數量。我們有 O(E) = O(nm) 以及 $O(T) = O(n)$，加上二分搜尋的時間複雜度，總複雜度會是 $O(n^2m\log{n})$。

PE

Judging from the scale of n, an O(n²) algorithm is sufficient. So it's not hard to guess that doing flood fill to check for each room's size would be the last step. Follow that instinct we need to do discretization in O(n²) to prepare for the flood fill. That turns out to be possible. One way of discretization is to create a 2n × 2n map. Observed that there is only O(n) walls, we can use O(n) time to register each wall on the map.

We must be careful to not count those non-enclosed areas. This may be done by carefully designed flood fill (e.g. special return value when out of bound) or by mark out the outside area before doing the flood fill.

An O(2n × 2n) algorithm could pass the tests but we can solve this task in O(n × n) instead. The key observation is that the x values we need to consider are the ones which have vertical lines on it. So, only n x values and n y values need to be considered during the discretization. I was planned to make O(2n × 2n) solutions TLE but Dreamoon stopped me.

從 n 的大小我們可以知道 O(n²) 的演算法足以通過。可以猜到最後一步可以用 flood fill 的方法來枚舉每個房間。依據這個直覺，我們可以得出必須要在 O(n²) 的時間內離散化的結論。事實上這是可行的，甚至因為只有 O(n) 道牆壁，所以我們對於每道牆壁可以花 O(n) 的時間來把它轉化到離散的地圖上。

我們要小心不要數到那些沒有被完整包圍的區域，一個可能的方法是在 flood fill 的時候小心處理 (例如在超出邊界時採用不同的回傳值)，另外一個方法是在開始 flood fill 前先把所有外圍的區域標記起來。

O(2n × 2n) 的演算法可以通過測試，不過其實我們可以做到 O(n × n)。一個關鍵的觀察是，我們只需要考慮那些有垂直牆壁的 x 座標，所以我們在離散化時所考慮的 x 跟 y 座標可以只有 n 個。我本來想讓 O(2n × 2n) 的作法 TLE，但是 Dreamoon 阻止了我。

PF

First, let's consider a simpler task: We have n1 pieces with 1 unit of weight and n2 pieces of 2 units of weight without any order (i.e. you can reorder them as much as you want). How many round trips are needed? This task can be greedily solved in O(1) by putting 2 first. Another variation of this task is that given n1 pieces with 1 unit of weight and n2 pieces of 2 units of weight without any order and the truck is loaded x units of weight currently. What is the minimum number of round trips required if the load in the trunk can not be pulled out? This task can also be solved in O(1) in a similar way.

Let's consider a DP solution to the original problem. The table looks like DP[pos][c1][c2] where pos is the position of the current piece of baggage and c1, c2 is the number of 1 weight and 2 weight pieces that have been pulled out already. Each entry of DP[pos][c1][c2] stores the minimum wasted truck space of that state.

We need to consider three kinds of transitions:

1. pull out the current piece: dpt[pos][c1 + (current_weight == 1)][c2 + (current_weight == 2)] = dpt[pos — 1][c1][c2]

2. load the current piece to the trunk (if possible): dpt[pos][c1][c2] = dpt[pos — 1][c1][c2]

3. Make the current piece to be the first piece of next round trip: dpt[pos][c1][c2] = dpt[pos — 1][c1][c2] + current_truck_free_space

Note that when doing the DP we need to know the current free space of the truck, we can obtain this value by the simpler task mentioned earlier.

Finally we check DP[n][c1][c2] for every c1 and c2 values. We pick the minimum c1 + c2 among those states require the optimal number of trips (again the simpler task can be utilized to find the number of trips needed). The time complexity is O(n³).

首先，讓我們考慮一個比較簡單的子題目：我們有 n1 個 1 單位重量的行李跟 n2 個 2 單位重量的行李，如果不考慮順序(也就是你可以任意安排順序)，請問至少要多少趟才載的完？這個子題目可以貪心的用 O(1) 的時間解掉，只要優先載運 2 單位重量的行李就好了。另外一個難一點的子題目：給定 1 單位重量的行李數量跟 2 單位重量的行李數量，也不考慮順序，並且此時車內已經有 x 單位重量且不可抽出的行李，請問至少要多少趟才載的完？這個子題目也可以用 O(1) 以類似的方法解掉。

對於原來的問題，我們考慮一個 DP，DP[pos][c1][c2]。pos 代表現在要處理的行李編號，而 c1 及 c2 分別代表已經被拉出來的 1 跟 2 單位重量的行李件數。DP[pos][c1][c2] 的數值代表這個狀態中最少需要浪費掉多少的卡車空間。

考慮三種轉移：

1. 把目前行李拉出來： dpt[pos][c1 + (current_weight == 1)][c2 + (current_weight == 2)] = dpt[pos — 1][c1][c2]

2. 如果可以的話把目前行李裝上車： dpt[pos][c1][c2] = dpt[pos — 1][c1][c2]

3. 把目前行李當成下一趟的第一件行李： dpt[pos][c1][c2] = dpt[pos — 1][c1][c2] + current_truck_free_space

在 DP 的過程中我們必須知道目前的狀態中，卡車還剩下多少空間，上面提到的子問題可以幫助我們計算這個值。

最後，對於所有 c1 及 c2 的值，我們檢查 DP[n][c1][c2] 去求答案。答案即為滿足最少趟數(趟數也可以用子問題求得)的狀態中， c1 + c2 最小的那一個。總時間複雜度為 $O(n^3)$。

First I want to thank all the problem solvers!
Hope you had or are going to have a good time with Dreamoon!

If you think there's something that can be improved in this editorial please let me know!

Definitions used in this editorial:
⌈⌉ stands for ceiling function.
⌊⌋ stands for floor function.
stands for real division.
For non-negative integer a and positive integer b, div(a, b) stands for integral division, .
For non-negative integer a and positive integer b, mod(a, b) stands for module operation, a = div(a, b) * b + mod(a, b).
length(string) is the length of string.
For non-negative integer a ≤ b, A[a..b] stands for the set of A[a], A[a + 1], A[a + 2]... A[b - 1] when A is an array and the substring of A consists of a^th to (b - 1)^th character(inclusive) of A when A is a string. For such substring we have length(A[a..b]) = b - a.
C(a, b) stands for the combination function, the ways of selecting a elements from a group of b elements.

476A - Dreamoon and Stairs
We can show that the maximum number of moves possible is n and minimal moves needed is , so the problem equals to determine the minimal integer that is a multiple of m in the range .
One way to find the minimal number which is a multiple of m and greater than or equal to a number x is , we can compare this number to the upper bound n to determine if there is a valid solution.
Although best practice is O(1), O(n) enumeration of each possible number of moves would also work.
time complexity: O(1)
sample code: 8212169
explanation of sample code:
The can be calculated in the following c++ code if a is non-negative and b is positive: (a+b-1)/b
Because / in c++ is integral division so (a+b-1)/b would result in
Let a = div(a, b)b + mod(a, b) = db + m, .
Which means if , otherwise div(a + b - 1, b) = d + 1. Can be translated to if , otherwise div(a + b - 1, b) = div(a, b) + 1. Which matches the value of .

476B - Dreamoon and WiFi
The order of moves won't change the final position, so we can move all '?'s to the end of the string.
We have the following information:
1. the correct final position
2. the position that Dreamoon will be before all '?'s
3. the number of '?'s
We can infer that the distance and direction dreamoon still needs to move in the '?' part from 1. and 2., and furthur translate that to how many +1s and -1s dreamoon will need to move.
What's left is a combinatorial problem, the probability would be .
So we can compute that formula within O(n) time assuming n is the length of commands, but since N is small so we can brute force every possible choice of '?' with some recursive or dfs like search in O(2ⁿ) time complexity.
Note that the problem asks for a precision of 10^- 9, so one should output to 11 decimal places or more.
time complexity: O(n), assuming n is the length of commands.
sample code: 8215177

476C - Dreamoon and Sums / 477A - Dreamoon and Sums
If we fix the value of k, and let d = div(x, b), m = mod(x, b), we have :
d = mk
x = db + m
So we have x = mkb + m = (kb + 1) * m.
And we know m would be in range [1, b - 1] because it's a remainder and x is positive, so the sum of x of that fixed k would be .
Next we should notice that if an integer x is nice it can only be nice for a single particular k because a given x uniquely defines div(x, b) and mod(x, b).
Thus the final answer would be sum up for all individual k: which can be calculated in O(a) and will pass the time limit of 1.5 seconds.
Also the formula above can be expanded to . Dreamoon says he's too lazy to do this part, so if you use O(1) solution you just computed the answer faster than Dreamoon!!!
Note that no matter which approach one should be very careful of overflowing of the integer data type of the used language. For example one should do a module after every multiplication if using 64-bit integer type. And pay attention to precedence of operations: take c++ for example a+b%c would be executed as a+(b%c) instead of (a+b)%c, another c++ example a*(b*c)%m would be executed as (a*(b*c))%m instead of a*((b*c)%m).
Thanks saurabhsuniljain for pointing out the preceding problem and examples in the comment!
time complexity: O(1)
sample code: 8215188

476D - Dreamoon and Sets / 477B - Dreamoon and Sets
The first observation is that if we divide each number in a set by k, than the set would be rank 1. So we could find n sets of rank 1 then multiple every number by k.
For how to find n sets of rank 1, we can use {6a + 1, 6a + 2, 6a + 3, 6a + 5} as a valid rank 1 set and take a = 0 to n - 1 to form n sets and thus m = (6n - 1) * k.
The proof that m is minimal can be shown by the fact that we take three consecutive odd numbers in each set. If we take less odd numbers there will be more than 1 even number in a set which their gcd is obviously a multiple of 2. And if we take more odd numbers m would be larger.
The output method is straight forward. Overall time complexity is O(n).
time complexity: O(n)
sample code: 8215198

476E - Dreamoon and Strings / 477C - Dreamoon and Strings
First let A[i] to be the minimal length L needed so that substring s[i..i + L] can become pattern p by removing some characters. We can calculate this greedily by keep selecting next occurrence of characters in p in O(length(s)) time for a fixed i, so for all i requires O(length(s)²).
Next we can do a dp D[i][j] where D[i] is the answer array for s[0..i]. D[i] can contribute to D[i + 1] with 0 or 1 removal and to D[i + A[i]] with A[i] - length(p) removal(s). In other words, D[i][j] can transition into tree relations D[i + 1][j] = D[i][j] //not delete s[i], D[i + 1][j + 1] = D[i][j] //delete s[i], and D[i + A[i]][j + A[i] - length(p)] = D[i][j] + 1 //form a substring p by deleting A[i] - length(p) characters. Calculate forwardly from D[0] to D[length(s) - 1] gives the final answer array as D[length(s)]. Calculating D[i] requires O(length(s)) time for a fixed i, so for all i takes O(length(s)²) time.
time complexity: O(n²), n = length(s)
sample code: 8215203

Another solution:
Let k = div(length(s), length(p)). We can run an edit distance like algorithm as following (omitting the details of initialization and boundary conditions):

for(i=0;i<n;i++)
    for(j=0;j<k*p;j++)
        if(s[i]==p[j%length(p)])
            D[i][j] = D[i-1][j-1]
         D[i][j] = min(D[i][j], D[i-1][j] + (j%length(p)!=length(p)-1))

That means remove cost is 1 when it is in the middle of a p and 0 elsewhere because p need to be consecutive(thus no need to be actually remove outside of a p). Then D[n][t * length(p)] is the minimal number of removals to have t non-overlapping substring of p. So we have answer[D[n][t * length(p)..(t + 1) * length(p)] = t. And after the maximal t is reached, decrease answer by 1 for every length(p).
time complexity: O(n²)
sample code: 8215394

477D - Dreamoon and Binary
Let Xb be the binary string of number X. An ideal sequence can be expressed as a partition of Xb: P₁ = Xb[1..p₁], P₂ = Xb[p₁..p₂], ... P_K = Xb[p_K - 1..length(Xb)] where P_i ≤ P_i + 1. The length of operations of such sequence is P_K + K.
We can calculate the number of different ideal sequences by dp. State D[i][j] stands for the answer of state that we have print Xb[1..j] and last partition is Xb[i..j]. A possible way of transition is that a state D[i][j] can go to state D[i][j + 1] and D[j][k] where k is the minimal possible position such that value of Xb[j..k] is equal to or greater than the value of Xb[i..j] and Xb[j] is 1 since we can't print any leading 0.
Note that D[j][k + 1] can also derived from D[i][j] but it will covered by D[i][j] → D[j][k] → D[j][k + 1], so we don't need to consider this case to avoid redundant counts.
If we can determine k for each i, j pair in O(1) then we can compute this dp in O(length(Xb)²) in the following manner:

for(j=0;j<n;j++)
    for(i=0;i<j;i++)
        compute the transitions of D[i][j]

So let's look into how to calculate the value k for a given i, j pair. If the value of Xb[j..2j - i] is equal to or greater than Xb[i..j] than k is 2j - i because if k is less than 2j - i would make length of the new partition less than the previous partition thus its value would be lesser. And if k can't be 2j - i, the value of 2j - i + 1 is always a valid choice because it would make the length of the new partition greater than the previous one. So for each length L if we know the order of Xb[i..i + L] and Xb[i + L..i + 2L] in O(1) time we can calculate k in O(1) time(can be easily shown by assuming L = j - i).
One way of doing such is using prefix doubling algorithm for suffix array construction to build a RMQ structure for query in O(1) time. The prefix doubling algorithm requires O(nlgn) precompute time. Note there is still a various of ways to do this part of task in the same or better time complexties.
And for the shortest length part we can compute the minimal parts needed so far for each state along with the preivous dp. Then compare all states ends with j = length(Xb).
Overall we can solve this problem in O(length(Xb)²) with caution in details like boundaries and module operations.
time complexity: O(n²), n = length(Xb)
Note the sample code use a nlgnlgn version of prefix doubling algorithm
sample code: 8215216

477E - Dreamoon and Notepad
Although swapping two parts of a query would result in different answer, if we reverse the lines length alltogether then the answer would stay the same. So we only analyze queries where r2 ≥ r1.
The answers would comes in several types, we’ll discuss them one by one:
1. HOME key being pressed once: the answer will be 1(HOME) + r2 - r1(down keys) + c2(right keys). Note that this is the best answer if the HOME key is ever pressed once, so we won’t consider HOME key anymore. This step is O(1) for a single query, thus O(q) in total.
2. direct presses r2 - r1 down keys and no or one END key in those rows: because the cursor position will be reset to the row length if we go down to a row with length less than current cursor position, the possible positions that can be at row p if we start at end of each previous rows can be track with a stack. The position directly pressing only down keys from r1 to r2 is min(c1, the length of first row after r1 in stack). We can use a binary search to get the first row after or equal r1 in stack. From that row till r2 in the stack are the positions possible when pressing ONE END key (pressing more won’t get more possible positions), we can use a binary search to find the position closest to c2 which is the best. We can sort all queries and use O(qlgn) time for queries and O(n) time for maintaining stack, so O(qlgn + n) in total.
3. go back some rows and press one or no END key at the row: we only interested in END OF rows in stack constructed in 2.. We can use a binary search in stack to identify the range of rows interested. For those lengths of row less than c2(also can use a binary search to locate) we only need to consider the first one encountered(closest to r1), note still need to consider if it needs an END key for this case. For those lengths of row greater than or equal to c2, the answer would be r1 + r2 - 2 * (row reached) + (length of the row) - c2 + (1 if length of the row greater than c1). The terms related to row in the previous formula is 2 * (row reached) + (length of the row) + (1 if length of the row greater than c1). We can identify the range with and without +1(last term) and query in a segment tree of the minimal value of 2 * (row reached) + (length of the row) for each range. Thus the time need here is O(nlgn) for maintaining segment tree and O(qlgn) for query while sharing with the stack of 2., so O(nlgn + qlgn) in total.
4. go beyond r2 some rows and press no or one END at the row: this needs a reversed stack and very similar approach of 3.. The time complexity is the same as 2. and 3..
So the total time complexity is O((n + q)lgn), note this problem is very hard to get the code right.
time complexity: O((n + q)lgn)
sample code: 8212528

Hello, everyone! Codeforces Round #272 will be held at this local time. We're looking forward to your participation!

The problems are from dreamoon_love_AA and drazil(that's me) from Taiwan, and thanks 9mmlitswe for some discussion. Also we want to thank Zlobober and Gerald for helping us prepare the round, Delinur for translating the statement into Russian, and MikeMirzayanov for Codeforces and Polygon.

This is our first round on Codeforces, we hope you'll find it interesting! Please read all problem statements and discover what the main character dreamoon_love_AA do in those problems for he's really cute =)

Update1 Note this round will be held 1.5hrs earlier than usual Codeforces rounds, so please double check the starting time in your local time.

Update2 Score distribution!
Div2: 500-1500-1500-2000-2500
Div1: 500-1000-1500-2000-3000

Update3 The contests are over. Congratulations to the winners!

Div1:
1. Petr
2. qwer1561
3. kutengine
4. ifsmirnov
5. TankEngineer

Div2:
1. ridowan007
2. a00012025
3. xavier13540
4. v_Enhance
5. pkq2006

And standings are here:
Div1: standings
Div2: standings

Update4 Editorial can be found here. It's finished by now but it's welcome to tell me if anything can be improved!